我已经实现了 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());
}
}
}