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