《数据结构的算法在C++中的应用》（英文版）Chapter 12 Graphs

Chapter 12 G raphs

Chapter 12 Graphs

Main topics Definition of graphs and some terminology Three common graph representations Some algorithms

Main topics • Definition of graphs and some terminology • Three common graph representations • Some algorithms

12.1 Definition and terminologies 1. Definition of graphs Graph=(v,e) V: nonempty finite vertice set E: edge set Undirected prapl oh If the tuple denoting an edge is unordered then (v1, v2)and(v2, vl)are the same edge

12.1 Definition and terminologies 1. Definition of graphs: Graph=(V, E) V: nonempty finite vertice set E: edge set • Undirected praph: If the tuple denoting an edge is unordered, then (v1,v2) and (v2,v1) are the same edge

12.1 Definition and terminologies oh Directed grap If the tuple denoting an edge is ordered. then (VI, v2)and(v2, v I)are different edges

12.1 Definition and terminologies • Directed graph: If the tuple denoting an edge is ordered, then (v1,v2) and (v2,v1) are different edges

12.1 Definition and terminologies Example V(G1)={V12V2V32V4} v3E(G1)={(V1,V2)V1V3),(V12V 4)(V2,3)(V2,V4)(V3,V4)} V(G2)={V1V2,V3} E(G2){V1V2>2<Ⅴ2V3}

12.1 Definition and terminologies • Example: V2 V4 V3 V1 V(G1 )={V1 ,V2 ,V3 ,V4} E(G1 )={(V1 ,V2 ),(V1 ,V3 ),(V1 ,V 4 ),(V2 ,V3 ),(V2 ,V4 ),(V3 ,V4 )} V1 V2 V(G2 )={V1 ,V2,,V3} E(G2 )={,,} V3

12.1 Definition and terminologies We will not discuss graphs of the following types

12.1 Definition and terminologies • We will not discuss graphs of the following types

12.1 Definition and terminologies 2. Complete graph In an undirected graph with n nodes, the number of edges <=n*(n-1)/2.If=is satisfied then it is called a complete undirect graph

12.1 Definition and terminologies 2.Complete graph In an undirected graph with n nodes, the number of edges <=n*(n-1)/2. If “=“ is satisfied, then it is called a complete undirect graph. V2 V4 V3 V1

12.1 Definition and terminologies In a directed graph with n nodes, the number of edges <=n (n-1).If=is satisfied, then it is called a complete directed graph

12.1 Definition and terminologies In a directed graph with n nodes, the number of edges <=n*(n-1). If “=“ is satisfied, then it is called a complete directed graph

12.1 Definition and terminologies 3.degree d, of vertex 1, TD(v) is the number of edges incident on vertex i In a directed grap h in-degree of vertex i is the number of edges incident to 1, ID(v) out-degree of vertex i is the number of edges from the 1, OD(v)

12.1 Definition and terminologies 3.degree di of vertex i, TD(v): is the number of edges incident on vertex i. In a directed graph : • in-degree of vertex i is the number of edges incident to i, ID(v). • out-degree of vertex i is the number of edges from the i, OD(v)

12. 1 Definition and terminologies TD(V=ID(V+OD(V) v3ID(v2)=1 OD(v2 =2 TD(v2)=3 Generally if there are n vertices and e edges in a graph, the en e=(XTD(vi))/2

12.1 Definition and terminologies • TD(v)=ID(v)+OD(v) Generally,if there are n vertices and e edges in a graph, then e=(TD(vi ))/2 v1 v2 v3 ID(v2 )=1 OD(v2 )=2 TD(v2 )=3 i=1 n