Algorithms & Data Structures (Winter 2022) Graphs – Introduction
• Introduction. • BFS.
• Strong Connected Components / Topological Sort. • Network Flow 1.
Copyright By PowCoder代写 加微信 powcoder
• Network Flow 2.
• Shortest Path.
• Minimum Spanning Trees.
• Bipartite Graphs.
Graphs – Definition
• An abstract way of representing connectivity using nodes (also called vertices) and edges.
• m edges connect some pairs of nodes.
• Edges can be either one-directional (directed) or bidirectional.
• Nodes and edges can have some auxiliary information.
Graphs – Definition
• Graph G = (V, E)
• V = set of vertices
• E=setofedgesÍ(V ́V)
• Types of graphs
• Undirected: edge (u, v) = (v, u); for all v, (v, v) Ï E (No self loops.)
• Directed: (u, v) is edge from u to v, denoted as u ® v. Self loops are allowed.
• Weighted: each edge has an associated weight, given by a weight
function w : E ® R.
• Dense: |E| » |V|2.
• Sparse: |E| << |V|2. a
• |E| = O(|V|2) 11 d1e2f
Graphs - Properties
• If (u, v) Î E, then vertex v is adjacent to vertex u.
• Adjacency relationship is: • Symmetric if G is undirected.
• Not necessarily so if G is directed.
• If G is (strongly) connected:
• There is a path between every pair of vertices. • |E|3|V|–1.
• Furthermore, if |E| = |V| – 1, then G is a tree.
Graphs - Vocabulary
• Ingoingedgesofu:{(v,u)∈E} (e.g.in(e)={(b,e),(d,e)}) • Outgoingedgesofu:{(u,v)∈E}(e.g.out(d)={(d,e)})
• In-degree(u): | in(u) | // Number of predecessors
• Out-degree(u): | out(u) | //Number of successors
Graphs - Representation
• Two standard ways. • Adjacency Lists.
• Adjacency Matrix.
1234 10111 21010
c d 31101 3 4 41010
Graphs – Representation – Adjacency List
• Consists of an array Adj of |V| lists.
• One list per vertex.
• For u Î V, Adj[u] consists of all vertices adjacent to u.
Note: If weighted, store weights also in adjacency lists.
Adjacency List – Storage Requirement
• For directed graphs:
• Sum of lengths of all adj. lists is
åout-degree(v) = |E| vÎV
• Total storage: Q(V+E)
• For undirected graphs:
• Sum of lengths of all adj. lists is ådegree(v) = 2|E|
• Total storage: Q(V+E)
No. of edges leaving v
No. of edges incident on v. Edge (u,v) is incident
on vertices u and v.
Adjacency List – Pros and Cons
• Space-efficient, when a graph is sparse.
• Can be modified to support many graph variants.
• Determining if an edge (u,v) ÎE is not efficient. • Have to search in u’s adjacency list. Q(degree(u)) time.
• Q(V) in the worst case.
Graphs – Representation – Adjacency Matrix
• |V| ́ |V| matrix A.
• Number vertices from 1 to |V| in some arbitrary manner.
1 if(i,j)ÎE • A is then given by: A[i, j] = aij = ìíî0 otherwise
1a b2 1234 10111 20010 cd430001 3 40000
1234 10111 2 1 0 1 0
A=AT forundirectedgraphs. 11
c d 31101 3 4 41010
Adjacency Matrix – Storage-Time Requirement
• Space: Q(V2).
• Not memory efficient for large sparse graphs.
• Time: to list all vertices adjacent to u: Q(V). • Time: to determine if (u, v) Î E: Q(1).
• Can store weights instead of bits for weighted graph. abcdef
Graphs– Traversal-Searching
• IsthereapathfromstovinG? • Searching a graph:
• Systematically follow the edges of a graph to visit the vertices of the graph.
• Used to discover the structure of a graph.
• Standard graph-searching algorithms. • Breadth-first Search (BFS).
• Depth-first Search (DFS).
Graphs– Breadth-First Search
• Expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.
• The algorithm discovers all vertices at distance k from s before discovering any vertices at distance k + 1.
• A vertex is “discovered” the first time it is encountered during the search. A vertex is “finished” if all vertices adjacent to it have been discovered.
• It uses a first-in, first-out queue Q to manage the progress.
• Colors the vertices to keep track of progress.
• White – Undiscovered.
• Grey – Discovered but not finished. • Black – Finished.
• Colors are required only to reason about the algorithm. Can be implemented without colors.
Graphs– Breadth-First Search
• Input: Graph G = (V, E), either directed or undirected, and source vertex s Î V.
• d[v] = distance (smallest # of edges, or shortest path) from s
to v, for all v Î V. d[v] = ¥ if v is not reachable from s.
• p[v] = u such that (u, v) is last edge on shortest path s v.
• u is v’s predecessor.
• Builds breadth-first tree with root s that contains all reachable vertices.
Breadth-First Search - Example
Breadth-First Search - Example
Breadth-First Search - Example
Q: r t x 122
Breadth-First Search - Example
Q: t x v 222
Breadth-First Search - Example
Q: x v u 223
Breadth-First Search - Example
Q: v u y 233
Breadth-First Search - Example
Breadth-First Search - Example
Breadth-First Search - Example
Breadth-First Search - Example
Breadth-First Search - Analysis
Initialization O(V)
Traversal Loop:
After initialization, each vertex is enqueued and dequeued at most once, and each operation takes O(1). So, total time for queuing is O(V).
The adjacency list of each vertex is scanned
at most once. The sum of lengths of all
adjacency lists is Q(E).
Breadth-First Search - Analysis
• Initialization takes O(V).
• Traversal Loop
• After initialization, each vertex is enqueued and dequeued at most once, and each operation takes O(1). So, total time for queuing is O(V).
• The adjacency list of each vertex is scanned at most once. The sum of lengths of all adjacency lists is Q(E).
• Summing up over all vertices ⇒ total running time of BFS is O(V+E), linear in the size of the
adjacency list representation of graph.
Breadth-First Search - Application
• Suppose we are given an unweighted directed graph G = (V, E) with two special vertices, and we want to find the shortest path from a source vertex s to a target vertex t.
• Special case of shortest path.
• All edges have weight 1, and the length of a path is just the number of edges.
Breadth-First Search - Application
14th , 2020 29
Depth-First Search
• Explore edges out of the most recently discovered vertex v.
• When all edges of v have been explored, backtrack to explore other edges leaving the vertex from which v was discovered (its predecessor).
• “Search as deep as possible first.”
• Continue until all vertices reachable from the original source
are discovered.
• If any undiscovered vertices remain, then one of them is chosen as a new source and search is repeated from that source.
Depth-First Search
• Input: G = (V, E), directed or undirected. No source vertex given.
• 2 timestamps on each vertex. Integers between 1 and 2|V|. • d[v] = discovery time (v turns from white to gray)
• f [v] = finishing time (v turns from gray to black)
• p[v] : predecessor of v = u, such that v was discovered during the scan of u’s adjacency list.
• Uses the same coloring scheme for vertices as BFS.
• Builds depth-first forest comprising several depth-first
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
Starting time d(x)
4/5 3/ xyz
Finishing time f(x)
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
Depth-First Search - Example
4/5 3/6 10/ xyz
Depth-First Search - Example
4/5 3/6 10/ xyz
Depth-First Search - Example
4/5 3/6 10/11
Depth-First Search - Example
4/5 3/6 10/11
Depth-First Search - Example
Starting time d(x)
4/5 3/6 10/11
Finishing time f(x)
Depth-First Search
DFS-Visit(u)
1. 2. 3. 4. 5. 6. 7.
for each vertex u Î V[G] do color[u] ¬ white
p[u] ¬ NIL time ¬ 0
for each vertex u Î V[G] do if color[u] = white
then DFS-Visit(u)
3. 4. 5. 6. 7. 8.
color[u] ¬ GRAY # White vertex u has been discovered
time ¬ time + 1 d[u] ¬ time
for each v Î Adj[u]
do if color[v] = WHITE then p[v] ¬ u
DFS-Visit(v) color[u] ¬ BLACK # Blacken u;
it is finished.
f[u] ¬ time ¬ time + 1
Uses a global timestamp time.
Depth-First Search - Analysis
• Loops on lines 1-2 & 5-7 take Q(V) time, excluding time to execute DFS-Visit.
• DFS-Visit is called once for each white vertex vÎV when it’s painted gray the first time. Lines 4-7 of
DFS-Visit is executed |Adj[v]| times. The total cost of executing DFS-Visit is åvÎV|Adj[v]| = Q(E)
• Total running time of DFS is Q(V+E).
Depth-First Search - Analysis
Depth-First Search - Application
• Depth-first search is often a subroutine in another algorithm.
• Depth-first search yields valuable information about the structure of a
• The most basic property of depth-first search is that the predecessor subgraph G does indeed form a forest of trees.
• Another important property of depth-first search is that discovery and finishing times have parenthesis structure.
• If we represent the discovery of vertex u with a left parenthesis “(u” and represent its finishing by a right parenthesis “u)”, then the history of discoveries and finishings makes a well-formed expression in the sense that the parentheses are properly nested.
OK: ( { } ) [ ] Not OK: ( { ) }
123456 1234 52
Parenthesis Property
2/9 1/10
4/5 7/8 12/13
Whatever First Search
BFS and DFS differ essentially only in that one uses a queue and the other uses a stack.
Bag = Stack : Depth-First (Topological Sort)
Bag = Queue : Breadth-First (Shortest Path)
Bag = Priority Queue : Best-First (Minimum Spanning Tree)
• Introduction.
• Strong Connected Components / Topological Sort. • Network Flow 1.
• Network Flow 2.
• Shortest Path.
• Minimum Spanning Trees.
• Bipartite Graphs.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com