复旦大学：《数据结构与算法设计 Data Structures and Algorithm》课程英文讲义_Chapter 10 Graph algorithms

Data Structures and Algorithm Xiaoqing Zheng Zhengxq@fudan.edu.cn

Data Structures and Algorithm Data Structures and Algorithm Xiaoqing Zheng zhengxq@fudan.edu.cn

Representations of undirected graph 2 5 3 5)(4 Adjacency-list representation of graph G=(V, E)

Representations ofd d h un directe d grap h 1 2 1 2 5 / 3 2 1 3 4 / 3 2 4 4 2 5 3 / / 5 4 4 2 5 3 / 5 4 1 / Adjacency-list representation of graph G = ( V, E )

Representations of undirected graph 12345 101001 210110 301010 5)(4 510010 Adjacency-matrix representation of graph G=(V, E)

Representations ofd d h un directe d grap h 1 2 12345 1 01001 3 2 10110 3 0 1 0 1 0 5 4 3 0 1 0 1 0 4 01101 5 1 0 0 1 0 d f h 5 1 0 0 1 0 A djacency-matrix representation of grap h G = ( V, E )

Representations of directed graph 4 4(5 6 123456 Adjacency-list representation of graph G=(V, E)

Representations ofd d h irecte d grap h 1 2 3 1 2 4 / 2 5 / 3 6 5 4 2 / / 4 5 4 2 / 6 5 4 / 6 6 / Adjacency-list representation of graph G = ( V, E )

Representations of directed graph 123456 10100 2000010 3000011 4010000 4(5 6 5000100 6000001 Adjacency-matrix representation of graph G=(V, E)

Representations ofd d h irecte d grap h 1 2 3 123456 1 010100 2 000010 3 000011 4 5 6 4 010000 5 000100 d f h 6 000001 A jacency-matrix representation of grap h G = ( V, E )

raphs Definition. a directed graph(digraph G=(, E) is an ordered pair consisting of a set v of vertices(singular: vertex ● a set e∈ x y ofedges. In an undirected graphG=(v, E), the edge set e consists of unordered pairs of vertices In either case, we have E=O(2). Moreover, if G is connected, then E≥-1

G h rap s D fi i i Definition. A di d h rected graph (di h grap ) G = (V, E) is an ordered pair consisting of y a set V of vertices (i l s ngu ar: vertex), y a set E ∈ V × V of edges. In an undirected graph G = (V, E), the edge set E consists of unordered pairs of vertices. In either case, we have |E| = O(V2). Moreover, if G is connected then is connected, then |E| ≥ |V| – 1

Representations of grap Adjacency-list representation An adjacency list of a vertex v E v is the list Adilv of vertices adjacent to v For undirected graphs, Adilvl= degree(v) For directed graphs, lAdilvll=out-degree(v) Adiacency-matrix representation The adjacency matrix of a graph G=(v, E), where ={1,2,…,n}, is the matrix A[1….n21….n] given by A[;.n∫lif()∈E, 0 if(i,j e

Representations of h grap Adjacency-list representation list representation An adjacency list of a vertex v ∈ V is the list Adj[v] of ertices adjacent to of vertices adjacent to v. y For undirected graphs, |Adj[v]| = degree(v). y For directed graphs For directed graphs, |Adj[v]| = out-degree(v). Adjacency-matrix representation The adjacency matrix of a graph G = (V, E), where V = {1, 2, …, n}, is the matrix A[1 … n, 1 … n] given by 1 if (i, j) ∈ E, A[i j] = 0 if (i, j) ∉ E. A[i, j]

Breadth-first search Given a graph G=(, E)and a distinguished source vertex s, breadth -first search systematically explores the edges of g to discover every vertex that is reachable from S

Bread ht -f h irst search Gi en a graph Given a graph G = (V, E) and a disting ished and a distinguished source vertex s, breadth-first search systematically explores the edges of the edges of G to "discover" every vertex that is to "discover" every vertex that is reachable from s. ∞ 0 ∞ ∞ r stu ∞ ∞ ∞ ∞ v wxy

Breadth-first search example Gray vertices

Bread ht -f hl irst search example r s t u ∞ 0 ∞ ∞ r Q s ∞ ∞ ∞ ∞ 0 Gray vertices v w x y y

Breadth-first search example 11 Gray vertices

Bread ht -f hl irst search example r s t u Q w r 1 0 ∞ ∞ r 1 1 ∞ 1 ∞ ∞ Gray vertices v w x y y