深度和廣度遍歷是圖算法中最基本的兩種搜索方法。它們可以用來查找圖中的所有節點,從而對圖進行分析和處理。在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語言代碼。通過本文的學習,希望讀者能夠更加深入地理解圖的遍歷算法,并在實際應用中靈活運用。