CS代考 Lecture 19: Basic Graph Algorithms

Lecture 19: Basic Graph Algorithms

Processing Graphs
• Graphs model many scenarios

• Many problems are presented as graph problems
• Can then use known general graph algorithms to solve those
• Data is inputted as adjacency matrix or, more commonly, an adjacency lists
• To start processing the data, we often need some way to derive structure from this input
• Breadth First Search and Depth First Search are the most common simple ways of imposing structure.

Breadth First Search
BFS idea. Explore outward from in all possible directions, adding nodes one “layer” at a time.
1 all neighbors of 􏰇.
2 all nodes that do not belong to
all nodes that do not belong to an earlier layer, and that
to a node in 1. 􏰌􏰑􏰆
1, and that have an edge
have an edge to a node in 𝑖.
Def: The distance from to is the number of edges on the shortest
pathfrom to .
Theorem. For each , 𝑖 consists of all nodes at distance exactly from . There is a path from to iff appears in some layer.

Color: indicates status
• white: (initial value)
undiscovered
• gray: discovered, but neighbors not fully processed
• black: discovered and neighbors fully processed
Every node stores a color, a distance and a parent
Distance (d): the length of shortest path from s to u
Parent (p): u’s predecessor on the shortest path from s to u
BFS Algorithm
BFS(𝐺, 𝑠):
for each vertex 𝑢∈𝑉−{𝑠}
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑤h𝑖𝑡𝑒 𝑢. 𝑑 ← ∞
𝑠. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦
initialize an empty queue 𝑄 Enqueue(𝑄, 𝑠)
……………
Note: Assume, initially, that G is connected (will fix later)

BFS Algorithm Complete
BFS(𝐺, 𝑠):
for each vertex 𝑢∈𝑉−{𝑠}
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑤h𝑖𝑡𝑒 𝑢. 𝑑 ← ∞
𝑠. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦 𝑠. 𝑑 ← 0
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
initialize an empty queue 𝑄 Enqueue(𝑄,𝑠)
while 𝑄≠Ø do
𝑢 ← Dequeue(𝑄) for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢]
𝑣. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then 𝑣. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦 𝑣.𝑑←𝑢.𝑑 + 1
Enqueue(𝑄, 𝑣) 𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑏𝑙𝑎𝑐𝑘
Note: Nodes in Queue
• Are ones that have been seen
but are unprocessed (gray)
• Algorithm keeps current active nodes in a (FIFO) Queue
• Starts by inserting in
• At each step takes node
• Checks all neighbors
•If has not been seen yet
• Marks 𝑣 as seen (gray)
• Says that distance from
𝑠 to 𝑣 is 1+distto𝑢
• Makes 𝑢 the parent of 𝑣 (9)
• inserts 𝑣 in queue (10)
• Marks as being fully processed (11)

Running time:
, which is
if the graph is connected.
BFS Algorithm Complete
Parent pointers:
 Pointing to the node that leads to its discovery
BFS(𝐺, 𝑠):
for each vertex 𝑢∈𝑉−{𝑠}
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑤h𝑖𝑡𝑒 𝑢. 𝑑 ← ∞
𝑠. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦
initialize an empty queue 𝑄 Enqueue(𝑄, 𝑠)
while 𝑄≠Ø do
𝑢 ← Dequeue(𝑄) for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢]
if 𝑣. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then 𝑣. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦
𝑣. 𝑑 ← 𝑢. 𝑑 + 1 𝑣. 𝑝 ← 𝑢 Enqueue(𝑄, 𝑣)
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑏𝑙𝑎𝑐𝑘
Parent must be in
 Can follow parent pointers to
find the actual shortest path  The pointers form a BFS
tree, rooted at

Note: BFS finds the shortest path from to every other node.

Connected Components
Connected component containing . All nodes reachable from . 1 7 9 11
4 5 8 10 12
Connected component containing node
BFS starting from finds the connected component containing .
Repeatedly running BFS from an undiscovered node finds all the connected components.

