DFS與BFS的追蹤

圖一

• DFS(深度追蹤)

說明:

以圖一為例，當起點設為0時，會不斷往下深入，所以0會先向下追蹤分支的其中一個節點，再從該節點不斷向下
因此會深入到1 3直到底部，直到最底部7，此時會往上追蹤回4
當4上面的1被追蹤後，會回到底部7，7會再重另一個分支向上跑，直到每個節點都被追蹤過

程式碼:

void my_dfs(int index, head_p point[], int visited[]) {
  visited[index] = 1;
  stack[++top] = point[index];
  for (head_p w = point[index]; w; w = w->next) {
    if (w->num > 6 || w->num < 0) {
      break;
    }
    if (visited[w->num] != 1) {
      my_dfs(w->num, point, visited);
    }
  }
}

• BFS(廣度追蹤)

說明:

廣度追蹤會先追蹤完同一層節點，再向下追蹤下一層所有節點
因此當0為起點，會優先追蹤0的兩個分支1,2
若1,2節點追蹤完畢後，會分別追蹤分支1,2的兩個分支
直到節點追蹤完畢

程式碼:

void my_bfs(int num, head_p point[], int visited[]) {
  stack_new[++top_new] = point[num];
  visited[point[num]->num] = 1;
  while (point[num]->next) {
    if (visited[point[num]->num] == 0) {
      stack[++top] = point[num];
    }
    point[num] = point[num]->next;
  }
  for (int i = 0; i <= top; i++) {
    if (visited[stack[i]->num] == 0) {
      my_bfs(stack[i]->num, point, visited);
    }
  }
}