java 遍历过 BFS 的图的树结构图
Showing the tree structure of a graph in which BFS traversal has been performed in java
我在研究广度优先搜索或 BFS 算法时遇到了一个想法。我显示了我在其中实现了 BFS 的图的树结构。现在也许我可以使用链表以不同的方式显示树结构,但我想修改我用来显示树结构的 BFS 方法
public class BFS
{
private Queue<Integer> queue;
public BFS()
{
queue = new LinkedList<Integer>();
}
public void bfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + "\t");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
上面给出的是我的 BFS 方法,有人可以帮助我让我知道我必须对代码进行哪些确切的修改才能获得所需的输出
例如,假设给定的邻接矩阵是这样的:
{0,1,0,0,0,1,0,0
1,0,0,0,0,0,0,0
0,0,0,0,0,0,1,0
0,0,0,0,0,0,1,1
0,0,0,0,0,1,0,0
1,0,0,0,1,0,1,0
0,0,1,0,0,1,0,1
0,0,0,1,0,0,0,1}
这个图的树结构是这样的
A
/ \
B F
/ \
E G
/ | \
C H D
用 BFS 可以做你描述的事情,但是很麻烦。 Post-Order Traversal 或 In-Order Traversal 可能更合适。检查 here 并查看适合的内容。
我在研究广度优先搜索或 BFS 算法时遇到了一个想法。我显示了我在其中实现了 BFS 的图的树结构。现在也许我可以使用链表以不同的方式显示树结构,但我想修改我用来显示树结构的 BFS 方法
public class BFS
{
private Queue<Integer> queue;
public BFS()
{
queue = new LinkedList<Integer>();
}
public void bfs(int adjacency_matrix[][], int source)
{
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
queue.add(source);
while (!queue.isEmpty())
{
element = queue.remove();
i = element;
System.out.print(i + "\t");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
queue.add(i);
visited[i] = 1;
}
i++;
}
}
}
上面给出的是我的 BFS 方法,有人可以帮助我让我知道我必须对代码进行哪些确切的修改才能获得所需的输出
例如,假设给定的邻接矩阵是这样的:
{0,1,0,0,0,1,0,0
1,0,0,0,0,0,0,0
0,0,0,0,0,0,1,0
0,0,0,0,0,0,1,1
0,0,0,0,0,1,0,0
1,0,0,0,1,0,1,0
0,0,1,0,0,1,0,1
0,0,0,1,0,0,0,1}
这个图的树结构是这样的
A
/ \
B F
/ \
E G
/ | \
C H D
用 BFS 可以做你描述的事情,但是很麻烦。 Post-Order Traversal 或 In-Order Traversal 可能更合适。检查 here 并查看适合的内容。