Connectedness definition

connectedness definition psychology and connectedness examples psychology and connectedness in graph theory
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
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