[Algorithm] Graph traversal(DFS, BFS)

Traversal

• The process of visiting each node in a graph.
• How to visit all nodes once?
  • Depth-first search(DFS)
  • Breadth-first search(BFS)

 

Depth-First Search(DFS)

• Keep moving until there is no more possible block.
• Go back the previous step and move other unvisited block.
• Algorithm of DFS
  1. Visit the start vertex.
  2. Visit one of unvisited vertices neighboring to the start vertex.
  3. Repeat step 2 until there is no more unvisited vertex.
  4. If there is no more unvisited vertex, go back one step and visit another unvisited vertex.
• DFS is implemented with the stack.

void DFS(Graph* pgraph)
{
	Stack stack;
    bool* visited = (bool *)malloc(sizeof(bool)* pgraph->num);
    for (int i = 0; i < pgraph->num; i++)
   		visited[i] = false // Make all vertices unvisited.
        
    InitStack(&stack);
    Push(&stack, 0); // Push the initial vertex;
    while (!IsSEmpty(&stack){
    	GNode* cur;
        int vtx = SPeek(&stack);
        Pop(&stack);
        
        //skip if the vertex has been visited.
        if (visited[vtx]) continue;
        else{
        	visited[vtx] = true;
         	printf("%d ", vtx);
        }
        
        // Push the vertex if it has been unvisited.
        cur = pgraph->heads[vtx]->next;
        while (cur != NULL) {
        	if(!visited[cur->id])
            	Push(&stack, cur->id);
            cur = cur->next;
        }
    }
}

 

 

Breadth-First Search(BFS)

• Keep moving step-by-step for all possible blocks.
• Algorithm of BFS
  
  1. Visit the start vertex.
  2. Visit all unvisited vertices neighboring to the start vertex.
  3. Repeat step 2 until there is no more unvisited vertex.
• BFS is implemented with the queue.

void BFS(Graph* pgraph)
{
	Queue queue;
    bool* visited = (bool *)malloc(sizeof(bool)* pgraph->num);
    for (int i = 0; i < pgraph->num; i++)
    	visited[i] = false; // Make all vertices unvisited.
        
     InitQueue(&queue);
     EnQueue(&queue, 0); // Enqueue the initial vertex;
     while(!IsQEmpty(&queue)){
     	GNode* cur;
        int vtx = QPeek(&queue);
        DeQueue(&queue);
        
        // Skip if the vertex has been visited.
        if (visited[vtx]) continue;
        else {
        	visited[vtx] = true;
            printf("%d ", vtx);
        }
        
        // Enqueue the vertex if it has been unvisited.
        cur = pgraph->heads[vtx]->next;
        while (cur != NULL){
        	if(!visited[cur->id])
            	EnQueue(&queue, cur->id);
            cur = cur->next;
        }
     }
}