Modification for Finding Connected Components
for each vertex 𝑢∈𝑉 do
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑤h𝑖𝑡𝑒 𝑢. 𝑑 ← ∞
for each vertex 𝑢∈𝑉 do if 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then
BFS-Visit(𝑢)
BFS-Visit(𝐺, 𝑠): |*Assumes s is white*|
𝑠. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦 𝑠. 𝑑 ← 0
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
initialize an empty queue 𝑄 Enqueue(𝑄,𝑠)
while 𝑄≠Ø do
𝑢 ← Dequeue(𝑄) for each 𝑣 ∈ 𝐴𝑑𝑗[𝑢]
𝑣. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then 𝑣. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦 𝑣.𝑑←𝑢.𝑑 + 1
Enqueue(𝑄, 𝑣) 𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑏𝑙𝑎𝑐𝑘
The old BFS(G,s) algorithm is renamed BFS-Visit(G,s).
A new upper-level BFS(G) is created.
BFS(G) initializes all vertices to white (unvisited)
It then calls all vertices s, passing them to BFS-visit(s), if s was not already seen while traversing a previously visited connected component.

Connected Components
Connected component containing . All nodes reachable from . 1 7 11 2
4 5 8 10 12
BFS-Visit(1) would turn all nodes in leftmost component black

Connected Components
Connected component containing . All nodes reachable from . 1 7 11 2
4 5 8 10 12
BFS-Visit(1) would turn all nodes in leftmost component black BFS-Visit(2) would turn all nodes in rightmost component black
BFS-Visit(i) for would do nothing.
BFS-Visit(10) would then turn all nodes in middle component black

s-t connectivity and shortest path in directed graphs
s-t connectivity (often called reachability for directed graphs). Given two nodes and , is there a path from to ?
 Undirected graph: can reach can reach
 Directed graph: Not necessarily true
s-t shortest path problem. Given two node and , what is the length of the shortest path between s and t?
 Undirected graph: is the shortest path from to is the shortest path from to
 Directed graph: Not necessarily true
BFS on a directed graph. Same as in undirected case
 Ex: Web crawler. Start from web page . Find all web pages
linked from s, either directly or indirectly.

Strong Connectivity in Directed Graphs
Def. Node and are mutually reachable if there is a path from to and also a path from to .
Def. A graph is strongly connected if every pair of nodes is mutually reachable.
strongly connected not strongly connected
Definition: vertex s is “strong” in Graph G if,
foreveryvertext, thereis apathfromstotandfromttos.
Observation 1: If graph G has a strong vertex s then EVERY vertex in G is strong
Observation 2: A graph G is strongly connected
if and only if every vertex in G is strong

Strong Connectivity in Directed Graphs
Def. Node and are mutually reachable if there is a path from to and also a path from to .
Def. A graph is strongly connected if every pair of nodes is mutually reachable.
strongly connected
Algorithm for checking strong connectivity
not strongly connected
 Pick any node .
 Run BFS from
 Reverse all edges in
 Return true iff all nodes reached in both BFS executions.
and run BFS from

Strongly Connected Components
Strongly-Connected-Components(𝐺):
create 𝐺􏰢􏰽􏰾 which is 𝐺 with all edges reversed while there are nodes left do
𝑢←any node
run BFS in 𝐺 starting from 𝑢
run BFS in 𝐺􏰢􏰽􏰾 starting from 𝑢
𝐶 ← {nodes reached in both BFSs}
output 𝐶 as a strongly connected component remove 𝐶 and its edges from 𝐺 and 𝐺􏰢􏰽􏰾
Running time:
See text book for a algorithm (not required)

Exercise on Chess
Find the minimum number of steps taken by a knight to reach a destination
(x’,y’) from an input position (x,y) on a chess board.
Start from position (x,y) and apply BFS, considering that the neighbors of (x,y) are all the positions that can be reach with one move (as above).
Continue this process for each neighbor
The first time that you reach (x’,y’) corresponds to the minimum number of steps.
From some position (x, y) the knight can move to the following positions provided that they are within the board limits:
(x + 2, y – 1)
(x + 2, y + 1) (x – 2, y + 1) (x – 2, y – 1) (x + 1, y + 2) (x + 1, y – 2) (x – 1, y + 2) (x – 1, y – 2)

