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