《实现primkruskaldijkstra和拓扑排序算法doc实现primkruskalDijkstra和拓扑排序算法doc》由会员分享，可在线阅读，更多相关《实现primkruskaldijkstra和拓扑排序算法doc实现primkruskalDijkstra和拓扑排序算法doc（30页珍藏版）》请在金锄头文库上搜索。
1、实现prim-kruskal-dijkstra和拓扑排序算法doc（实现prim kruskal Dijkstra和拓扑排序算法doc）Collected by oneselfMistakes are unavoidableFor reference onlyIn case of errorPlease correct me! Thank youSchool of computer and information, Fujian Agriculture And Forestry UniversityComputer classCourse design reportCourse name:da
2、ta structureCourse design topics:Algorithm implementation of Graphs(1) set up the information of the graph; 2) read the information of the drawing from the fileEstablish adjacency matrix and adjacency table; (3) to achieve Prim, Kruskal, Dijkstra and topological sorting algorithmFull name：Yixiangyan
3、gThe Department of:ComputerMajor:Computer science and Technology (upgraded Edition)Grade:07Student number:071806019Tutor:HuangsixianTitle：associate professor2008, 06, 28Catalog1. the purpose of curriculum design:.2. curriculum design requirements:.The idea of 3. algorithms describes.3.1, the constru
4、ction of the storage structure.3.2, Prim algorithm:.3.3, Kruskal algorithm:.3.4, Dijkstra algorithm:.3.5, topological sorting algorithm:.4. program structure:.5. test results:.6. summary:. And the following:.References:. And the following:.Appendix:.:.1., the purpose of curriculum designThe purpose
5、of this course design is based on the C languageThrough the completion of a number of difficult courses, design topics, writing, debugging, operationFurther understand and master the design methods of data structures and algorithmsHave initial independent analysis and design ability, master the basi
6、c methods and skills of software development process, such as problem analysis, system design, program coding, test and so on, and consolidate the theoretical knowledgeIntegrate theory with practiceTo improve the ability to analyze and solve problemsSoftware development with system view and general
7、specification of software developmentCultivate the scientific working methods and style of software workers, and train students ability to investigate and study technical documents, data, manuals and the preparation of technical documents2. curriculum design requirementsAlgorithm implementation of G
8、raphs(1) file the information of the graph;(2) read the information from the file into the diagramEstablish adjacency matrix and adjacency list;(3) implementing Prim, Kruskal, Dijkstra, and topological sorting algorithms3. algorithm descriptionThis procedure involves the establishment of the storage
9、 structure of the graph, Prim, Kruskal, Dijkstra and topological sorting algorithm3.1, storage structure is established:Read from the document to achieve the map informationAt the same time, we establish the directed adjacency matrix, undirected adjacency matrix, directed adjacency table and undirec
10、ted adjacency listFirstly, the initialization of adjacency matrix, adjacency table and undirected adjacency matrix and adjacency table are carried outWhen the directed adjacency matrix and the undirected adjacency matrix are initializedBecause you dont know how many vertices and edges you read intoS
11、o take the undirected adjacency matrixInitialize the character array of its vertex character to * so that you can easily determine where the vertex name is recordedThe degree of each edge is initialized to 9999, which means that the number of vertices and the number of edges are initially 0, and Gra
12、phKind is YOUXIANG, WUXIANG, respectivelyInitializes the adjacency table and the undirected adjacency tableVertex number, edge number, GraphKind initial method, ibid., all firstarc points to NULL, indicating that there is no edgeNextThe information that reads the edges into four graphsA function is
13、used to determine whether the vertices of the newly read edges appear in the previously read information, and if not, the name of the vertex is recordedUndirected graphs regard information as undirectedAdd two edges at a timeDirected graphs regard information as directedAdd only one edge at a timeAd
14、jacency matrix add edgeRight to fill in the corresponding location of a two-dimensional arrayAdjacent tables add edgesApply a AreNode dynamically and add the information behind the edgesInsert the corresponding position by head insertion3.2, Prim algorithm:The complete set of vertex in graph V, U ha
15、s been stored in the selected point, using the data structure of closedge storage selection needs data, the first subscript 0 corresponding points in U, closedgei.uxiabiao=0 (U, because only this one point subscript 0), closedgei.lowcost in the store he points to 0. The right, closedge0.lowcost=0 said; subscript 0 points have been made in UIn closedge, find the first point that is not in the U and is directl
