CS代写 COMP9312_22T2

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 removes) 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