Graph Traversal
COMP9312_22T2
– Connectivity
Copyright By PowCoder代写 加微信 powcoder
– Topological sort
Breath-first and depth-first traversals
Strategies
Traversals of graphs are also called searches Applications of BFS
§ Shortest Path §…
Applications of DFS
§ Strongly connected component § Topological Order
A quick view:
https://seanperfecto.github.io/BFS-DFS-Pathfinder/
Breadth-first traversal
Consider implementing a breadth-first traversal on a graph: • Chooseanyvertex,markitasvisitedandpushitontoqueue
• Whilethequeueisnotempty:
• Pop to top vertex v from the queue
• For each vertex adjacent to v that has not been visited:
• Mark it visited, and
• Push it onto the queue
This continues until the queue is empty
• Note: if there are no unvisited vertices, the graph is connected
The size of the queue is at most O(|V|)
Breadth-First Traversal
An implementation can use a queue
Consider this graph
Performing a breadth-first traversal • Push the first vertex onto the queue
Performing a breadth-first traversal • PopAandpushB,CandE
Performing a breadth-first traversal: • PopBandpushD
Performing a breadth-first traversal: • PopCandpushF
Performing a breadth-first traversal: • PopEandpushGandH
A, B, C, E
Performing a breadth-first traversal: • Pop D
A, B, C, E, D
Performing a breadth-first traversal: • Pop F
A, B, C, E, D, F
Performing a breadth-first traversal: • PopGandpushI
A, B, C, E, D, F, G
Performing a breadth-first traversal: • Pop H
A, B, C, E, D, F, G, H
Performing a breadth-first traversal:
• Pop I, The queue is empty: we are finished
A, B, C, E, D, F, G, H, I
Coding practice~
Number of iterations: diameter
Depth-First Traversal
Consider implementing a depth-first traversal on a graph: • Choose any vertex, mark it as visited
• From that vertex:
• If there is another adjacent vertex not yet visited, go to it
• Otherwise, go back to the last vertex that has not had all of its adjacent vertices visited and continue from there
• Continue until no visited vertices have unvisited adjacent vertices
Two implementations:
• Recursive approach (a statement in a function calls itself repeatedly)
• Iterative approach (a loop repeatedly executes until the controlling condition becomes false)
Recursive depth-first traversal
A recursive implementation uses the call stack for memory:
Iterative depth-first traversal
An iterative implementation can use a stack
Perform a recursive depth-first traversal on this same graph
Performing a recursive depth-first traversal: • Visit the first node
Performing a recursive depth-first traversal: • A has an unvisited neighbor
Performing a recursive depth-first traversal: • B has an unvisited neighbor
Performing a recursive depth-first traversal: • C has an unvisited neighbor
A, B, C, D
Performing a recursive depth-first traversal: • D has no unvisited neighbors, so we return to C
A, B, C, D, E
Performing a recursive depth-first traversal: • E has an unvisited neighbor
A, B, C, D, E, G
Performing a recursive depth-first traversal: • G has an unvisited neighbor
A, B, C, D, E, G, I
Performing a recursive depth-first traversal: • I has an unvisited neighbor
A, B, C, D, E, G, I, H
Performing a recursive depth-first traversal:
• We recurse back to C which has an unvisited neighbour
A, B, C, D, E, G, I, H, F
Performing a recursive depth-first traversal:
• We recurse finding that no other nodes have unvisited neighbours
A, B, C, D, E, G, I, H, F
Comparing BFS and DFS
The order can differ greatly
• An iterative depth-first traversal may also be different again
BFS: A, B, C, E, D, F, G, H, I Recursive DFS: A, B, C, D, E, G, I, H, F
Quick quiz
Can you show the result of iterative
depth-first traversal?
Performing an iterative depth-first traversal: • Push the first vertex onto the stack
Performing an iterative depth-first traversal: • PopAandpushB,CandE
Performing an iterative depth-first traversal: • PopEandpushGandH
Performing an iterative depth-first traversal: • PopHandpushI
Performing an iterative depth-first traversal: • Pop I
A, E, H, I
Performing an iterative depth-first traversal: • Pop G
A, E, H, I, G
Performing an iterative depth-first traversal: • PopCandpushDandF
A, E, H, I, G, C
Performing an iterative depth-first traversal: • Pop F
A, E, H, I, G, C, F
Performing an iterative depth-first traversal: • Pop D
A, E, H, I, G, C, F, D
Performing an iterative depth-first traversal: • Pop B
A, E, H, I, G, C, F, D, B
Complexity Analysis
We have to track which vertices have been visited requiring O(|V|) memory
The time complexity cannot be better than and should not be worse than O(|V| + |E|)
Connected graphs simplify this to O(|E|) – Why?
DFS: Recursive VS stack-based
Coding practice~
Which one is better?
https://docs.google.com/forms/d/e/1FAIpQLSdrFDB9mq3nHhpufQ0p7MuuGH41e36DkJFg1 r8Rv_S4iFaogQ/viewform?usp=sf_link
This topic covered graph traversals
• Consideredbreadth-firstanddepth-firsttraversals • Depth-firsttraversalscanrecursiveoriterative
• Consideredanexamplewithbothimplementations • They are also called searches
y Dynamic Depth-First Search in Directed Graphs
ua Yang\, \, Lu Qin\, \, Xubo Wang\, and Xuemin Lin§ *Recent Research on DFS/BFS
\Centre for Artificial Intelligence, University of Technology Sydney, Australia §The University of Wales, Australia
{dong.wen, lu.qin, ying.zhang, Dynamic Graphs
When graph updates (new edge inserts or old edge remove s) rch (DFS)CisoamfunpduamtenDtalFaSndfirmopmortasnctraal-tch v1 v0 v0
h analysis. It is the basis of many graph algo- v18
VS v2 v4 v3
ramework and corresponding algorithms for is a virtual root connecting all vertices in G.
computing strongly connected components, ty, and detecting biconnected components.
Update DFS tree v7 DFS is normally shown as a DFS-Tree. Given
dates in many real-world graphs (e.g., social ommunication networks), we study the prob- v6 ee maintenance in dynamic directed graphs.
ver, their methods cannot easily be applied
general directed graphs. Motivated by this, Figure 1: An example graph G and its DFS-Tree T .
e, most works focus on the DFS-Tree main-
m in undirected graphs and directed acyclic (a) The graph G
rtion and deletion in general directed graphs. e several optimizations to speed up the algo-
48 22T2 connected components [9,17,20], detecting biconnected com-
ponents [11], finding graph bridges [21], finding paths, de-
(b) A DFS-Tree T of G
nduct extensive experiments on 12 real-world
*Recent Research on DFS/BFS
External Memory Algorithms
If there is no enough memory to store the whole graph, how to compute DFS
*Recent Research on DFS/BFS
Distributed Algorithms
The information (neighbors) of different vertices locate in different machines.
Distributed DFS algorithm is hard.
Connectivity
Connectivity
We will use graph traversals to determine: • Whether one vertex is connected to another
• The connected sub-graphs of a graph
First, let us determine whether one vertex is connected to another
• vj isconnectedtovk ifthereisapathfromvj tovk Strategy:
• Performabreadth-firsttraversalstartingatvj
• While looping, if the vertex vk ever found to be adjacent to the front of the queue, return
• If the loop ends, return false
Determining Connections
Is A connected to D?
Determining Connections
Vertex A is marked as visited and pushed onto the queue
Determining Connections
Pop the head, A, and mark and push B, F and G
Determining Connections
Pop B and mark and, in the left graph, mark and push H • On the right graph, B has no unvisited adjacent vertices
Determining Connections
Popping F results in the pushing of E
Determining Connections
In either graph, G has no adjacent vertices that are unvisited
Determining Connections
Popping H on the left graph results in C and I being pushed
Determining Connections
The queue op the right is empty
• We determine A is not connected to D
Determining Connections
On the left, we pop C and return true because D is adjacent to C • In the left graph, A is connected to D
Determining Connections
On the left, we pop C and return true because D is adjacent to C • In the left graph, A is connected to D
Connectivity
Coding practice~
Any better idea?
Connected Components
If we continued the traversal, we would find all vertices that are connected to A
Suppose we want to find the connected components of the graph
• While there are unvisited vertices:
• Select an unvisited vertex and perform a traversal on that vertex
• Each vertex that is visited in that traversal is added to the set initially containing the initial unvisited vertex
• Continue until all vertices are visited
We would use a disjoint set data structure for maximum efficiency (will be introduced later)
Connected Components
Here we start with a set of singletons
Connected Components
The vertex A is unvisited, so we start with it
Connected Components
Take the union of with its adjacent vertices: {A, B, H, I}
Connected Components
As the traversal continues, we take the union of the set {G} with the set containing H: {A, B, G, H, I}
• The traversal is finished
Connected Components
Start another traversal with C: this defines a new set {C}
Connected Components
We take the union of {C} and its adjacent vertex J: {C, J} • This traversal is finished
Connected Components
We start again with the set {D}
Connected Components
K and E are adjacent to D, so take the unions creating {D, E, K}
Connected Components
Finally, during this last traversal we find that F is adjacent to E • Take the union of {F} with the set containing E: {D, E, F, K}
Connected Components
All vertices are visited, so we are done
• There are three connected sub-graphs {A, B, G, H, I}, {C, J}, {D, E, F, K}
Tracking Unvisited Vertices
The time complexity to find an unvisited vertex: O(|V|)
How do you implement a list of unvisited vertices so as to: • FindanunvisitedvertexinO(1)time
• RemoveavertexthathasbeenvisitedfromthislistinO(1)time?
The solution will use O(|V|) additional memory Coding practice~
Tracking Unvisited Vertices
Create two arrays:
• One array, unvisited, will contain the unvisited vertices
• The other, loc_in_unvisited, will contain the location of vertex vi in the first array
Tracking Unvisited Vertices
Suppose we visit D • Disinentry3
Tracking Unvisited Vertices
Suppose we visit D
• Disinentry3
• Copy the last unvisited vertex into this location and update the location array for this value
Tracking Unvisited Vertices
Suppose we visit G • Gisinentry6
Tracking Unvisited Vertices
Suppose we visit G
• Gisinentry6
• Copy the last unvisited vertex into this location and update the location array for this value
Tracking Unvisited Vertices
Suppose we now visit K • Kisinentry3
Tracking Unvisited Vertices
Suppose we now visit K
• Kisinentry3
• Copy the last unvisited vertex into this location and update the location array for this value
Tracking Unvisited Vertices
If we want to find an unvisited vertex, we simply return the last entry of the first array and return it
Tracking Unvisited Vertices
In this case, an unvisited vertex is H
• Removing it is trivial: just decrement the count of unvisited vertices
Tracking Unvisited Vertices
The actual algorithm is exceptionally fast: • The initialization is O(|V|)
• Determining if the vertex vk is visited is fast: O(1)
• Marking vertex vk as having been visited is also fast: O(1) • Returning a vertex that is unvisited is also fast: O(1)
Compute connected components with new data structure We start with two arrays
Compute connected components with new data structure
The first unvisited vertex is K – RemoveK
Compute connected components with new data structure
– VisitDthroughtheedge(K,D)
– CopyJintolocation3andupdatethelocationarray
Compute connected components with new data structure
– VisitEthroughtheedge(K,E)
– CopyIintolocation4andupdatethelocationarray
Compute connected components with new data structure
– VisitFthroughtheedge(E,F)
– CopyHintolocation5andupdatethelocationarray
Compute connected components with new data structure
– BFSQueueisempty,onecomponent{D,E,F,K}isfound. – Then,wevisitG
Compute connected components with new data structure
– VisitHthrough(G,H) – RemoveH
Compute connected components with new data structure
Compute connected components with new data structure
– CopyJintolocation0andupdatethelocationarray
Compute connected components with new data structure
– CopyCintolocation1andupdatethelocationarray
Compute connected components with new data structure
Compute connected components with new data structure
Connected Component Detection
Coding practice~
Any other easier way to implement?
Disjoint set data structure
• Considernelements,named1,2,…,n
• The disjoint set is a collection of sets of elements
• Each element is in exactly one set • setsaredisjoint
• tostart,eachsetcontainsoneelement
• SetName=find(elementName)
• returnsthenameofthesetthatcontainsthegivenelement
• union(SetName1,SetName2)
• uniontwosetstogetherintoanewset
How to quickly perform union and find operations?
Disjoint set data structure
Attempt 1: Quick Find
• Arrayimplementation.elementsare1,…,N
• SetName[i] = name of the set containing element i • Pseudo code:
Initialize(int N)
SetName = new int [N+1]; for (int e=1; e<=N; e++)
SetName[e] = e;
Union(int i, int j)
for (int k=1; k<=N; k++)
if (SetName[k] == j) SetName[k] = i;
int Find(int e) return SetName[e];
Time Complexity Analysis: Find : O(1), Union : O(n)
Note: we usually use n to denote the number of vertices (i.e., |V|) and use m to denote the number of edges (i.e., |E|).
Disjoint Set data structure
Attempt 2: Smart Union: Union by Size
• union(u, v): make smaller tree’s root point to bigger one’s root • That is, make v’s root point to u’s if v’s tree is smaller.
• Union(4,5), union(6,7), union(4,6)
Now perform union(3, 4). Smaller tree made the child node.
101 7 22T2
Disjoint Set data structure
Union by Size:
link smaller tree to larger one
Lemma: After n union ops, the tree height is at most log(n).
Initialize(int N)
setsize = new int[N+1]; parent = new int [N+1]; for (int e=1; e <= N; e++)
parent[e] = 0;
setsize[e] = 1;
int Find(int e)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com