Depth First Search

Reference:

1. 演算法筆記: Rat in a Maze
2. 魔人日誌: [練習] graph走訪程式

Example_1: 遍歷所有的點

        0
      /   \
     1     2
      \   /
        3
        |
        4

#define GRAPH_MAX 5

bool graph[GRAPH_MAX][GRAPH_MAX] = {{0,1,1,0,0},        //初始化 圖形
                                    {1,0,0,1,0},
                                    {1,0,0,1,0},
                                    {0,1,1,0,1},
                                    {0,0,0,1,0}};

bool    bVisited[GRAPH_MAX]     = {false};              //初始化 訪問陣列,用來判斷點是否已走過 

void DFS(int v)
{
    int i;
    bVisited[v] = true;                                 //設點已被訪問過
    printf("%d ", v);                                   //印出被訪問的點
    for(i=0; i<GRAPH_MAX; i++)                          //訪問有關聯的點
        if(graph[v][i] && !bVisited[i])
            DFS(i);
}

int main(){
    DFS(0);                                             //從0開始遍歷整個GRAPH
    return 0;
}

output: 0 1 3 2 4

Example_2: 到達指定的點

        0
      /   \
     1     2
         /
        3
        |
        4

#define GRAPH_MAX 5

bool graph[GRAPH_MAX][GRAPH_MAX] = {{0,1,1,0,0},            
                                    {1,0,0,0,0},
                                    {1,0,0,1,0},
                                    {0,0,1,0,1},
                                    {0,0,0,1,0}};

bool    bVisited[GRAPH_MAX]     = {false};

bool DFS(int v, int target)
{
    int i;
    bVisited[v] = true;
    printf("enter %d\n", v);

    for(i=0; i<GRAPH_MAX; i++) {
        if(graph[v][i] && !bVisited[i] && !bVisited[target]) {
            if(!DFS(i, target))
                printf("enter again %d\n", v);
        }
    }

    if(!bVisited[target]) {
        printf("leave %d\n", v);
        return false;
    }

    return true;
}

int main(int argc, char* argv[])
{
    DFS(0,3);                               //從0開始,要到3

    return 0;
}

output: DFS(0,3)

enter: 0
enter: 1
leave: 1
enter again: 0
enter: 2
enter: 3

output: DFS(2,4)

enter: 2
enter: 0
enter: 1
leave: 1
enter again: 0
leave: 0
enter again: 2
enter: 3
enter: 4