lecture1introduction(參考版)
2025-07-20 15:19本頁面
【正文】 2) Any other subgraph that contains it as a true subgraph is not connected. ? Any connected, undirected graph G = (V, E) satisfies that | E | ? | V | 1. (Hints: Adding each edge decreases of connected ponents by at most one) A directed graph is strongly connected if every two vertices are reachable from each other. ? Strongly connected ponent of a directed graph is a subgraph such that: 1) It is strongly connected。 ? Element of E: Edge。 ? 《 計(jì)算機(jī)算法導(dǎo)引 —設(shè)計(jì)與分析 》 ：盧開澄編著，清華大學(xué)出版社， 21元。 ? 《 圖算法 》 ：馬紹漢編著，山東大學(xué)出版社。Lecture 1. Introduction Haodi Feng Sch. of Comp. Sci. and Tech. Shandong University Email: Office: Rm430, Computing Center ? 2022SDU 2 Text Book amp。 Reference Books Text Book: ? Introduction to Algorithms (Second Edition) – Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein – Higher Education Press, The MIT Press, 68RMB Reference Books ? Algorithm Design Techniques and Analysis – . Alsuwaiyel (Saudi Arabia), 電子工業(yè)出版社， 40元。 ? 《 算法設(shè)計(jì)與分析 》 ：王曉東編著，清華大學(xué)出版社， 30元。 ? 2022SDU 3 Grading Scheme Total 100 ? Assignment 10% ? Final Examination: 90% ? 2022SDU 4 Contents Part I ? Explore techniques on a graph – Breadthfirst search algorithm (BFS) – Depthfirst search algorithm (DFS) ? Applications of DFS – Classifying edges (for directed or undirected) – Topological sort (for directed acyclic) – Strongly connected ponents deposing (for directed) – Biconnected ponents deposing (for undirected) ? 2022SDU 5 Contents (continued) Part II ? Minimum spanning tree problem (for undirected) – Kruskal’s algorithm – Prim’s algorithm ? Bottleneck spanning tree problem Part III ? Singlesource shortest paths problem (for directed) – BellmanFord algorithm – Dijkstra’s algorithm ? Allpairs shortest paths problem – Matrixmultiplication based algorithm – Floyd’s algorithm – Johnson’s algorithm ? 2022SDU 6 Contents (continued) Part IV ? Maximum flow problem (for work) – FordFulkerson algorithm – Dinic’s algorithm ? Applications of Maxflow problem – Maximum matching algorithm for Bipartite graphs Part V ? Maximum Matching ? 2022SDU 7 Prerequisite Data Structure C, Java or other programming languages A little mathematics ? 2022SDU 8 Graph Preliminary Knowledge In this class, try to answer three
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1