数据结构实验六 图结构及其应用

}

// 对\顶点vs\自身进行初始化 flag[vs] = 1; dist[vs] = 0;

// 遍历G.vexnum-1次；每次找出一个顶点的最短路径。 for (i = 1; i < G.vexnum; i++) { }

// 打印dijkstra最短路径的结果

//printf(\ //for (i = 0; i < G.vexnum; i++)

// printf(\ Dispath(G, dist, prev, flag, vs); //输出最短路径

// 寻找当前最小的路径；

// 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。 min = INFINITY;

for (j = 0; j < G.vexnum; j++) { }

// 标记\顶点k\为已经获取到最短路径 flag[k] = 1;

// 修正当前最短路径和前驱顶点

// 即，当已经\顶点k的最短路径\之后，更新\未获取最短路径的顶点的最短路径和前驱顶for (j = 0; j < G.vexnum; j++) { }

tmp = (G.arcs[k][j] == INFINITY ? INFINITY : (min + G.arcs[k][j])); // 防止if (flag[j] == 0 && (tmp < dist[j])) { }

dist[j] = tmp; prev[j] = k;

if (flag[j] == 0 && dist[j] < min) { }

min = dist[j]; k = j;

点\。

溢出

}

int main() { }

// MGraph umg; //无权图

// createUMGraph(&umg); //创建无权图 // print(umg); MGraph mg;

createMGraph(&mg); print(mg); DFSTraverse(mg); BFSTraverse(mg); dijkstra(mg, 0); return 0;

【运行结果】

五、 实验心得体会

巩固了深度优先搜索、广度优先搜索和图的知识。