硕士算法2010_第5章_图的算法001讲解.ppt

算法设计与分析;第5章 图的算法;Graphs; 图4.-1 哥尼斯堡七桥问题;Definition: Directed graph;Definition: Undirected graph;Definitions: Weighted Graph;Graph Representations;Adjacency Matrix for weight digraph;Array of Adjacency Lists Representation;Array of Adjacency Lists Representation;More Definitions; ;; ;Bi-connected Components of an Undirected Graph;Bi-connected Components of an Undirected Graph;Bi-connected components, e.g.;Strongly Connected Components of a Digraph;Strongly Connected Components and Equivalence Relations;Condensation graph;Condensation graph and its strongly connected components; ;Breath-first search;Breath-first search, e.g.;宽度优先有哪些信誉好的足球投注网站算法;Breadth-first search: Algorithm;;Breadth-first search tree;时间复杂度分析;深度优先有哪些信誉好的足球投注网站算法;Depth-first search for Digraph;Depth-first search for digraph ;Depth-first search algorithm: outline;Depth-first search algorithm;算法DFS的时间复杂???;Depth-First Search on Undirected Graphs;Algorithm for depth-first search on undirected graph;边的分类;Depth-first search tree;;Topological Sort;早晨穿衣的过程;拓扑排序算法思想;Topological Sort;Queue-based Topological Sort;Graph Optimization Problems and Greedy Algorithms;Greedy Algorithms: Make the best choice;Optimization Problems;Minimum Spanning Tree;最小生成树问题 ;Minimum Spanning Tree Problem;Prim’s MST Algorithm;The Algorithm in action, e.g.;Prim’s MST Algorithm: Outline;Prim’s MST Algorithm: Implementation;Alternative Prim’s Algorithm Implementation;Properties of Minimum Spanning Trees;Properties of Minimum Spanning Trees …;Correctness of Prim’s MST Algorithm;最短路径问题;Problem: Single-Source Shortest Paths;Shortest-Path;Properties of Shortest Paths;Shortest Paths problems;Shortest Paths Definitions;Single Source Shortest Paths;e.g. Dijkstra’s Algorithm;Dijkstra’s Algorithm;Function minVertex ;Correctness of Dijkstra’s Shortest-Path Algorithm;第5章结束