FB1-求无向连通图中距离顶点v最远的结点
[[#计算无向连通图的直径（任意两点间最短路径的最大值）]]
代码实现
求无向连通图中距离顶点v最远的结点
| C |
|---|
| /**
* 求无向连通图中距离顶点v最远的结点
*
* 算法思想：
* 利用BFS的层次遍历特性，最后被访问的节点就是距离起始节点最远的节点
*
* 理论依据：
* 1. BFS按层次遍历，先访问距离为1的节点，再访问距离为2的节点...
* 2. 最后一个出队的节点一定是距离起始节点最远的节点
* 3. 这是因为BFS保证了按最短路径距离的顺序访问节点
*
* 应用场景：
* - 网络中最远的服务器
* - 社交网络中关系最远的人
* - 树的直径计算（需要两次BFS）
*/
int findFarthestNode(Graph G, int v) {
// 访问标记数组，防止重复访问节点
int visit[maxsize] = {0};
// 循环队列，用于BFS层次遍历
int que[maxsize];
int front = 0, rear = 0;
// 标记起始节点v为已访问
visit[v] = 1;
// 将起始节点入队
que[++rear] = v;
// 用于记录最后访问的节点
int lastVisited = v;
// BFS遍历所有可达节点
while (front != rear) {
// 出队操作：获取队首节点
v = que[++front];
// 更新最后访问的节点
lastVisited = v;
// 遍历当前节点的所有邻接节点
Node p = G.adjlist[v].firstarc;
for (; p != NULL; p = p->nextarc) {
// 如果邻接节点未被访问
if (visit[p->adjvex] == 0) {
// 标记为已访问
visit[p->adjvex] = 1;
// 将邻接节点入队
que[++rear] = p->adjvex;
}
}
}
// 返回最后访问的节点，即距离起始节点最远的节点
return lastVisited;
}
|
计算无向连通图的直径（任意两点间最短路径的最大值）
计算两点间最短距离（使用BFS）
| C |
|---|
| /**
* 计算无向连通图的直径（任意两点间最短路径的最大值）
*
* 算法思想：
* 1. 从任意节点开始，使用BFS找到距离它最远的节点u
* 2. 从节点u开始，再次使用BFS找到距离u最远的节点v
* 3. u到v的距离就是图的直径
*
* 理论依据：
* 这是基于树的直径算法，对于连通图同样适用
*/
int calculateGraphDiameter(Graph G) {
// 第一次BFS：从节点0开始找到最远节点
int farthestNode1 = findFarthestNode(G, 0);
// 第二次BFS：从第一次找到的最远节点开始，找到真正的最远节点
int farthestNode2 = findFarthestNode(G, farthestNode1);
// 第三次BFS：计算两个最远节点间的距离
return getDistance(G, farthestNode1, farthestNode2);
}
/**
* 函数：getDistance
* 功能：使用广度优先搜索（BFS）算法计算无向/有向无权图中两个顶点之间的最短路径长度（边数）
* 参数：
* G : 图的邻接表表示
* start : 起始顶点编号
* end : 目标顶点编号
* 返回值：
* 若存在路径，返回从 start 到 end 的最短距离（边数）
* 若不可达，返回 -1（虽然题目假设图连通，但仍保留健壮性处理）
*
* 注意：本算法适用于无权图。若为有权图，应使用 Dijkstra 或 Bellman-Ford 等算法。
*/
int getDistance(Graph G, int start, int end) {
// 特殊情况：起点和终点相同，距离为0
if (start == end) return 0;
// 访问标记数组，visit[i] == 1 表示顶点 i 已被访问
int visit[maxsize] = {0};
// 循环队列，用于实现 BFS 的层次遍历
int que[maxsize];
int front = 0, rear = 0; // 队首和队尾指针（初始为空）
// 距离数组，distance[i] 表示从 start 到顶点 i 的最短距离
int distance[maxsize] = {0};
// 标记起始节点为已访问，并入队
visit[start] = 1;
que[++rear] = start; // 入队操作：先移动 rear 再赋值（1-indexed 风格）
// 当队列非空时持续进行 BFS
while (front != rear) {
// 出队一个顶点
int current = que[++front]; // 先移动 front 再取值
// 如果当前顶点就是目标顶点，直接返回其距离
if (current == end) {
return distance[current];
}
// 遍历当前顶点的所有邻接点（通过邻接表）
Node p = G.adjlist[current].firstarc;
while (p != NULL) {
int neighbor = p->adjvex; // 获取邻接顶点编号
// 若该邻接点未被访问，则进行处理
if (visit[neighbor] == 0) {
visit[neighbor] = 1; // 标记为已访问（避免重复入队）
// 距离 = 当前节点距离 + 1（无权图的边权为1）
distance[neighbor] = distance[current] + 1;
// 将邻接点入队，等待后续扩展
que[++rear] = neighbor;
}
p = p->nextarc; // 移动到下一个邻接边
}
}
// 若 BFS 结束仍未找到目标节点，说明不可达
return -1;
}
|
复杂度分析
时间复杂度：O(V + E)
- V: 顶点数，E: 边数
- 每个顶点最多入队和出队一次：O(V)
- 每条边最多被检查一次：O(E)
- 总时间复杂度：O(V + E)
空间复杂度：O(V)
visit[]数组：O(V)que[]队列：O(V)distance[]数组（在距离计算中使用）：O(V)- 总空间复杂度：O(V)
图解说明
| Text Only |
|---|
| 示例图结构：
1
/ \
0 3
\ / \
2 4
/
5
从节点0开始找最远节点的BFS过程：
第1层（距离0）：[0]
访问顺序：0
队列状态：[0] → []
第2层（距离1）：[1, 2]
访问顺序：0 → 1 → 2
队列状态：[1,2] → [2] → []
第3层（距离2）：[3]
访问顺序：0 → 1 → 2 → 3
队列状态：[3] → []
第4层（距离3）：[4]
访问顺序：0 → 1 → 2 → 3 → 4
队列状态：[4] → []
第5层（距离4）：[5]
访问顺序：0 → 1 → 2 → 3 → 4 → 5
队列状态：[5] → []
最后访问的节点是5，它就是距离节点0最远的节点
距离为4（路径：0→1→3→4→5 或 0→2→3→4→5）
图的直径计算过程：
1. 从节点0开始BFS → 最远节点是5
2. 从节点5开始BFS → 最远节点可能是0或1或2
3. 计算5到最远节点的距离 → 图的直径
|
相关知识点延伸
1. 树的直径算法
| C |
|---|
| // 树的直径：两次BFS算法
int treeDiameter(Graph tree) {
// 第一次BFS找最远点
int farthest1 = findFarthestNode(tree, 0);
// 第二次BFS找真正的最远点
int farthest2 = findFarthestNode(tree, farthest1);
// 计算距离
return getDistance(tree, farthest1, farthest2);
}
|
2. 多源BFS优化
| C |
|---|
| // 同时从多个节点开始的BFS
void multiSourceBFS(Graph G, int sources[], int sourceCount) {
int visit[maxsize] = {0};
int que[maxsize];
int front = 0, rear = 0;
// 所有源节点同时入队
for (int i = 0; i < sourceCount; i++) {
visit[sources[i]] = 1;
que[++rear] = sources[i];
}
// 同时进行BFS扩展
while (front != rear) {
int current = que[++front];
printf("访问节点: %d\n", current);
Node p = G.adjlist[current].firstarc;
for (; p != NULL; p = p->nextarc) {
if (visit[p->adjvex] == 0) {
visit[p->adjvex] = 1;
que[++rear] = p->adjvex;
}
}
}
}
|
3. 应用场景扩展
| C |
|---|
| // 网络中的关键节点识别
int findCriticalNode(Graph G) {
int maxDistance = -1;
int criticalNode = 0;
// 对每个节点计算其到最远节点的距离
for (int i = 0; i < G.numver; i++) {
int farthest = findFarthestNode(G, i);
int distance = getDistance(G, i, farthest);
if (distance > maxDistance) {
maxDistance = distance;
criticalNode = i;
}
}
return criticalNode;
}
|
4. 最小生成树中的应用
在最小生成树中，直径的计算对于网络设计非常重要：
- 通信网络：最小化最大延迟
- 交通网络：最小化最远站点间的旅行时间
- 分布式系统：最小化节点间最大通信跳数
5. 算法正确性证明要点
- BFS的层次性：保证按距离递增顺序访问节点
- 连通性保证：无向连通图确保所有节点可达
- 最优性：BFS保证找到的是最短路径距离
- 终止性：有限图确保算法在有限步内终止
这个算法是图论中基础而重要的应用，体现了BFS在求解最短路径相关问题中的强大能力。