iT邦幫忙

0

【資料結構】DFS與BFS的追蹤

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);
    }
  }
}


尚未有邦友留言

立即登入留言