C语言DFS 求无向连通图距离顶点v最远的顶点
时间: 2024-05-13 14:19:35 浏览: 7
对于无向连通图,可以从任意一个顶点开始,进行深度优先搜索(DFS)。在搜索的过程中,可以记录下当前搜索到的最远距离及其对应的顶点。当搜索完成后,最远距离对应的顶点就是距离v最远的顶点。
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAXN 1000
int n, m; // n为顶点数,m为边数
int head[MAXN], ver[MAXN], nxt[MAXN], tot = 0; // 邻接表存图
bool vis[MAXN]; // 标记数组,记录顶点是否被访问过
int farthest_vertex, farthest_dist; // 距离v最远的顶点及其距离
void add_edge(int x, int y) {
ver[++tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void dfs(int u, int dist) {
vis[u] = true;
if (dist > farthest_dist) { // 更新最远距离及其对应的顶点
farthest_dist = dist;
farthest_vertex = u;
}
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (!vis[v]) {
dfs(v, dist + 1);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int x, y;
scanf("%d%d", &x, &y);
add_edge(x, y); // 无向图
add_edge(y, x);
}
int v; // 起点v
scanf("%d", &v);
dfs(v, 0);
printf("距离v最远的顶点是%d,距离为%d\n", farthest_vertex, farthest_dist);
return 0;
}
```
其中,邻接表存图需要自行实现,这里不再赘述。在搜索的过程中,需要记录当前搜索到的距离及其对应的顶点。如果当前距离比已有的最远距离还要远,则更新最远距离及其对应的顶点。最后输出距离v最远的顶点及其距离即可。