java - 我在使用 theGraph.bfs 函数时需要帮助

Question

我已经实现了 BFS。并且使用 BFS，我想实现影响最大化的贪婪逼近算法。我的代码进入无限循环。我需要帮助确定发生的逻辑错误。在贪婪影响最大化中，我想在代码中创建一组最大长度 val （变量）。基于节点和边的阈值执行 BFS。使用 BFS，我们可以知道使用图的一个顶点可以达到多少个顶点。

    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Set;
    import java.util.Collections;
    
    class Vertex {
    
        public char label;
        public boolean wasVisited;
    
        public Vertex(char lab) {
            label = lab;
            wasVisited = false;
        }
    }
    
    class Graph {
    
        private final int MAX_VERTS = 20;
        private Vertex vertexList[]; //node_weight[] ;
        private int adjMat[][];
        private int nVerts, NV, count;
        private float node_weight[], prob_matrice[][];
        private Queue<Integer> q, q1, q2, q3;
        private int probsum;
    
        public Graph() {
            vertexList = new Vertex[MAX_VERTS];
            node_weight = new float[MAX_VERTS];
            adjMat = new int[MAX_VERTS][MAX_VERTS];
            prob_matrice = new float[MAX_VERTS][MAX_VERTS];
            nVerts = 0;
            NV = 0;
            // count =0;
            q = new LinkedList<Integer>();
            q1 = new LinkedList<Integer>();
            //    q2 = new LinkedList<Integer>();
            //    q3 = new LinkedList<Integer>();
        }
    
        public void addVertex(char lab) {
            vertexList[nVerts++] = new Vertex(lab);
            //  node_weight[nVerts++] = nw;
        }
    
        public void nodeweight(float nw) {
            node_weight[NV++] = nw;
        }
    
        public void addEdge(int start, int end, float pb1, float pb2) {
            adjMat[start][end] = 1;
            adjMat[end][start] = 1;
            prob_matrice[start][end] = pb1;
            prob_matrice[end][start] = pb2;
        }
    
        public void displayVertex(int v) {
            System.out.print(vertexList[v].label);
            // count++;
        }
    
        public int activecounts() {
            int d = 0;
            int y;
            for (y = 0; y < nVerts; y++) {
                if (vertexList[y].wasVisited == true) {
                    d++;
                }
              //  System.out.println("The activated nodes are:" + d);
            }
            return d;
            
          //  System.out.println(count);
           // return count;
        }
    
        public void probmatdis(int nvp) {
            System.out.println("Probability matrice");
            for (int i = 0; i < nvp; i++) {
                for (int j = 0; j < nvp; j++) {
                    System.out.print(prob_matrice[i][j] + "\t");
                }
                System.out.println();
            }
        }
    
        public void nodeweightdis(int nvp) {
            System.out.println("Node Weight matrice");
            for (int i = 0; i < nvp; i++) {
                System.out.print(node_weight[i] + "\t");
    
            }
            System.out.println();
        }
    
        public int getAdjUnvisitedVertex(int v) {
            int j;
            for (j = 0; j < nVerts; j++) {
                if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
                    for (int k = 0; k < nVerts; k++) {
                        if (adjMat[j][k] == 1 && vertexList[k].wasVisited == true) {
                            q1.add(k);
                        }
                    }
                    float probsum = 0;
                    //     int queuelength = q1.size();
                    while (!q1.isEmpty()) {
                        //for(l = 0; l<queuelength; l++){
                        int e = q1.remove();
                        probsum = probsum + prob_matrice[e][j];
                        // }
                    }
    
                    if (probsum >= node_weight[j]) {
                        return j;
                    }
                }
            }
            //   q1.clear();
            return -1;
    
        }
    
        public void bfs(Integer sv[]) {
            for (int i = 0; i < sv.length; i++) {
                vertexList[sv[i]].wasVisited = true;
                displayVertex(sv[i]);
                q.add(sv[i]);
            }
            int v2;
            while (!q.isEmpty()) {
                int[] v1 = new int[sv.length];
                for (int i = 0; i < sv.length; i++) {
                    try {
                        //      System.out.println(q.element());
                        v1[i] = q.remove();
                        while ((v2 = getAdjUnvisitedVertex(v1[i])) != -1) {
                            vertexList[v2].wasVisited = true;
                            displayVertex(v2);
                            //     System.out.println("line");
                            q.add(v2);
                        }
                    } catch (Exception e) {
                        System.out.println("Exception: " + e);
                    }
                }
    
            }
            
        }
        //  q.clear();
    
    //    public static int[] convertIntSetToStringSet(
    //            Set<Integer> setOfInteger) {
    //        return setOfInteger.stream()
    //                .mapToInt(Integer::intValue)
    //                .toArray();
    //    }
        
        
    }
    
    public class Active {
    
        public static void main(String[] args) {
            Graph theGraph = new Graph();
            int n_vertex;
            Scanner sc1, sc2;
            sc1 = new Scanner(System.in);
            System.out.println("Enter the number of vertices in Graph:");
            n_vertex = sc1.nextInt();
            sc2 = new Scanner(System.in);
    
            for (int i = 0; i < n_vertex; i++) {
                System.out.println("Enter the node");
                String st = sc2.next();
                char ch = st.charAt(0);
                System.out.println("Enter the node weight");
                float node_weight = sc1.nextFloat();
                //char ver = sc.next().charAt(0);
                theGraph.addVertex(ch);
                theGraph.nodeweight(node_weight);
    
            }
    
            System.out.println("Enter the Count of Edges in Graph:");
    
            // sc1 = new Scanner(System.in);
            int n_edges = sc1.nextInt();
            for (int i = 0; i < n_edges; i++) {
                System.out.println("Enter the Starting Vertex of the edge in Graph:");
                int start_edge = sc1.nextInt();
                System.out.println("Enter the Ending Vertex of the edge in Graph:");
                int end_edge = sc1.nextInt();
                float probability1, probability2;
                probability1 = sc1.nextFloat();
                probability2 = sc1.nextFloat();
                theGraph.addEdge(start_edge, end_edge, probability1, probability2);
            }
    
            theGraph.nodeweightdis(n_vertex);
            theGraph.probmatdis(n_vertex);
    
            Set<Integer> SetXi = new HashSet<Integer>();
           //   Set<Integer> SetXi = Collections.emptySet();  
            Set<Integer> temp = new HashSet<Integer>();
            Set<Integer> calc = new HashSet<Integer>();
            System.out.println("Enter the size of the seed set");
            Integer val = sc1.nextInt();
            Integer[] xiunioncount = new Integer[n_vertex];
            Integer xicount = 0;
            Integer[] difference = new Integer[n_vertex];
            Integer p;
            while ((SetXi.size()) <= val) {
                
                for (p = 0; p < n_vertex; p++) {
                    temp.addAll(SetXi);
                    temp.add(p);
    //                Iterator itr = temp.iterator();
    //                while (itr.hasNext()) {
    //                System.out.println(itr.next());
    //                }
                    Integer h = temp.size();
                    Integer[] unionarray = new Integer[h];
                    unionarray = temp.toArray(unionarray);
                  theGraph.bfs(unionarray);
                   xiunioncount[p] = theGraph.activecounts();
                 //   System.out.println(xiunioncount[p]);
                    difference[p] = xiunioncount[p] - xicount;
                   // temp.clear();
                }
    
                int max = difference[0];
                Integer ind = 0;
                for (int n = 0; n < n_vertex; n++) {
                    if (max < difference[n]) {
                        max = difference[n];
                        ind = n;
                    }
                }
    
                //   xicount = Collections.max(Arrays.asList(difference));
                
                xicount = max;
                Integer arr[] = {ind};
    
                Collections.addAll(calc, arr);
                SetXi.addAll(calc);
            }
    
            System.out.println("Seed Set is");
            Iterator itr = SetXi.iterator();
            while (itr.hasNext()) {
                System.out.println(itr.next());
    
            }
        }
    }

标签： javabreadth-first-search