Question? Leave a message!




Connectedness

Connectedness
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
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 © 2006-2013 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 sub-graphs 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 breadth-first 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 breadth-first 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 D?Connectedness 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 sub-graphs – 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 K
sharer
Presentations
Free