圖的DFS遍歷

• 首先我們需要知道什么是圖
  

• 簡單地說，圖就是由一些小圓點（稱為頂點）和連接這些小圓點的直線（稱為邊）組成的。例如上圖是由五個頂點（編號為1，2，3，4，5）和五條邊（1-2，1-3，1-5，2-4，3-5）組成。

• 接下來我將會展示從1號頂點以DFS算法遍歷這張圖的代碼。

• 每個頂點是第幾個被訪問到的，這個數字，稱為時間戳。（在本段代碼里沒有體現）

---

代碼實現

#include<stdio.h>
int book[2000], a[2000][2000];
int sum, n, m;void dfs(int cur)
{int i;printf("%d ", cur);sum++;if (sum == n)return;for (i = 1; i <= n; i++){if (a[cur][i] == 1 && book[i] == 0){book[i] = 1;dfs(i);}}return;
}int main()
{int i, j, m, x, y;scanf("%d %d", &n, &m);for (i = 1; i <= m; i++){scanf("%d %d", &x, &y);a[x][y] = 1;a[y][x] = 1;}book[1] = 1; //從第一個點出發dfs(1);return 0;
}

運行結果：

這張圖DFS遍歷順序為1 2 4 3 5

總結

以上是生活随笔為你收集整理的[C] 图的深度优先遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。