如何对图进行不同的基本遍历？
How to perform different basic traversals of graphs?
我正在尝试对给定图执行迭代广度优先遍历、迭代深度优先遍历和递归深度优先遍历（使用邻接矩阵）。
在当前状态下，我的程序输出各种错误答案。
这里有一些例子。
我很期待
From Node A
DFS (iterative): A B H C D E I F G
DFS (recursive): A B H C D E I F G
BFS (iterative): A B D I H C E F G
但我得到了
From Node A
DFS (iterative): A I D B H C F G E
DFS (recursive): A B H C F D E I G
BFS (iterative): A B D I H C E F G
我不确定我的程序的问题是在于遍历的实现，还是在于我对程序其他部分的实现。更具体地说，我不确定是我的实现 connectNode 或 getNeighbors 方法导致了不正确的输出，还是我的遍历实现。
编辑：如果这很重要，应该按升序选择邻居。也许这是问题的一部分？
EDIT2：感谢@HylianPikachu 的建议，我添加了新的代码行。我现在得到了完整的答案，但它们的顺序仍然不正确。
EDIT3：我添加了代码以使其成为 bfs 和递归 dfs 的访问根节点。我认为。我还应该注意，我得到了这段代码的一部分，并被告知要填写其余部分。堆栈和队列的使用是我被告知要使用的，尽管可能有更好的选择。
EDIT4：添加了所建议的内容，现在，迭代 BFS 工作并获得了正确的结果。但是，两个 DSF 搜索仍然不起作用。我修改了上面程序的结果，以显示这一点。
import java.util.*;
public class GraphM {
public Node rootNode;
public List<Node> nodes = new ArrayList<Node>(); // nodes in graph
public int[][] adjMatrix; // adjacency Matrix
public void setRootNode(Node n) {
rootNode = n;
}
public Node getRootNode() {
return rootNode;
}
public void addNode(Node n) {
nodes.add(n);
}
// This method connects two nodes
public void connectNode(Node src, Node dst) {
if(adjMatrix == null) {
adjMatrix = new int[nodes.size()][nodes.size()];
}
adjMatrix[nodes.indexOf(src)][nodes.indexOf(dst)] = 1;
adjMatrix[nodes.indexOf(dst)][nodes.indexOf(src)] = 1;
}
// Helper method to get one unvisited node from a given node n.
private Node getUnvisitedChildNode(Node n) {
int index = nodes.indexOf(n);
int size = adjMatrix.length;
for (int j = 0; j < size; j++)
if (adjMatrix[index][j] == 1 && ((Node) nodes.get(j)).visited == false)
return nodes.get(j);
return null;
}
// get all neighboring nodes of node n.
public List<Node> getNeighbors(Node n) {
List<Node> neighbors = new ArrayList<Node>();
for(int i = 0; i < nodes.size(); i ++) {
if (adjMatrix[nodes.indexOf(n)][i] == 1) {
neighbors.add(nodes.get(i));
}
Collections.sort(neighbors);
}
return neighbors;
}
// Helper methods for clearing visited property of node
private void reset() {
for (Node n : nodes)
n.visited = false;
}
// Helper methods for printing the node label
private void printNode(Node n) {
System.out.print(n.label + " ");
}
// BFS traversal (iterative version)
public void bfs() {
Queue<Node> queue = new LinkedList<Node>();
queue.add(rootNode);
while(!queue.isEmpty()) {
Node node = queue.poll();
printNode(node);
node.visited = true;
List<Node> neighbors = getNeighbors(node);
for ( int i = 0; i < neighbors.size(); i ++) {
Node n = neighbors.get(i);
if (n != null && n.visited != true) {
queue.add(n);
n.visited = true;
}
}
}
}
// DFS traversal (iterative version)
public void dfs() {
Stack<Node> stack = new Stack<Node>();
stack.add(rootNode);
while(!stack.isEmpty()){
Node node = stack.pop();
if(node.visited != true) {
printNode(node);
node.visited = true;
}
List<Node> neighbors = getNeighbors(node);
for (int i = 0; i < neighbors.size(); i++) {
Node n = neighbors.get(i);
if(n != null && n.visited != true) {
stack.add(n);
}
}
}
}
// DFS traversal (recursive version)
public void dfs(Node n) {
printNode(n);
n.visited = true;
List<Node> neighbors = getNeighbors(n);
for (int i = 0; i < neighbors.size(); i ++) {
Node node = neighbors.get(i);
if(node != null && node.visited != true) {
dfs(node);
}
}
}
// A simple Node class
static class Node implements Comparable<Node> {
public char label;
public boolean visited = false;
public Node(char label) {
this.label = label;
}
public int compareTo(Node node) {
return Character.compare(this.label, node.label);
}
}
// Test everything
public static void main(String[] args) {
Node n0 = new Node('A');
Node n1 = new Node('B');
Node n2 = new Node('C');
Node n3 = new Node('D');
Node n4 = new Node('E');
Node n5 = new Node('F');
Node n6 = new Node('G');
Node n7 = new Node('H');
Node n8 = new Node('I');
// Create the graph (by adding nodes and edges between nodes)
GraphM g = new GraphM();
g.addNode(n0);
g.addNode(n1);
g.addNode(n2);
g.addNode(n3);
g.addNode(n4);
g.addNode(n5);
g.addNode(n6);
g.addNode(n7);
g.addNode(n8);
g.connectNode(n0, n1);
g.connectNode(n0, n3);
g.connectNode(n0, n8);
g.connectNode(n1, n7);
g.connectNode(n2, n7);
g.connectNode(n2, n3);
g.connectNode(n3, n4);
g.connectNode(n4, n8);
g.connectNode(n5, n6);
g.connectNode(n5, n2);
// Perform the DFS and BFS traversal of the graph
for (Node n : g.nodes) {
g.setRootNode(n);
System.out.print("From node ");
g.printNode(n);
System.out.print("\nDFS (iterative): ");
g.dfs();
g.reset();
System.out.print("\nDFS (recursive): ");
g.dfs(g.getRootNode());
g.reset();
System.out.print("\nBFS (iterative): ");
g.bfs();
g.reset();
System.out.println("\n");
}
}
}
我建议将您的问题分解成更小的部分。
如果你想为无向图编写 class，请先编写并测试一下。
如果你想看看你是否可以实现遍历，首先要确保你的图能正常工作。您还可以使用 guava, which lets you use MutableGraph (and lots more). Here is how to install it in case you're using IntelliJ and here 是如何使用来自番石榴的图表。
另外记得使用调试器来找出您的代码是否出错。
所以，我们已经涵盖了你问题的第一部分，但我会在这里为后续的人重申一下。每当使用图形和邻接矩阵时，初始化数组中元素的最佳方法可能是 "both ways."
与其仅使用以下内容，还需要首先列出特定顶点才能找到邻居：
adjMatrix[nodes.indexOf(src)][nodes.indexOf(dst)] = 1;
使用这个，它会导致与顶点顺序无关的搜索：
adjMatrix[nodes.indexOf(src)][nodes.indexOf(dst)] = 1;
adjMatrix[nodes.indexOf(dst)][nodes.indexOf(src)] = 1;
现在，订购。您希望按照从 "least" 字母到 "greatest" 字母的顺序输出顶点。我们将单独处理您的每个数据结构。
在 BFS（迭代）中，您使用队列。队列是"first in, first out." 换句话说，每当您调用queue.poll() 时，最近最少添加到队列中的元素将首先输出。因此，您需要从最小到最大添加节点。
在 DFS（迭代）中，您使用堆栈。 Stacks是"last in, first out." 换句话说，当你调用stack.pop()时，最近添加到Stack中的元素将首先输出。因此，您需要从大到小添加节点。
在 DFS（递归）中，您使用列表。列表本身没有 "in-out" 排序，因为我们可以按我们想要的任何顺序轮询它们，但最简单的事情就是将列表从最小到最大排序并按顺序输出它们。
考虑到这一点，我们需要引入对图进行排序的协议。这三个协议都使用 getNeighbors()，因此我们将在调用该函数后立即对输出的列表进行排序。可以使用 java.utils.Collections 中的函数 Collections.sort(List l) 对列表进行排序，但我们首先需要修改您的节点 class，以便 Java 知道如何对节点进行排序。要进一步阅读我正在做的事情的详细信息，您可以查看 here，但是这个 post 比我预期的要长得多，所以我将在这里展示代码，让感兴趣的人自己去探索link。
您首先要通过实施 Comparable<Node> 并添加 compareTo() 函数来调整您的节点 class。
static class Node implements Comparable<Node>{
public char label;
public boolean visited = false;
public Node(char label) {
this.label = label;
}
@Override
public int compareTo(Node that) {
return Character.compare(this.label, that.label);
}
}
然后，如果我们想对List进行从小到大的排序，我们可以使用Collections.sort(neighbors)。当我们想要它从大到小时，我们可以使用Collections.sort(neighbors, Collections.reverseOrder())。我们的最终代码将如下所示：
// BFS traversal (iterative version)
public void bfs() {
Queue<Node> queue = new LinkedList<Node>();
queue.add(rootNode);
while(!queue.isEmpty()) {
Node node = queue.poll();
printNode(node);
node.visited = true;
List<Node> neighbors = getNeighbors(node);
//NEW CODE: Sort our neighbors List!
Collections.sort(neighbors);
for ( int i = 0; i < neighbors.size(); i ++) {
Node n = neighbors.get(i);
if (n != null && n.visited != true) {
queue.add(n);
n.visited = true;
}
}
}
}
// DFS traversal (iterative version)
public void dfs() {
Stack<Node> stack = new Stack<Node>();
stack.add(rootNode);
while(!stack.isEmpty()){
Node node = stack.pop();
if(node.visited != true) {
printNode(node);
node.visited = true;
}
List<Node> neighbors = getNeighbors(node);
//NEW CODE: Sort our neighbors List in reverse order!
Collections.sort(neighbors, Collections.reverseOrder());
for (int i = 0; i < neighbors.size(); i++) {
Node n = neighbors.get(i);
if(n != null && n.visited != true) {
stack.add(n);
}
}
}
}
// DFS traversal (recursive version)
public void dfs(Node n) {
printNode(n);
n.visited = true;
List<Node> neighbors = getNeighbors(n);
//NEW CODE: Sort our neighbors List!
Collections.sort(neighbors);
for (int i = 0; i < neighbors.size(); i ++) {
Node node = neighbors.get(i);
if(node != null && node.visited != true) {
dfs(node);
}
}
}
我正在尝试对给定图执行迭代广度优先遍历、迭代深度优先遍历和递归深度优先遍历（使用邻接矩阵）。
在当前状态下，我的程序输出各种错误答案。
这里有一些例子。
我很期待
From Node A
DFS (iterative): A B H C D E I F G
DFS (recursive): A B H C D E I F G
BFS (iterative): A B D I H C E F G
但我得到了
From Node A
DFS (iterative): A I D B H C F G E
DFS (recursive): A B H C F D E I G
BFS (iterative): A B D I H C E F G
我不确定我的程序的问题是在于遍历的实现，还是在于我对程序其他部分的实现。更具体地说，我不确定是我的实现 connectNode 或 getNeighbors 方法导致了不正确的输出，还是我的遍历实现。
编辑：如果这很重要，应该按升序选择邻居。也许这是问题的一部分？
EDIT2：感谢@HylianPikachu 的建议，我添加了新的代码行。我现在得到了完整的答案，但它们的顺序仍然不正确。
EDIT3：我添加了代码以使其成为 bfs 和递归 dfs 的访问根节点。我认为。我还应该注意，我得到了这段代码的一部分，并被告知要填写其余部分。堆栈和队列的使用是我被告知要使用的，尽管可能有更好的选择。
EDIT4：添加了所建议的内容，现在，迭代 BFS 工作并获得了正确的结果。但是，两个 DSF 搜索仍然不起作用。我修改了上面程序的结果，以显示这一点。
import java.util.*;
public class GraphM {
public Node rootNode;
public List<Node> nodes = new ArrayList<Node>(); // nodes in graph
public int[][] adjMatrix; // adjacency Matrix
public void setRootNode(Node n) {
rootNode = n;
}
public Node getRootNode() {
return rootNode;
}
public void addNode(Node n) {
nodes.add(n);
}
// This method connects two nodes
public void connectNode(Node src, Node dst) {
if(adjMatrix == null) {
adjMatrix = new int[nodes.size()][nodes.size()];
}
adjMatrix[nodes.indexOf(src)][nodes.indexOf(dst)] = 1;
adjMatrix[nodes.indexOf(dst)][nodes.indexOf(src)] = 1;
}
// Helper method to get one unvisited node from a given node n.
private Node getUnvisitedChildNode(Node n) {
int index = nodes.indexOf(n);
int size = adjMatrix.length;
for (int j = 0; j < size; j++)
if (adjMatrix[index][j] == 1 && ((Node) nodes.get(j)).visited == false)
return nodes.get(j);
return null;
}
// get all neighboring nodes of node n.
public List<Node> getNeighbors(Node n) {
List<Node> neighbors = new ArrayList<Node>();
for(int i = 0; i < nodes.size(); i ++) {
if (adjMatrix[nodes.indexOf(n)][i] == 1) {
neighbors.add(nodes.get(i));
}
Collections.sort(neighbors);
}
return neighbors;
}
// Helper methods for clearing visited property of node
private void reset() {
for (Node n : nodes)
n.visited = false;
}
// Helper methods for printing the node label
private void printNode(Node n) {
System.out.print(n.label + " ");
}
// BFS traversal (iterative version)
public void bfs() {
Queue<Node> queue = new LinkedList<Node>();
queue.add(rootNode);
while(!queue.isEmpty()) {
Node node = queue.poll();
printNode(node);
node.visited = true;
List<Node> neighbors = getNeighbors(node);
for ( int i = 0; i < neighbors.size(); i ++) {
Node n = neighbors.get(i);
if (n != null && n.visited != true) {
queue.add(n);
n.visited = true;
}
}
}
}
// DFS traversal (iterative version)
public void dfs() {
Stack<Node> stack = new Stack<Node>();
stack.add(rootNode);
while(!stack.isEmpty()){
Node node = stack.pop();
if(node.visited != true) {
printNode(node);
node.visited = true;
}
List<Node> neighbors = getNeighbors(node);
for (int i = 0; i < neighbors.size(); i++) {
Node n = neighbors.get(i);
if(n != null && n.visited != true) {
stack.add(n);
}
}
}
}
// DFS traversal (recursive version)
public void dfs(Node n) {
printNode(n);
n.visited = true;
List<Node> neighbors = getNeighbors(n);
for (int i = 0; i < neighbors.size(); i ++) {
Node node = neighbors.get(i);
if(node != null && node.visited != true) {
dfs(node);
}
}
}
// A simple Node class
static class Node implements Comparable<Node> {
public char label;
public boolean visited = false;
public Node(char label) {
this.label = label;
}
public int compareTo(Node node) {
return Character.compare(this.label, node.label);
}
}
// Test everything
public static void main(String[] args) {
Node n0 = new Node('A');
Node n1 = new Node('B');
Node n2 = new Node('C');
Node n3 = new Node('D');
Node n4 = new Node('E');
Node n5 = new Node('F');
Node n6 = new Node('G');
Node n7 = new Node('H');
Node n8 = new Node('I');
// Create the graph (by adding nodes and edges between nodes)
GraphM g = new GraphM();
g.addNode(n0);
g.addNode(n1);
g.addNode(n2);
g.addNode(n3);
g.addNode(n4);
g.addNode(n5);
g.addNode(n6);
g.addNode(n7);
g.addNode(n8);
g.connectNode(n0, n1);
g.connectNode(n0, n3);
g.connectNode(n0, n8);
g.connectNode(n1, n7);
g.connectNode(n2, n7);
g.connectNode(n2, n3);
g.connectNode(n3, n4);
g.connectNode(n4, n8);
g.connectNode(n5, n6);
g.connectNode(n5, n2);
// Perform the DFS and BFS traversal of the graph
for (Node n : g.nodes) {
g.setRootNode(n);
System.out.print("From node ");
g.printNode(n);
System.out.print("\nDFS (iterative): ");
g.dfs();
g.reset();
System.out.print("\nDFS (recursive): ");
g.dfs(g.getRootNode());
g.reset();
System.out.print("\nBFS (iterative): ");
g.bfs();
g.reset();
System.out.println("\n");
}
}
}
我建议将您的问题分解成更小的部分。
如果你想为无向图编写 class，请先编写并测试一下。
如果你想看看你是否可以实现遍历，首先要确保你的图能正常工作。您还可以使用 guava, which lets you use MutableGraph (and lots more). Here is how to install it in case you're using IntelliJ and here 是如何使用来自番石榴的图表。
另外记得使用调试器来找出您的代码是否出错。
所以，我们已经涵盖了你问题的第一部分，但我会在这里为后续的人重申一下。每当使用图形和邻接矩阵时，初始化数组中元素的最佳方法可能是 "both ways."
与其仅使用以下内容，还需要首先列出特定顶点才能找到邻居：
adjMatrix[nodes.indexOf(src)][nodes.indexOf(dst)] = 1;
使用这个，它会导致与顶点顺序无关的搜索：
adjMatrix[nodes.indexOf(src)][nodes.indexOf(dst)] = 1;
adjMatrix[nodes.indexOf(dst)][nodes.indexOf(src)] = 1;
现在，订购。您希望按照从 "least" 字母到 "greatest" 字母的顺序输出顶点。我们将单独处理您的每个数据结构。
在 BFS（迭代）中，您使用队列。队列是"first in, first out." 换句话说，每当您调用queue.poll() 时，最近最少添加到队列中的元素将首先输出。因此，您需要从最小到最大添加节点。
在 DFS（迭代）中，您使用堆栈。 Stacks是"last in, first out." 换句话说，当你调用stack.pop()时，最近添加到Stack中的元素将首先输出。因此，您需要从大到小添加节点。
在 DFS（递归）中，您使用列表。列表本身没有 "in-out" 排序，因为我们可以按我们想要的任何顺序轮询它们，但最简单的事情就是将列表从最小到最大排序并按顺序输出它们。
考虑到这一点，我们需要引入对图进行排序的协议。这三个协议都使用 getNeighbors()，因此我们将在调用该函数后立即对输出的列表进行排序。可以使用 java.utils.Collections 中的函数 Collections.sort(List l) 对列表进行排序，但我们首先需要修改您的节点 class，以便 Java 知道如何对节点进行排序。要进一步阅读我正在做的事情的详细信息，您可以查看 here，但是这个 post 比我预期的要长得多，所以我将在这里展示代码，让感兴趣的人自己去探索link。
您首先要通过实施 Comparable<Node> 并添加 compareTo() 函数来调整您的节点 class。
static class Node implements Comparable<Node>{
public char label;
public boolean visited = false;
public Node(char label) {
this.label = label;
}
@Override
public int compareTo(Node that) {
return Character.compare(this.label, that.label);
}
}
然后，如果我们想对List进行从小到大的排序，我们可以使用Collections.sort(neighbors)。当我们想要它从大到小时，我们可以使用Collections.sort(neighbors, Collections.reverseOrder())。我们的最终代码将如下所示：
// BFS traversal (iterative version)
public void bfs() {
Queue<Node> queue = new LinkedList<Node>();
queue.add(rootNode);
while(!queue.isEmpty()) {
Node node = queue.poll();
printNode(node);
node.visited = true;
List<Node> neighbors = getNeighbors(node);
//NEW CODE: Sort our neighbors List!
Collections.sort(neighbors);
for ( int i = 0; i < neighbors.size(); i ++) {
Node n = neighbors.get(i);
if (n != null && n.visited != true) {
queue.add(n);
n.visited = true;
}
}
}
}
// DFS traversal (iterative version)
public void dfs() {
Stack<Node> stack = new Stack<Node>();
stack.add(rootNode);
while(!stack.isEmpty()){
Node node = stack.pop();
if(node.visited != true) {
printNode(node);
node.visited = true;
}
List<Node> neighbors = getNeighbors(node);
//NEW CODE: Sort our neighbors List in reverse order!
Collections.sort(neighbors, Collections.reverseOrder());
for (int i = 0; i < neighbors.size(); i++) {
Node n = neighbors.get(i);
if(n != null && n.visited != true) {
stack.add(n);
}
}
}
}
// DFS traversal (recursive version)
public void dfs(Node n) {
printNode(n);
n.visited = true;
List<Node> neighbors = getNeighbors(n);
//NEW CODE: Sort our neighbors List!
Collections.sort(neighbors);
for (int i = 0; i < neighbors.size(); i ++) {
Node node = neighbors.get(i);
if(node != null && node.visited != true) {
dfs(node);
}
}
}