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