《算法课件Lecture1章节》由会员分享，可在线阅读，更多相关《算法课件Lecture1章节（40页珍藏版）》请在金锄头文库上搜索。
1、Design and Analysis of Algorithms,Sch. of Comp. Sci. and Tech. Shandong University, 2006SDU 2,Text Book & 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 Re
2、ference Books 图算法：马绍汉编著，山东大学出版社。 Algorithm Design Techniques and Analysis M.H. Alsuwaiyel (Saudi Arabia), 电子工业出版社，40元。 算法设计与分析：王晓东编著，清华大学出版社，30元。 计算机算法导引设计与分析：卢开澄编著，清华大学出版社，21元。 算法设计与分析：郑宗汉编著，清华大学出版社，32元。, 2006SDU 3,Grading Scheme,Total 100 Assignments and Attendance: 5% Project: 10% Final Examinati
3、on: 85% Caution: Please do not sign attendance for others Please do not copy others programs and assignment Otherwise, 0 mark will be given Please keep quiet in class, 2006SDU 4,Contents,Part I Explore techniques on a graph Breadth-first search algorithm (BFS) Depth-first search algorithm (DFS) Appl
4、ications of DFS Classifying edges (for directed or undirected) Topological sort (for directed acyclic) Strongly connected components decomposing (for directed) Bi-connected components decomposing (for undirected), 2006SDU 5,Contents (continued),Part II Minimum spanning tree problem (for undirected)
5、Kruskals algorithm Prims algorithm Bottleneck spanning tree problem Part III Single-source shortest paths problem (for directed) Bellman-Ford algorithm Dijkstras algorithm All-pairs shortest paths problem Matrix-multiplication based algorithm Floyds algorithm Johnsons algorithm, 2006SDU 6,Contents (
6、continued),Part IV Maximum flow problem (for network) Ford-Fulkerson algorithm Dinics algorithm Applications of Max-flow problem Maximum matching algorithm for Bipartite graphs Part V Uniquely decodable coding problem UDC algorithm Huffmans algorithm, 2006SDU 7,Why Study this Course?,Closely related
7、 to our lives Help to guide how others analyze and solve problems Help to develop the ability of analyzing and solving problems via computers Very interesting if you can concentrate on this course, 2006SDU 8,Prerequisite,Data Structure C, Java or other programming languages A little mathematics, 200
8、6SDU 9,Graph Preliminary Knowledge,In this class, try to answer three questions: What is a graph? How to represent a graph? Basic properties of a graph, 2006SDU 10,Graph Basics (Graph),A graph G is a pair (V, E), where V is a non-empty finite set and E is a set of pairs on V Denote as G = (V, E) Ele
9、ment of V: vertex; V: vertex set Element of E: edge(arc); E: edge set Undirected graph(u.w.a., graph): each pair in E is unordered, i.e., if (u, v) E, then (u,v) = (v, u). Directed graph: each pair in E is ordered, i.e., for (u, v) E, (u, v) (v, u) G1 = (1, 2, 3), (1, 2), (2, 3), (3,1) G2 = (1, 2, 3
10、), (, , ), 2006SDU 11,Schematic Representation,Can you give the representation in format G = (V, E) for above?, 2006SDU 12,Graph Basics (Adjacency),Adjacency: In a graph G = (V, E), if (u, v) E, say that vertex v is adjacent to vertex u. If G is an undirected graph, vertex u is adjacent to vertex v,
11、 too. The adjacency relation is symmetric. We also say (u,v) is incident with u and v, vice versa. If G is a directed graph, if (u, v) E, vertex v is adjacent to vertex u, usually, vertex u is not called to be adjacent to vertex v. Now, (u, v) is incident from or leaves vertex u and is incident to o
12、r enters vertex v. Two edges are called to be adjacent if they share a common vertex., 2006SDU 13,Graph Basics,Repeated edges: edges e and f have the same endpoints. （14） Self-loop: an edge from a vertex to itself. Simple graph: a graph without repeated edges and without self-loops, 2006SDU 14,Graph
13、 Basics (Degree),Degree of a vertex v: For undirected graph: Number of edges incident with v. Denote as dG(v) or simply, d(v). For directed graph: In-degree: number of edges entering (or incident to) v. Out-degree: number of edges leaving (or incident from) v. Denote as idG(v), odG(v) or simply, id(
14、v), od(v) respectively. Isolated vertex: a vertex whose degree is 0. Endpoint of a graph: a vertex with degree 1., 2006SDU 15,Graph Properties,Theorem 1.1 (Handshaking Lemma) Given an undirected graph G = (V, E), the sum of degrees of all vertices is that , where | E | is the number of edges in G. Proof: can you give? How about a directed graph? (sum of in-degrees equals to sum of out-degress, i.e., the number or arcs) Corollary 1.2 Given a graph G = (V, E), the number of vertices with odd degrees is even. Proof: can you give?, 2006
