一道数据结构题

Question

请问，这个算法，可以有人给我顺一遍吗，有些地方看不懂，求说明，谢谢啦

• 

•  

• 

•  

• 

• 
  

• 
  

Answer 1

1)要实现的算法①建立图的存储结构②深度优先搜索和广度优先搜索③求图的最小生成树④拓扑排序⑤最短路径2)存储结构设计　　本系统采用图结构（mgraph）存储抽象操作的信息。其中，各结点间的邻接关系用图的邻接矩阵类型（adjmatrix）存储。顶点信息用结构数组（vexs）存储。其中每个数据元素师一个结构变量，包括一些基本信息。此外，本系统还设置了三个全局变量：visited[]数组用于存储顶点是否被访问标记；d[]用于存放边上的权值或者是存储查找路径顶点的编号；campus是一个图结构的全局变量3)功能设计　　本程序一共设置了9个子功能菜单，图的初始化由函数initgraph（）实现，依据读入的图的顶点个数和边的个数。分别初始化图结构中图的顶点向量数组和图的邻接矩阵。9个功能设计描述如下：①建立有向图。有向图的建立有由BuildAdjacencyList()实现。当用户选择该功能时，用户要手动输入该图的信息。从而建立有向图。②输出邻接表。邻接表的输出有函数ShowAdjacencyList()实现。当用户选择该项功能时，系统即以邻接表的形式输出各顶点所连接的点。③输出顶点的度。顶点读的输出由函数ShowAdjacencyListDegree()实现。当用户选择该功能时，系统即将每个顶点的度以数字的形式输出。④进行拓扑排序。拓扑排序功能的实现由函数TopologicalSortAdjacencyList()完成。一旦选择，就会进行排序并输出。⑤深度优先遍历。采用DFS算法进行深度优先遍历，遍历完成后，将遍历得到的结点有序输出。⑥广度优先遍历。采用BFS算法进行广度优先遍历，遍历完成后，将遍历得到的结点有序输出。⑦无向图最小生成树。最小生成树的算法实现由函数AdjacencyListPrim()完成。该函数采用Prim算法对邻接矩阵求最小生成树并输出。⑧有向图求最短路径。最短路径的实现采用函数AdjacencyListDijkstra()完成。该函数采用的是Dijkstra 算法对邻接矩阵对各顶点到其他顶点的最短距离。并依次输出。