深度和廣度遍歷是圖算法中最基本的兩種搜索方法。它們可以用來查找圖中的所有節(jié)點(diǎn)，從而對圖進(jìn)行分析和處理。在PTA練習(xí)題中，圖的廣度和深度遍歷也是常見的考點(diǎn)。本文將介紹如何使用鄰接矩陣實(shí)現(xiàn)圖的廣度和深度遍歷，并提供相應(yīng)的C語言代碼。
程序運(yùn)行效果------------------------在本例中，我們將使用一個(gè)簡單的有向圖（包含5個(gè)節(jié)點(diǎn)和6條邊）進(jìn)行練習(xí)。該圖的鄰接矩陣表示如下：```0 1 1 0 00 0 1 0 00
程序運(yùn)行效果
------------------------
在本例中，我們將使用一個(gè)簡單的有向圖（包含5個(gè)節(jié)點(diǎn)和6條邊）進(jìn)行練習(xí)。該圖的鄰接矩陣表示如下：
```
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
```
主函數(shù)（分段函數(shù)的創(chuàng)建）
------------------------
由于本例涉及到多個(gè)函數(shù)，我們需要先定義它們的函數(shù)原型。具體來說，我們需要定義以下函數(shù)：
- void createGraph(int graph[MAX_VERTEXES][MAX_VERTEXES], int * numVertexes)：創(chuàng)建圖
- 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])：廣度遍歷圖
變量的聲明以及創(chuàng)建
------------------------
在主函數(shù)中，我們需要聲明一些變量，包括鄰接矩陣、頂點(diǎn)數(shù)和訪問標(biāo)記等。具體來說，我們需要定義以下變量：
```
define MAX_VERTEXES 100 // 圖中最大頂點(diǎn)數(shù)
int graph[MAX_VERTEXES][MAX_VERTEXES]; // 鄰接矩陣
bool visited[MAX_VERTEXES]; // 訪問標(biāo)記數(shù)組
int numVertexes; // 頂點(diǎn)數(shù)
```
圖的深度遍歷輸出函數(shù)
------------------------
深度遍歷是沿著圖的某一條分支遍歷到不能再繼續(xù)為止，然后回溯到前面的節(jié)點(diǎn)，嘗試走其他的路徑，直到所有的節(jié)點(diǎn)都被訪問為止。在C語言中，我們可以使用遞歸函數(shù)來實(shí)現(xiàn)深度遍歷。具體來說，我們可以定義一個(gè)名為depthFirstSearch()的函數(shù)來實(shí)現(xiàn)深度遍歷，并在其中使用遞歸來訪問每個(gè)未被訪問的節(jié)點(diǎn)。示例代碼如下：
```
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);
}
}
}
```
創(chuàng)建圖的函數(shù)
------------------------
在深度遍歷和廣度遍歷之前，我們必須先創(chuàng)建一個(gè)圖。創(chuàng)建圖的過程就是根據(jù)給定的鄰接矩陣來初始化我們的graph數(shù)組。具體來說，我們可以定義一個(gè)名為createGraph()的函數(shù)來實(shí)現(xiàn)圖的創(chuàng)建，并在其中通過scanf()函數(shù)從控制臺(tái)獲取輸入。示例代碼如下：
```
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;
}
}
```
圖的廣度遍歷
------------------------
與深度遍歷不同，廣度遍歷是從圖的起始節(jié)點(diǎn)開始，依次訪問其子節(jié)點(diǎn)，再依次訪問這些子節(jié)點(diǎn)的子節(jié)點(diǎn)，直到所有的節(jié)點(diǎn)都被訪問為止。在C語言中，我們可以使用隊(duì)列來實(shí)現(xiàn)廣度遍歷。具體來說，我們可以定義一個(gè)名為breadthFirstSearch()的函數(shù)來實(shí)現(xiàn)廣度遍歷，并在其中使用隊(duì)列來存儲(chǔ)待訪問的節(jié)點(diǎn)。示例代碼如下：
```
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
結(jié)論
-------------------------
在本文中，我們介紹了如何使用鄰接矩陣實(shí)現(xiàn)圖的深度和廣度遍歷，并提供了相應(yīng)的C語言代碼。通過本文的學(xué)習(xí)，希望讀者能夠更加深入地理解圖的遍歷算法，并在實(shí)際應(yīng)用中靈活運(yùn)用。