我们可以做图bfs和dfs而不着色吗？

Question

我知道如何做DFS和BFS与图形节点有一些像颜色一样的属性，以便在DFS或BFS的过程中，我可以告诉节点是否已访问过。 我想知道如果给我一个图并且图节点没有颜色标记，我该如何做DFS或BFS？

非常感谢！

Answer 1

是的，这是可以做到的DFS不使用三种颜色，可以改为保持在班上的“节点”一个布尔属性，看看它已经先前访问或不：

void DFS-Visit(Node current , int time){ 
     current.visited = true; 
     for (int i = 0 ; i < current.neighbor.length ; i++) 
      if (!current.neighbor[i].visited) 
       DFS-Visit(current.neighbor[i]); 
     System.out.println(current.key); 
     return; 
    } 
    void DFS(Node[] G){ 
     for (int i = 0 ; i < G.length; i++) 
      G[i].visited = false; 
     for (int i = 0 ; i < G.length; i++) 
      if (!G[i].visited) 
       DFS-Visit(G[i]); 
     return; 
    } 
    class Node{ 
    Node[] neighbor; 
    boolean visited; 
    int key; // content of the node , it might be anything 
    }