数据结构习题集（李冬梅 第2版）C语言版源程序习题源代码习题集-算法6-3

1、邻接矩阵存储带权无向图 #include using namespace std;定义最大顶点数 define MVNum 128 定义状态类型#define Status int函数结果状态代码/definedefine#define#define#defineOK 1ERROR 0 INFEASIBLE 0EXISTED 2Maxlnt 0 x7fffffff定义图的结构体类型typedef struct int vexs MVNum + 1 ;/顶点集因为顶点存储序号范围为1MVNumint arcs (MVNum + 1 MVNum + 1 ;/邻接矩阵int vexnum, arcn

2、um; /图当前的顶点数和边数)AMGraph;bool SMVNum + 1;int DMVNum + 1;int PathMVNum + 1;采用邻接矩阵表示法，创立无向图graphStatus createUDN(AMGraph Sgraph, int vexnum, int arcnum) graph, vexnutn = vexnurn; 初始化图的总顶点数graph, arcnum = arcnum;/初始化图的总边数if (graph.vexnum MVNum) return ERROR; /顶点数超过最大允许范围，返回错误代码。(注意数组下标从0开始) for (int i =

3、 0; i = graph.vexnum; i+) 依次输入顶点信息graph.vexsi = i;)for (int i 0; i - graph.vexnum; i + +) 初始化所有边的权值为0,表示边不存在for (int j = 0; j = graph.vexnum; j+) graph.arcsij = 0;)int vex one, vex two, weight;一条边依附的两个顶点 vex_one 和 vex_tw。for (int i = 0; i graph. arcnum; i+) 循环输入 arcnum 条边的信息cin vex_one vex_two weigh

4、t;graph.arcs vex_one vex_two = weight; 表权值为 1,表示边存在 graph.arcsvex_twovex_one = weight;return OK; /创立成功，返回成功代码。/定义打印无向图函数void printUDN(AMGraph graph)(for (int i = 0; i = graph.vexnum; i + + ) /在第一行打印顶点信息cout graph.vexsi ”cout endl;for (int i = 1; i = graph.vexnum; i+) /输出边的信息(每行第一个数字为顶点)(注意。号顶点不输出)co

5、ut graph.vexs i u/输出该行对应的顶点for (int j = 1; j = graph.vexnum; j+) 输出该行顶点对应所有边信息cout graph.arcsij ) cout endl;输出结束)用Dijkstra算法求图G中距离顶点vO的最短路径长度最大的一个顶点mint ShortestPathMAX(AMGraph G, int vO)( int n = G.vexnum;for (int v 1; v - n; v+) Sv - false;S初始为空集Dv = G.arcsvOv;if (Dv - 0) Dv Maxint;if (Dv Maxint)

6、Pathv = vO; else Pathv = -1;/end forSv0 = true;DvO - 0;int ShortestPathMAX(AMGraph G, int vO)( int n = G.vexnum;for (int v 1; v - n; v+) Sv - false;S初始为空集Dv = G.arcsvOv;if (Dv - 0) Dv Maxint;if (Dv Maxint) Pathv = vO; else Pathv = -1;/end forSv0 = true;DvO - 0;n为G中顶点的个数将vO到各个终点的最短路径长度初始化为弧上的权值如果vO和v

7、之间有弧，那么将v的前驱置为vO如果vO和v之间无弧,那么将v的前驱置为-1/将vO力口入S/源点到源点的距离为0/*初始化结束，开始主循环.每次求得vO到某个顶点v的最短路径,将v加到S集for (int i = 1; i n; i+) /对其余n-l个顶点，依次进行计算int min - Maxlnt, v;for (int w - 1; w - n; w+ + ) /选择一条当前的最短路径，终点为vif (!Sw & Dw min) v = w;min = Dw；)S v = true;for (int w - 1; w - n; w+) if (IS w & (Dv + G.arcs(

8、v w D(w ) /更新从v。出发到集合V-S上所有顶点的最短路径长度 Dw = Dv + G.arcs v w ;/更新 DwPathw = v;/更改w的前驱为v/ end if/ end for/end for/*最短路径求解完毕，设距离顶点vO的最短路径长度最大的一个顶点为m*/int Max - Dl;int m = 1;for (int i = 2; i = n; i+)if (Max Di)m = i;return m;/返回顶点下标int main() int n, m, w;cout ”请输入顶点的数量n和边的数量m (空格分隔，下同)：b;cin n m;/输入n和m的值AMGraph G;cout ”请依次输入m条边所依附的两端顶点以及边权重：n”； createUDN(G, n, m);打印图的信息printUDN(G);int v;cout 请输入开始顶点编号：bn;cin v;cout ShortestPathM