Exercise on Binary Maze
Given a binary rectangular maze, find the shortest path’s length from a
position (x,y) to position (x’,y’).
[1101 0] [01110] [01101] [10111]
The path can only contain cells having value 1, and at position (x,y) the valid moves are:
GoTop: (x–1,y)
GoLeft: (x,y–1) GoDown: (x+1,y) GoRight: (x,y+1)
Start from position (x,y) and apply BFS, considering that the neighbors of (x,y) are all the positions that can be reach with one move (as above).
Continue this process for each neighbor
The first time that you reach (x’,y’) corresponds to the minimum number of steps.

Exercise on Bipartite Graphs A bipartite graph is a graph whose vertices can be divided into two disjoint
sets U and V such that every edge connects a vertex in U to one in V.
Problem: Given a connected undirected graph determine whether it is bipartite or not.
• Run BFS from any vertex: d[v] stores the shortest distance from the root to v. Set S to be the set of all vertices with even d[v], and V-S all vertices with odd d[v].
• G is bipartite if and only if all edges (u,v) in the graph satisfy that the parity of d[v] and d[u] are not the same, i.e., d[v] is odd and d[u] is even or vice versa.
• Alternatively: If a graph contains an odd cycle, we cannot divide the graph such that every adjacent vertex has a different parity. To check if a given graph contains an odd-cycle or not, do a breadth–first search starting from an arbitrary vertex v. If in the BFS, we find an edge, both of whose endpoints are at the same level, then the graph is not Bipartite, and an odd-cycle is found.

Depth First Search and DFS Tree
• Breadth first search is “Broad”.
• It builds a wide tree, connecting a node to ALL of the neighbors that
have not yet been processed.
• Once a node starts being processed, it sees ALL of its neighbors
before any other node is processed
• There is another procedure, called DEPTH first search.
• Instead of going broad, it goes DEEP
• It recursively searches deep into the tree
• When a node u is processed, it looks at each of its neighbors in order
• At the time u checks a neighbor v, DFS starts processing v
(which starts processing it’s children, which start processing their children, etc.).
• Only after all of v’s descendants have been processed does u go on to process its next neighbor

Depth First Search and DFS Tree

DFS Algorithm
 White: undiscovered
 Gray: discovered, but
neighbors not fully explored
(on recursion stack)
 Black: discovered and
neighbors fully explored
Parent pointers:
Pointing to the node that leads to its discovery The pointers form a tree, rooted at
for each vertex 𝑢∈𝑉 do
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑤h𝑖𝑡𝑒
for each vertex 𝑢∈𝑉 do
if 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then DFS-Visit(𝑢)
………….
• DFS(G) calls the DFS-visit search on each vertex u
• Before DFS-Visit(u) returns, all nodes in the connected component containing u are turned black (will see later)
• So DFS-Visit will only be called once for each connected component in G

for each vertex 𝑢∈𝑉 do
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑤h𝑖𝑡𝑒
for each vertex 𝑢∈𝑉 do
if 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then DFS-Visit(𝑢)
DFS-Visit(𝑢):
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦
for each 𝑣∈𝐴𝑑𝑗𝑢 do
if 𝑣. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then 𝑣. 𝑝 ← 𝑢
DFS-Visit(𝑣) 𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑏𝑙𝑎𝑐𝑘
Running time:
DFS Algorithm
 White: undiscovered
 Gray: discovered, but neighbors
