天津大学：《数据结构 Data Structures》课程PPT教学课件（英文版）Chapter 6 Graph Algorithms

chapter 9 GRAPH ALGORITHMS $1 Definitions D G(V, E) where G: graph, V=V(G): =finite nonempty set of vertices, ande=E(G): =finite set of edges y Undirected graph: (v, vi)=(, vi): :=the same edge o Directed graph(digraph): ::Q*<vi tailhead v Restrictions (1)Self loop is illegaL. ①①0 (2)Multigraph is not considered (5=2 y' Complete graph: a graph that has the maximum number ofedges V=n=Q年‖#oV=n→ Qr #of E=C2=n(n-d) f of e= p n(n-1)

CHAPTER 9 GRAPH ALGORITHMS §1 Definitions  G( V, E ) where G ::= graph, V = V( G ) ::= finite nonempty set of vertices, and E = E( G ) ::= finite set of edges.  Undirected graph: ( vi , vj ) = ( vj , vi ) ::= the same edge.  Directed graph (digraph): ::=  tail head  Restrictions : (1) Self loop is illegal. (2) Multigraph is not considered 0 1 0 1 2  Complete graph: a graph that has the maximum number of edges 0 2 1 3 2 2 ( 1) # of E # of V − = = =  n n Cn n 0 2 1 3 # of E ( 1) # of V 2 = = − =  P n n n n

v, and v; are adjacent (Vis vi)is incident on v and vj vi is adjacent to v;; v, is adjacent from is incident on v; and vi Subgraph g’cG:=W(G)sV(G)&&E(G’)E(G) y Path(cG) from vn to va: = vo, Vil, Vi2,.,Vn, va) such that(vo, Vi), ( Vils Vi), ,(Vin, q)or,", Vins Vq> belong to E(G) D Length of a path number of edges on the path y Simple path =Vil, Vi,.., Vin are distinct y Cycle : =simple path with p=va e v; and vj in an undirected G are connected if there is a path from v: to vi (and hence there is also a path from v, to vi) y An undirected graph G is connected if every pair of distinct v; and v,are connected

 vi vj vi and vj are adjacent; ( vi , vj ) is incident on vi and vj vi v  j vi is adjacentto vj ; vj is adjacentfrom vi ; is incident on vi and vj  Subgraph G’  G ::= V( G’ )  V( G ) && E( G’ )  E( G )  Path ( G) from vp to vq ::= { vp , vi1 , vi2 , , vin, vq } such that ( vp , vi1 ), ( vi1 , vi2 ), , ( vin, vq ) or , , belong to E( G )  Length of a path ::= number of edges on the path  Simple path ::= vi1 , vi2 , , vin are distinct  Cycle ::= simple path with vp = vq  vi and vj in an undirected G are connected if there is a path from vi to vj (and hence there is also a path from vj to vi )  An undirected graph G is connected if every pair of distinct vi and vj are connected

/'(Connected) Component of an undirected G: = the maximal connected subgraph D' A tree: :=a graph that is connected and acyclic D ADAG: :=a directed acyclic graph y' Strongly connected directed graph G: =for every pair of vi and v, in V(G), there exist directed paths from v, to v, and from v; to v;. If the graph is connected without direction to the edges, then it is said to be weakly connected y Strongly connected component: the maximal subgraph that is strongly connected y Degree(v): : =number of edges incident to v. For a directed G, we have in-degree and out-degree. For example: in-degree(v)=3; out-degree(v)=l; degree(v)=4 y Given G with n vertices and e edges, then e=∑a/ where d,=cgre(n)

 (Connected) Component of an undirected G ::= the maximal connected subgraph  A tree ::= a graph that is connected and acyclic  Strongly connected directed graph G ::= for every pair of vi and vj in V( G ), there exist directed paths from vi to vj and from vj to vi . If the graph is connected without direction to the edges, then it is said to be weakly connected  Strongly connected component ::= the maximal subgraph that is strongly connected  Degree( v ) ::= number of edges incident to v. For a directed G, we have in-degree and out-degree. For example: v in-degree(v) = 3; out-degree(v) = 1; degree(v) = 4  Given G with n vertices and e edges, then 2 where degree( ) 1 0 i i n i i e d  d = v      =  − =  A DAG ::= a directed acyclic graph

