graph - 我们可以在不着色的情况下进行图形 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
  }