已知图的邻接矩阵,请用C语言编写函数对图以输入值为起点进行深度遍历和广度遍历
时间: 2024-05-06 13:19:22 浏览: 137
好的,我会根据您的要求回答您的问题。以下是对图进行深度遍历和广度遍历的 C 语言代码示例:
```c
#define MAX_VERTEX_NUM 100 // 图的最大顶点数
typedef int VertexType; // 顶点数据类型
typedef int EdgeType; // 边权值类型
// 定义邻接矩阵存储方式的图结构体
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点集合
EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int n, e; // 当前顶点数和边数
} MGraph;
// 以某个顶点 v 为起点进行深度遍历
void DFS(MGraph G, int v, int visited[]) {
visited[v] = 1; // 标记当前节点已访问
printf("%d ", G.vexs[v]); // 输出节点值
int i;
// 对未访问的邻节点进行递归访问
for (i = 0; i < G.n; i++) {
if (G.edges[v][i] != 0 && !visited[i]) {
DFS(G, i, visited);
}
}
}
// 以某个顶点 v 为起点进行广度遍历
void BFS(MGraph G, int v, int visited[]) {
visited[v] = 1; // 标记当前节点已访问
printf("%d ", G.vexs[v]); // 输出节点值
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
queue[rear++] = v; // 将当前节点入队
while (front != rear) { // 队列不为空时循环
int w = queue[front++]; // 取出队头节点
int i;
// 对未访问的邻节点进行访问,并将其入队
for (i = 0; i < G.n; i++) {
if (G.edges[w][i] != 0 && !visited[i]) {
visited[i] = 1;
printf("%d ", G.vexs[i]);
queue[rear++] = i;
}
}
}
}
// 对邻接矩阵存储的图进行深度优先遍历
void DFSTraverse(MGraph G) {
int visited[MAX_VERTEX_NUM] = {0}; // 标记所有节点未访问
int i;
// 对每个未访问过的节点进行深度优先遍历
for (i = 0; i < G.n; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
}
// 对邻接矩阵存储的图进行广度优先遍历
void BFSTraverse(MGraph G) {
int visited[MAX_VERTEX_NUM] = {0}; // 标记所有节点未访问
int i;
// 对每个未访问过的节点进行广度优先遍历
for (i = 0; i < G.n; i++) {
if (!visited[i]) {
BFS(G, i, visited);
}
}
}
```
注意:以上代码中省略了从输入读取邻接矩阵和顶点信息的部分,您需要根据具体输入方式进行相应修改。另外,对于大规模的图,深度遍历和广度遍历的时间和空间复杂度均为 O(n+m),其中 n、m 分别为顶点数和边数。如果需要处理巨大的图,还需要考虑使用其他更加高效的算法。
阅读全文