82 The structure of graph's storage Adjacency Matrix To describe the Adjacency matrix of the graph, we need a table to record the information of each vertex and an Adjacency Matrix contains the relations among each vertex。 Suppose thata=(v, E)is a graphg includes n vertex, the graphs Adjacency Matrix is a two dimensional array A. edgenn. A Edgell ∫1,if∈Eor(j∈E 0 else

◼ To describe the Adjacency Matrix of the graph, we need a table to record the information of each vertex and an Adjacency Matrix contains the relations among each vertex. ◼ Suppose that A = (V, E) is a graphg includes n vertex, the graph’s Adjacency Matrix is a two dimensional array A.edge[n][n] ： Adjacency Matrix      = , else , if , ( , ) . [ ][ ] o r 0 1 A i j E i j E Edge i j §2 The structure of graph’s storage

0 ①2 A edge 0101 1010 301 010 Aedge=10 1 000 2 The adjacency matrix of non-directional graph is symmetrical The adjacency matrix of directional graph is not always symmetrical

◼ The adjacency matrix of non-directional graph is symmetrical ◼ The adjacency matrix of directional graph is not always symmetrical 0 1 2 3           = 1 0 1 0 0 1 0 1 1 0 1 0 0 1 0 1 A.edge 0 1 2         = 0 0 0 1 0 1 0 1 0 A.edge

Among the directed graph, compute the number of l on line i, can get the vertex is outdegree. Compute the number of l on row i, can get the vertex i's indegree As for the undirected graph, Compute the number of l on row i, can get the vertex is degree

◼ Among the directed graph, compute the number of 1 on line i, can get the vertex i’s outdegree. Compute the number of 1 on row i, can get the vertex i’s indegree. ◼ As for the undirected graph, Compute the number of 1 on row i, can get the vertex i’s degree

Adjacency Matrix in the network w(i,j),ifi≠jand∈Eor(,j)∈E Aedge证={∞ ifi≠jand函Eor(ij)E ifi==j 8 (2 3 6 01∞4 o092 39 52 Aeage 3508 60 0 1 (

1 8 6 3 9 2 5 4 2 0 3 1               = 6 0 3 5 0 8 0 9 2 0 1 4 A.edge Adjacency Matrix in the network      ==          = i j i j i , j i , j i j i j i , j i , j i j i f i f and o r i f and o r , , ( ) ( , ), ( ) [ ][ ] 0 E E W E E A.edge

using Adjacency Matrix to define the graph # define maxvalue Int Max//在中 const int NumEdges =50 //edges' number const int NumVertices= 10://vertex's number typedef char Vertex Data; //vertex's data type typedef int Edge Data; // Edge's weight typedef struct t Vertex Data vexList[NumVertices]://vertex table Edge Data Edge [Num][Num Vertices]: //adjacency can be treat as the edge relation Int n, e://the number of the vertex and edge 1 MTGraph;

#define MaxValue Int_Max //在中 const int NumEdges = 50; //edges’ number const int NumVertices = 10; // vertex’s number typedef char VertexData; // vertex’s data type typedef int EdgeData; // Edge’s weight typedef struct { VertexData vexList[NumVertices]; //vertex table EdgeData Edge[NumVertices][NumVertices]; //adjacency can be treat as the edge’ relation int n, e; //the number of the vertex and edge } MTGraph; using Adjacency Matrix to define the graph

Adjacency List Adjacency List: A list type of storage structure The structure of arc adjvex nextarc info adivex; //the vertex which arc point to nextarc / point to the next arc pointer info:// the relative information of arc 顶点的结点结构 data firstarc data; //the vertex'information firstarc; //point to the first arc which associate the vertex

Adjacency List ▪ Adjacency List: A list type of storage structure。 ▪ The structure of arc adjvex; // the vertex which arc point to nextarc;// point to the next arc ’pointer info; // the relative information of arc adjvex nextarc info ▪顶点的结点结构 data firstarc data; // the vertex’ information firstarc; //point to the first arc which associate the vertex

a The adjacency list of undirected graph data adj dest link dest link A 0A 10 3∧ B 1 B 彐[2 2C 1∧ 3D 0 These edges come from the same vertex are in the same list. Each list node is delegated a certain edge(edge node), the node contain another vertex suflix--dest and pointer--linko

▪The adjacency list of undirected graph These edges come from the same vertex are in the same list. Each list node is delegated a certain edge(edge node), the node contain another vertex’ suffix--dest and pointer--link。 A B C D data adj A B C D 0 1 2 3 dest link dest link     1 3 0 2 1 0