深度和廣度遍歷是圖算法中最基本的兩種搜索方法。它們可以用來查找圖中的所有節點，從而對圖進行分析和處理。在PTA練習題中，圖的廣度和深度遍歷也是常見的考點。本文將介紹如何使用鄰接矩陣實現圖的廣度和深度遍歷，并提供相應的C語言代碼。
程序運行效果------------------------在本例中，我們將使用一個簡單的有向圖（包含5個節點和6條邊）進行練習。該圖的鄰接矩陣表示如下：```0 1 1 0 00 0 1 0 00
程序運行效果
------------------------
在本例中，我們將使用一個簡單的有向圖（包含5個節點和6條邊）進行練習。該圖的鄰接矩陣表示如下：
```
0 1 1 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
```
主函數（分段函數的創建）
------------------------
由于本例涉及到多個函數，我們需要先定義它們的函數原型。具體來說，我們需要定義以下函數：
- void createGraph(int graph[MAX_VERTEXES][MAX_VERTEXES], int * numVertexes)：創建圖
- void depthFirstSearch(int graph[MAX_VERTEXES][MAX_VERTEXES], int vertex, bool visited[MAX_VERTEXES])：深度遍歷圖
- void breadthFirstSearch(int graph[MAX_VERTEXES][MAX_VERTEXES], int vertex, bool visited[MAX_VERTEXES])：廣度遍歷圖
變量的聲明以及創建
------------------------
在主函數中，我們需要聲明一些變量，包括鄰接矩陣、頂點數和訪問標記等。具體來說，我們需要定義以下變量：
```
define MAX_VERTEXES 100 // 圖中最大頂點數
int graph[MAX_VERTEXES][MAX_VERTEXES]; // 鄰接矩陣
bool visited[MAX_VERTEXES]; // 訪問標記數組
int numVertexes; // 頂點數
```
圖的深度遍歷輸出函數
------------------------
深度遍歷是沿著圖的某一條分支遍歷到不能再繼續為止，然后回溯到前面的節點，嘗試走其他的路徑，直到所有的節點都被訪問為止。在C語言中，我們可以使用遞歸函數來實現深度遍歷。具體來說，我們可以定義一個名為depthFirstSearch()的函數來實現深度遍歷，并在其中使用遞歸來訪問每個未被訪問的節點。示例代碼如下：
```
void depthFirstSearch(int graph[MAX_VERTEXES][MAX_VERTEXES], int vertex, bool visited[MAX_VERTEXES]) {
visited[vertex] true;
printf("%d ", vertex);
for (int i 0; i < numVertexes; i ) {
if (graph[vertex][i] 1 visited[i] false) {
depthFirstSearch(graph, i, visited);
}
}
}
```
創建圖的函數
------------------------
在深度遍歷和廣度遍歷之前，我們必須先創建一個圖。創建圖的過程就是根據給定的鄰接矩陣來初始化我們的graph數組。具體來說，我們可以定義一個名為createGraph()的函數來實現圖的創建，并在其中通過scanf()函數從控制臺獲取輸入。示例代碼如下：
```
void createGraph(int graph[MAX_VERTEXES][MAX_VERTEXES], int * numVertexes) {
int numEdges;
scanf("%d %d", numVertexes, numEdges);
memset(graph, 0, sizeof(graph));
for (int i 0; i < numEdges; i ) {
int start, end;
scanf("%d %d", start, end);
graph[start][end] 1;
}
}
```
圖的廣度遍歷
------------------------
與深度遍歷不同，廣度遍歷是從圖的起始節點開始，依次訪問其子節點，再依次訪問這些子節點的子節點，直到所有的節點都被訪問為止。在C語言中，我們可以使用隊列來實現廣度遍歷。具體來說，我們可以定義一個名為breadthFirstSearch()的函數來實現廣度遍歷，并在其中使用隊列來存儲待訪問的節點。示例代碼如下：
```
void breadthFirstSearch(int graph[MAX_VERTEXES][MAX_VERTEXES], int vertex, bool visited[MAX_VERTEXES]) {
std::queue
visited[vertex] true;
printf("%d ", vertex);
q.push(vertex);
while (!q.empty()) {
int front ();
q.pop();
for (int i 0; i < numVertexes; i ) {
if (graph[front][i] 1 visited[i] false) {
visited[i] true;
printf("%d ", i);
q.push(i);
}
}
}
}
```
代碼下載地址
-------------------------
完整的C語言代碼可以從以下鏈接中下載：
提取碼：iyed
結論
-------------------------
在本文中，我們介紹了如何使用鄰接矩陣實現圖的深度和廣度遍歷，并提供了相應的C語言代碼。通過本文的學習，希望讀者能夠更加深入地理解圖的遍歷算法，并在實際應用中靈活運用。