Question? Leave a message!




Connectedness

Connectedness
ECE 250 Algorithms and Data Structures Connectedness Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Connectedness 2 Outline We will use graph traversals to determine: – Whether one vertex is connected to another – The connected subgraphs of a graphConnectedness 3 Connected First, let us determine whether one vertex is connected to another – v is connected to v if there is a path from the first to the second j k Strategy: – Perform a breadthfirst traversal starting at v j – While looping, if the vertex v ever found to be adjacent to the front of k the queue, return true – If the loop ends, return falseConnectedness 4 Connected Consider implementing a breadthfirst traversal on a graph: – Choose any vertex, mark it as visited and push it onto queue – While the queue is not empty: • 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,Connectedness 5 Determining Connections Is A connected to DConnectedness 6 Determining Connections Vertex A is marked as visited and pushed onto the queue A AConnectedness 7 Determining Connections Pop the head, A, and mark and push B, F and G B F G B F GConnectedness 8 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 F G H F GConnectedness 9 Determining Connections Popping F results in the pushing of E G H E G EConnectedness 10 Determining Connections In either graph, G has no adjacent vertices that are unvisited H E EConnectedness 11 Determining Connections Popping H on the left graph results in C and I being pushed C I DConnectedness 12 Determining Connections The queue op the right is empty – We determine A is not connected to D C I DConnectedness 13 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 IConnectedness 14 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 IConnectedness 15 Connected Components If we continued the traversal, we would find all vertices that are connected to A Suppose we want to partition the vertices into connected subgraphs – While there are unvisited vertices in the tree: • 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 efficiencyConnectedness 16 Connected Components Here we start with a set of singletons A B C D E F G H I J K A B C D E F G H I J KConnectedness 17 Connected Components The vertex A is unvisited, so we start with it A B C D E F G H I J K A B C D E F G H I J KConnectedness 18 Connected Components Take the union of with its adjacent vertices: A, B, H, I A B C D E F G H I J K A A C D E F G A A J KConnectedness 19 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 A B C D E F G H I J K A A C D E F A A A J KConnectedness 20 Connected Components Start another traversal with C: this defines a new set C A B C D E F G H I J K A A C D E F A A A J KConnectedness 21 Connected Components We take the union of C and its adjacent vertex J: C, J – This traversal is finished A B C D E F G H I J K A A C D E F A A A C KConnectedness 22 Connected Components We start again with the set D A B C D E F G H I J K A A C D E F A A A C KConnectedness 23 Connected Components K and E are adjacent to D, so take the unions creating D, E, K A B C D E F G H I J K A A C D D F A A A C DConnectedness 24 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 A B C D E F G H I J K A A C D D D A A A C DConnectedness 25 Connected Components All vertices are visited, so we are done – There are three connected subgraphs A, B, G, H, I, C, J, D, E, F, K A B C D E F G H I J K A A C D D D A A A C DConnectedness 26 Tracking Unvisited Vertices How do you implement a list of unvisited vertices so as to: – Find an unvisited vertex in Q(1) time – Remove a vertex that has been visited from this list in Q(1) time We cannot simply flag vertices as visited, as this would require O(V) time to find an unvisited vertex The solution will have to use Q(V) additional memory…Connectedness 27 Tracking Unvisited Vertices Create two arrays: – One array, unvisited, will contain the unvisited vertices – The other, locinunvisited, will contain the location of vertex v in i the first array 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G H I J K A B C D E F G H I J K 0 1 2 3 4 5 6 7 8 9 10Connectedness 28 Tracking Unvisited Vertices Suppose we visit D – D is in entry 3 0 1 2 3 4 5 6 7 8 9 10 A B C D E F G H I J K A B C D E F G H I J K 0 1 2 3 4 5 6 7 8 9 10Connectedness 29 Tracking Unvisited Vertices Suppose we visit D – D is in entry 3 – Copy the last unvisited vertex into this location and update the location array for this value 0 1 2 3 4 5 6 7 8 9 10 A B C K E F G H I J A B C D E F G H I J K 0 1 2 3 4 5 6 7 8 9 3Connectedness 30 Tracking Unvisited Vertices Suppose we visit G – G is in entry 6 0 1 2 3 4 5 6 7 8 9 10 A B C K E F G H I J A B C D E F G H I J K 0 1 2 3 4 5 6 7 8 9 3Connectedness 31 Tracking Unvisited Vertices Suppose we visit G – G is in entry 6 – Copy the last unvisited vertex into this location and update the location array for this value 0 1 2 3 4 5 6 7 8 9 10 A B C K E F J H I A B C D E F G H I J K 0 1 2 3 4 5 6 7 8 6 3Connectedness 32 Tracking Unvisited Vertices Suppose we now visit K – K is in entry 3 0 1 2 3 4 5 6 7 8 9 10 A B C K E F J H I A B C D E F G H I J K 0 1 2 3 4 5 6 7 8 6 3Connectedness 33 Tracking Unvisited Vertices Suppose we now visit K – K is in entry 3 – Copy the last unvisited vertex into this location and update the location array for this value 0 1 2 3 4 5 6 7 8 9 10 A B C I E F J H A B C D E F G H I J K 0 1 2 3 4 5 6 7 3 6 3Connectedness 34 Tracking Unvisited Vertices If we want to find an unvisited vertex, we simply return the last entry of the first array and return it 0 1 2 3 4 5 6 7 8 9 10 A B C I E F J H A B C D E F G H I J K 0 1 2 3 4 5 6 7 3 6 3Connectedness 35 Tracking Unvisited Vertices In this case, an unvisited vertex is H – Removing it is trivial: just decrement the count of unvisited vertices 0 1 2 3 4 5 6 7 8 9 10 A B C I E F J A B C D E F G H I J K 0 1 2 3 4 5 6 7 3 6 3Connectedness 36 Tracking Unvisited Vertices The actual algorithm is exceptionally fast: – The initialization is Q(V) int unvisitednV; int locinunvisitednV; for ( int i = 0; i nV; ++i ) unvisitedi = i; locinunvisitedi = i; Connectedness 37 Tracking Unvisited Vertices The actual algorithm is exceptionally fast: – Determining if the vertex v is visited is fast: Q(1) k bool isunvisited( int k ) const return locinunvisitedk count unvisited locinunvisitedk == k; Connectedness 38 Tracking Unvisited Vertices The actual algorithm is exceptionally fast: – Marking vertex v as having been visited is also fast: Q(1) k void erase( int k ) if ( isunvisited() ) return; // It has already been marked as visited count; int posn = locinunvisitedk; unvisitedposn = unvisitedcount; locinunvisitedunvisitedcount = posn; Connectedness 39 Tracking Unvisited Vertices The actual algorithm is exceptionally fast: – Returning a vertex that is unvisited is also fast: Q(1) int return unvisited() if ( count == 0 ) throw underflow(); count; return unvisitedcount; Connectedness 40 Summary This topic covered connectedness – Determining if two vertices are connected – Determining the connected subgraphs of a graph – Tracking unvisited verticesConnectedness 41 References Wikipedia, http://en.wikipedia.org/wiki/Connectivity(graphtheory) These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017

Recommend