浙江大学数据结构MOOC-课后习题-第七讲-图4 哈利·波特的考试

题目汇总

浙江大学index.php/tags-301.html" >数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

代码展示

照着教程视频来的，没啥好说的捏

#include #include #define MAXSIZE 100#define IFINITY 65535typedef int vertex;typedef int weightType;/* 边 */struct ENode{vertex V1, V2;weightType weight;};typedef ENode* ptrToENode;typedef ptrToENode Edge;/* 图结点 */struct GNode{int Nv;/* 节点数 */int Ne;/* 边数 */weightType G[MAXSIZE][MAXSIZE];/* 邻接矩阵 */};typedef GNode* ptrToGNode;typedef ptrToGNode MGraph;MGraph creatGraph(){vertex V, W;MGraph G = (MGraph)malloc(sizeof(GNode));G->Ne = 0;std::cin >> G->Nv;for (V = 0; V Nv; V++){for (W = 0; W Nv; W++){G->G[V][W] = IFINITY;}}return G;}void insertEdge(MGraph Graph, Edge E){Graph->G[E->V1][E->V2] = E->weight;Graph->G[E->V2][E->V1] = E->weight;}MGraph buildGraph(){MGraph G = creatGraph();//插入边std::cin >> G->Ne;if (G->Ne != 0){Edge E = (Edge)malloc(sizeof(ENode));for (int i = 0; i Ne; i++){std::cin >> E->V1 >> E->V2 >> E->weight;E->V1--;E->V2--;insertEdge(G, E);}}return G;}void floyd(MGraph Graph, weightType D[][MAXSIZE]){vertex i, j, k;/* 初始化 */for (i = 0; i Nv; i++){for (j = 0; j Nv; j++){D[i][j] = Graph->G[i][j];}}for(k = 0; k Nv; k++){for (i = 0; i Nv; i++){for (j = 0; j Nv; j++){if ((D[i][k] + D[k][j]) Nv; j++){if (D[i][j] > maxDist && i != j)maxDist = D[i][j];}return maxDist;}void findAnimal(MGraph G){weightType D[MAXSIZE][MAXSIZE], maxDist, minDist;vertex animal, i;/* 利用Floyd求出任意两点间的最短路径长度 */floyd(G, D);/* 找出每行中的最大值， 然后从所有最大值中找出最小值 */minDist = IFINITY;for (i = 0; i Nv; i++){maxDist = findMaxDist(G, D, i);if (maxDist == IFINITY){std::cout minDist = maxDist;animal = i + 1;}}std::cout MGraph G = buildGraph();findAnimal(G);return 0;}