Можем ли мы делать графики bfs и dfs без раскраски?

Question

Я знаю, как делать DFS и BFS с узлом графа имеет некоторый атрибут, такой как цвет, так что в процессе DFS или BFS я могу определить, был ли узел посещен. Мне интересно, если мне дан график, а у узла графа нет цветового флага, как я могу сделать DFS или BFS?

спасибо!

Answer 1

Да, это возможно сделать ДФС без использования трех цветов, вы можете вместо этого сохранить логический атрибут в классе «Node», чтобы увидеть, если он был ранее посещенным или нет:

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 
    }