深度和广度遍历是图算法中最基本的两种搜索方法。它们可以用来查找图中的所有节点，从而对图进行分析和处理。在PTA练习题中，图的广度和深度遍历也是常见的考点。本文将介绍如何使用邻接矩阵实现图的广度和深度遍历，并提供相应的C语言代码。
程序运行效果
------------------------
在本例中，我们将使用一个简单的有向图（包含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语言代码。通过本文的学习，希望读者能够更加深入地理解图的遍历算法，并在实际应用中灵活运用。
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
