👋 Hi, I’m @Beast Cheng
👀 I’m interested in photography, hiking, landscape…
🌱 I’m currently learning python, javascript, kotlin…
📫 How to reach me --> 458290771@qq.com

---

喜歡《數據結構》部分筆記的小伙伴可以訂閱專欄，今后還會不斷更新。🧑?💻
感興趣的小伙伴可以點一下訂閱、收藏、關注！🚀
謝謝大家！🙏

回顧樹的先根遍歷

void PreOrder(TreeNode *R)
{if (R != NULL){visit(R);  // 訪問根結點while (R還有下一個子樹T)PreOder(T);  // 先根遍歷下一棵子樹}
}

圖的深度優先遍歷-代碼實現

bool visited[MAX_VERTEX_NUM];  // 訪問標記數組void DFS (Graph G, int v)  // 從頂點v出發，深度優先遍歷圖G
{visit(v);  // 訪問頂點vvisited[v] = TRUE;  // 設已訪問標記for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))if (!visited[w])  // w為v的尚未訪問的鄰接結點{DFS(G, w);}  // if
}

如果是非連通圖，則無法遍歷所有結點
解決方法類似：完成遍歷之后，可以再進行一次掃描，如果發現有結點仍然是false，那就說明與之對應的結點是沒有被訪問過的
也就是要加上如下代碼之后再進行深度優先遍歷

void DFSTraverse(Graph G)  // 對圖G進行深度優先遍歷
{for(v = 0; v < G.vexnum; ++v)visited[v] = FALSE;  // 初始化已訪問標記數據for(v = 0; v < G.vexnum; ++v)  // 本代碼中是從v=0開始遍歷if(!visited[v])DFS(G, v);
}

深度優先遍歷序列

同一個圖的鄰接矩陣表示方式唯一，因此深度深度優先遍歷序列唯一
同一個圖的鄰接表表示方式不唯一，因此深度優先遍歷序列不唯一

此外，還有深度優先生成樹、深度優先生成森林

圖的遍歷和圖的連通性

對無向圖進行BFS/DFS遍歷
調用BFS/DFS函數的次數 = 連通分量數

對于連通圖，只需要調用一次BFS/DFS

---

對有向圖進行BFS/DFS遍歷
調用BFS/DFS函數的次數要具體分析

如果起始頂點到其他各頂點都有路徑，則只需調用一次BFS/DFS函數

---

對于強連通圖，從任一結點出發都只需調用一次BFS/DFS