#include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <math.h> #define MAXN 1010 int iMaxLength = 0;//最长路径长度 int iCurrentLength = 0;//当前路径长度 typedef int ElemType; ElemType stMax_Path[MAXN];//最长路径元素 ElemTyp stCurrent_Path[MAXN];//当前路径元素 bool DFS(BiTree root){ //程序健壮性检查：是否为空树 if( root == NULL ) return false; //根节点加入路径 stCurrent_Path[iCurrentLength++] = root->data; //访问到叶子节点 if( root->lchild == NULL && root->rchild == NULL ) { if( iCurrentLength > iMaxLenngth ){ iMaxLength = iCurrentLength;//更新最大路径长度 //同时更新最大路径数组： for(int iPos = 0; iPos < iCurrentLength; iPos++){ stMax_Path[iPos] = stCurrent_Path[iPos]; } } }else{ DFS(root->lchild);//递归遍历左子树 DFS(root->rchild);//递归遍历右子树 } iCurrentLength--;//回溯，从路径数组中移出当前节点 return true; } //一个打印函数，相当于main.c测试函数 bool Search_Longest_Path(BiTree T){ //声明变量时，已初始化 DFS(T);//递归查找最长路径 if (iMaxLength = = 0) printf("Not Found Longest Path.\n"); else{ //输出最长路径、最长路径长度 printf("Longest Path is:"); for(int iPos = 0; iPos < iMaxLength; iPos++){ printf("%d",stMax_Path[iPos]); } printf("\n"); printf("Longest Path Length is: %d\n", iMaxLength ); } return true; };算法设计题：
从根节点到叶子节点的最大距离称为树的半径。给定一个无向连通图，写一个算法找出半径最小的生成树。
最小生成树MST:
最小生成树的题目。下面介绍两个求MST的经典算法：
1.Prim算法。思路：添加点位，想象有两个集合：/*S*/存放已经选入MST的顶点集合；/*V-S*/存放未被选择的顶点集合。
2.Kruskal算法。加边法，适用于稀疏图，时间复杂度为O（E logE）。
题干中的无向连通图并未给出权值，所求的半径最小的生成树，并非课本所学的最小生成树。重新梳理图章节中的算法列表：
1.Prim&Kruskal算法的C语言实现与DFS/BFS并无关联；
2.DFS/BFS算法不考虑边权值，仅仅实现图的遍历；
【思考题】邻接表实现的Prim与Dijkstra几乎一模一样？
3.Dijsktra:dist[u]是源点到U的最短路径长度，但是叶子节点并不指定。切换Floyd也不解决问题，二者均为指定目标点位的路径规划算法。
【逆向思考】图不太可能考察MST代码实现、AOE网的代码实现、Dijkstra&Floyd的代码实现，上述代码实现过于复杂，不具备筛选性质。仅仅考察手动模拟。那么有限考察点：BFS遍历、DFS遍历、多源BFS最短路、拓扑排序就都成了重点。
重新梳理题目Msg：
找到一个顶点V，使得点V到最远点的最短距离尽可能小，这个最小的最大值即最小半径。
引入两个概念：
偏心距e<v>：以v为起点，到所有其它点的最短路径的最大值。
图的半径rad(G)：图的偏心距集合，最小值。
STEP1：求图的任意一点的生成树半径；
STEP2：比对所有点的生成树半径，排序求最小值。
一次简单选择排序，便能实现STEP2，套上遍历的壳子使用STEP1方法。
方案一:Floyd-Warshall（适合n很小，稠密图）
运行Floyd，算出逆向全部点对的最长距离d[i][j]，O（n^3）,添加叶子节点判定。
方案二：多次Dijkstra（正权图、稀疏图，效率更好O(n(m+n logn))）
多次单源最短路实现，等价于多源最短路实现。
一次总结：
Prim/Kruskal: 最小生成树MST，总边权和最小
Dijkstra/Floyd/BFS: 最短路径，两点之间的距离最小
DFS/BFS遍历，逆向Floyd加上叶子节点判定，可行。Dijkstra实现过于复杂，不可取。
【思考】最短路算法可以解决最小半径生成树问题，那么BFS如何使用呢，时间复杂度和手写难度是否能中和Floyd（时间复杂度较大）与Dijkstra（实现难度较高）呢？
- 🟢无权无向连通图：
生成树 → DFS / BFS；MST无定义，别上Prim/Kruskal
点到点最短路径 → BFS！（DFS不能求最短！）
- 🟢带权无向连通图：
MST → Prim / Kruskal；权正负都可以！
最短路：正权→Dijkstra；有负权→Floyd/SPFA
- 🟢有向图：
没有MST！不要用Prim/Kruskal！求最短路用 Dijkstra(正权) / SPFA / Floyd。
📋怎么选方案（快速决策表）
1. 无权连通图（边权恒为1）→ 多次BFS
2. 正权连通图，n很小（n≤200）→ Floyd（代码省事）
3. 正权连通图，稀疏图、n比较大 → 多次堆优化Dijkstra
4. 有负权边，无负环，n小 → Floyd
5. 有负权边，无负环，n大稀疏图 → 多次SPFA（不推荐，不稳定）
6. 确认是树（无环）→ 叶子剥离法，速度最快
哇，这个问题非常有意思，而且很容易和之前“图的半径”搞混！它有专门名字：
📌 最小半径生成树 MRST (Minimum Radius Spanning Tree)
问题完整定义：
给定无向连通带权图 G，找出它的一棵生成树 T（包含全部n个顶点、n‑1条边、连通、无环）；
树T的半径 rad(T)：树里根到叶子最大距离的最小值（树的中心的偏心距）；
目标：选出所有可能生成树当中 rad(T) 尽可能小的那一棵！
- 最小直径生成树 MDST（Minimum Diameter Spanning Tree）：生成树的直径最小（最远叶子对距离最小）。它和MRST非常接近，但不完全一样！
直径 = max偏心距；半径 = min偏心距。
对于树，如果直径D，半径r满足 r=\lceil D/2\rceil。所以MDST和MRST最优解往往是同一棵树，但定义不一样！MDST有一个经典的绝对中心（图的1‑中心）算法，稍微复杂一些。
总结：
原来离心率是一个整体的概念，图的定理应用。此题难度爆炸💥舍弃。
