Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter3 [2018/02/04 17:11] – [3.3 Implementing Graph Traversal] nasona | courses:cs211:winter2018:journals:nasona:chapter3 [2018/02/06 15:19] (current) – [3.2 Graph Connectivity and Traversal] nasona | ||
|---|---|---|---|
| Line 107: | Line 107: | ||
| * If there is no path between s and t, then there cannot be a node v that is in the connected component of each. | * If there is no path between s and t, then there cannot be a node v that is in the connected component of each. | ||
| * A natural algorithm for producing all the connected components of a graph, by growing them one component at a time. We start with an arbitrary node s, and use BFS or DFS to generate its connected component. | * A natural algorithm for producing all the connected components of a graph, by growing them one component at a time. We start with an arbitrary node s, and use BFS or DFS to generate its connected component. | ||
| - | |||
| - | |||
| - | ==Questions== | ||
| ==Additional Information== | ==Additional Information== | ||
| Line 196: | Line 193: | ||
| * BFS and DFS spend work only on edges and nodes in the connected component containing the starting node. They never see any of the other, disjointed nodes or edges. | * BFS and DFS spend work only on edges and nodes in the connected component containing the starting node. They never see any of the other, disjointed nodes or edges. | ||
| * The algorithm only spends a constant amount of work on a given edge or node in the iteration when the connected component it belongs to is under consideration. The total runtime is O(n + m). | * The algorithm only spends a constant amount of work on a given edge or node in the iteration when the connected component it belongs to is under consideration. The total runtime is O(n + m). | ||
| - | |||
| - | ==Questions== | ||
| ==Additional Information== | ==Additional Information== | ||
| Line 206: | Line 201: | ||
| ==Summary== | ==Summary== | ||
| + | A bipartite graph is one where the nodes can be broken up into two sets in a way that every edge has one end in one set and the other end in the other. If a graph is bipartite, then it cannot contain an odd cycle. The presence of an odd cycle is the only obstacle to a graph being bipartite. The algorithm we will use to test whether a graph is bipartite is basically laid over BFS with the added complexity that the odd layers will be colored blue and the even layers will be colored red. Therefore, the total runtime for the algorithm is O(n + m). If there is no edge in the graph that joins two nodes of the same layer, the graph is bipartite. If there is an edge that joins two nodes in the same layer, the graph is not bipartite. | ||
| ==Notes== | ==Notes== | ||
| - | * A bipartite graph is one where the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y. Set X will be colored red and set Y will be colored blue | + | * A bipartite graph is one where the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y. Set X will be colored red and set Y will be colored blue. |
| The Problem | The Problem | ||
| Line 222: | Line 218: | ||
| Analyzing the Algorithm | Analyzing the Algorithm | ||
| * Let G be a connected graph, and let L1, L2,… be the layers produced by BFS starting at node s. Then exactly one of the following two statements must hold true. | * Let G be a connected graph, and let L1, L2,… be the layers produced by BFS starting at node s. Then exactly one of the following two statements must hold true. | ||
| - | * There is no edge of G joining two nodes of the same layer. In this case C is a bipartite graph in which the odes in even layers can be colored red, and the nodes in odd layers can be colored blue. | + | * There is no edge of G joining two nodes of the same layer. In this case C is a bipartite graph in which the nodes in even layers can be colored red, and the nodes in odd layers can be colored blue. |
| * Proof: Every edge joins two nodes in adjacent layers. Our coloring procedure gives nodes in adjacent layers the opposite colors, so every edge has ends with opposite colors. | * Proof: Every edge joins two nodes in adjacent layers. Our coloring procedure gives nodes in adjacent layers the opposite colors, so every edge has ends with opposite colors. | ||
| * There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite. | * There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle, and so it cannot be bipartite. | ||
| * Proof: If two nodes x and y in the same layer are joined by an edge, then the cycle through x, y and their lowest common ancestor z has odd length, so the graph cannot be bipartite. | * Proof: If two nodes x and y in the same layer are joined by an edge, then the cycle through x, y and their lowest common ancestor z has odd length, so the graph cannot be bipartite. | ||
| - | |||
| - | ==Questions== | ||
| ==Additional Information== | ==Additional Information== | ||
| Line 236: | Line 230: | ||
| ==Summary== | ==Summary== | ||
| + | In directed graphs, the edge (u, v) represents an edge that goes from u to v; edges have a direction. To represent directed graphs, we will still use adjacency lists, but, now, there are two lists that are associated with each node. One list represents the nodes that the given node has edges to (outgoing edges); the other list represents the nodes that the given node has edges from (incoming edges). Directed BFS and directed DFS still run in O(n + m) runtime; the only thing that changes is the fact that the algorithms have to follow the rules of the directional edges. A strongly connected graph if, for every two nodes u and v, there is a path from u to v and a path from v to u. If u can be reached from v and if v can be reached from u, then the two nodes are mutually reachable. An algorithm checking for strong connectivity merely requires BFS over graph G and graph G with its edges reversed. If both searches yield the same results, the component is strongly connected. This algorithm runs in O(m + n) runtime. | ||
| ==Notes== | ==Notes== | ||
| Line 263: | Line 258: | ||
| ==Summary== | ==Summary== | ||
| + | A directed graph is acyclic if it has no cycles. A topological ordering of a graph is an ordering of its nodes as v1, v2,… so that i<j for every edge (vi, vj). In other words, all of the edges are pointing forward. All DAGs have topological orderings. The first node in the topological ordering of an directed acyclic graph would need to have no incoming edges. We can implement an algorithm for finding the topological ordering of a DAG in O(m + n) time by keeping track of the active nodes, keeping track of the number of incoming edges for a given node and maintaining a set that has all of the active nodes in the graph with no incoming edges from other active nodes. The active nodes with no active incoming edges are the ones that will be deleted and added to the topological ordering next because there are no tasks that have precedence over that given node. | ||
| ==Notes== | ==Notes== | ||
| Line 291: | Line 287: | ||
| * Each iteration consists of selecting a node v from the set S and deleting it. After deleting v, we go through the nodes w to which v had an edge and subtract one from the number of active incoming edges that we are maintaining for w. If this makes the number of incoming active edges to w drop to zero, we add w to set S. | * Each iteration consists of selecting a node v from the set S and deleting it. After deleting v, we go through the nodes w to which v had an edge and subtract one from the number of active incoming edges that we are maintaining for w. If this makes the number of incoming active edges to w drop to zero, we add w to set S. | ||
| * This way, we keep track of all nodes eligible for deleting at all times and expend constant work per edge. | * This way, we keep track of all nodes eligible for deleting at all times and expend constant work per edge. | ||
| - | |||
| - | ==Questions== | ||
| ==Additional Information== | ==Additional Information== | ||