not fully explored (on recursion
 Black: discovered and neighbors
fully explored
Parent pointers:
 Pointing to the node that leads to its discovery
 The pointers form a tree, rooted at 𝑠
We can add starting and finishing time for each u:
Starting time when u.color ← gray Finishing time when u.color ← black

Adjacency Lists: a:b,i,k,n,h
b: a, f, d, e, i
The starting and finishing timesareusefulforsome applications (to be discussed later)
Thebold edgesformtheDFS tree. Therestoftheedges(light red) point to ancestors in the tree, and are called back- edges.
• Back edges are also useful for some applications.
DFS Worked Example
2 15 2427 b n h
g: h 4 5 h: a, g c i:e,b,k,a
n: a, j, m, l
36 101317202526
i 18 19 l •
e m21 22 914 k

Application: Cycle Detection
Problem: Given an undirected graph , check if it contains a cycle.
 A tree (connected and acyclic) contains exactly edges.
 If it has fewer edges, it cannot be connected.
 If it has more edges, it must contain a cycle.
Algorithm:
 Run BFS/DFS to find all the connected components of .
 For each connected component, count the number of edges.
 If # edges # vertices, return “cycle detected”.
Running time:
Q: What if we also want to find a cycle (any is OK) if it exists?

Tree edges, back edges, and cross edges
After running BFS or DFS on an undirected graph, all edges can be classified into one of 3 types:
 Tree edges: traversed by the BFS/DFS.
 Back edges: connecting a node with one of its ancestors in the BFS/DFS-tree
(other than its parent).
 Cross edges: connecting two nodes with no ancestor/descendent relationship.
Theorem: In a DFS on an undirected graph, there are no cross edges.
Pf: Consider any edge in .
 Without loss of generality, assume is discovered before .
is discovered while is gray (why?). is in the DFS subtree rooted at u.
, then is a tree edge. , then is a back edge.
Theorem: In a BFS on an undirected graph, there are no back edges. (Not proven)

DFS for cycle detection
Idea: Run DFS on each connected component of .
If is a back edge.
– => is an ancestor (but not parent) of in the DFS trees.
=>There is thus a path from to in the DFS-tree and
=> to plus back edge creates a cycle.
If no back edge exists then only contains (DFS) tree edges – => the graph is a forest, and hence is acyclic.
• In DFS starting at a,
(i,b) was first back edge found
• => b was ancestor (not parent) of i in tree
• => tree contains path (b->e->i) from b to i
• => this path plus edge (i ,b) is the cycle b->e->i->b

DFS for cycle detection
Running time:
 Only traverse DFS-tree edges, until the first non- tree edge is found
 At most tree edges
CycleDetection(𝐺):
for each vertex 𝑢∈𝑉 do
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑤h𝑖𝑡𝑒
for each vertex 𝑢∈𝑉 do
if 𝑢. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then return “No cycle”
DFS-Visit(𝑢):
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑔𝑟𝑎𝑦
for each 𝑣∈𝐴𝑑𝑗𝑢 do
if 𝑣. 𝑐𝑜𝑙𝑜𝑟 = 𝑤h𝑖𝑡𝑒 then 𝑣. 𝑝 ← 𝑢
DFS-Visit(𝑢)
DFS-Visit(𝑣)
else if 𝑣≠𝑢.𝑝 then //back edge (u,v)
output “Cycle found:” while 𝑢≠𝑣 do
𝑢 ← 𝑢. 𝑝 output 𝑣
𝑢. 𝑐𝑜𝑙𝑜𝑟 ← 𝑏𝑙𝑎𝑐𝑘

Directed Graph
A directed graph distinguishes between edge and edge . Directed graphs are often used to represent order-dependent tasks
• out-degree of vertex is the number of edges leaving
• in-degree of vertex is the number of edges entering
• Each edge in-degree of
contributes one to the out-degree of , so
and one to the

Topological Sort
• Directed Acyclic Graph (DAG): Directed graph with no cycles.
• A Topological ordering of a graph is a linear ordering of the vertices
of a DAG such that if the linear ordering
is in the graph,
appears before in
• Topological ordering may not be unique
• The graph above has many topological orderings
• 0, 6, 1, 4, 3, 2, 5, 7, 8, 9
• 0, 4, 1, 6, 2, 5, 3, 7, 8, 9

Topological Sort Algorithm
• Observations
• A DAG must contain at least one vertex with in-degree
• Algorithm: Topological Sort (TS)
1. Output a vertex with in-degree zero in current
2. Remove and all edges from current graph.
3. If graph is not empty, goto step 1.
• Correctness
• At every stage, current graph remains a DAG (why?)
• Because current graph is always a DAG, TS can always output some vertex. So algorithm outputs all vertices.
• Suppose output order is not a topological order.
=> Then there is some edge such that appears before in the order. This is impossible, though, because can not be output until edge is removed!

Topological Sort Algorithm
Topological Sort(G)

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts