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:17] – [3.4 Bipartite Graphs: An Application of BFS] 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 227: | Line 222: | ||
| * 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 237: | 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 264: | 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 292: | 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== | ||
