Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:hornsbym:chapter_3 [2018/02/07 04:35] – [Section 3.2 (Graph connectivity/traversal)] hornsbym | courses:cs211:winter2018:journals:hornsbym:chapter_3 [2018/02/07 04:42] (current) – hornsbym | ||
|---|---|---|---|
| Line 30: | Line 30: | ||
| A bipartite graph is any graph which does not contain an odd cycle. In simpler terms, consider each of the nodes to be colored either red or blue. In a bipartite graph, a blue node can only connect to a red node, and vice versa. \\ | A bipartite graph is any graph which does not contain an odd cycle. In simpler terms, consider each of the nodes to be colored either red or blue. In a bipartite graph, a blue node can only connect to a red node, and vice versa. \\ | ||
| \\ | \\ | ||
| - | To determine whether or not a graph is bipartite, the first step involves running BFS on the graph. This will give us the layers of the graph. If any node on any level is connected to any node on that same level, the graph cannot be bipartite because the graph has to contain an odd cycle. This will always result in showing odd cycles, thus determining bipartiteness. | + | To determine whether or not a graph is bipartite, the first step involves running BFS on the graph. This will give us the layers of the graph. If any node on any level is connected to any node on that same level, the graph cannot be bipartite because the graph has to contain an odd cycle. This will always result in showing odd cycles, thus determining bipartiteness. |
| + | ===== Section 3.5 (Connectivity in Directed Graphs) ===== | ||
| + | Up until this point in chapter 3, we have been working with undirected graphs. This section addresses how to deal with directed graphs. \\ | ||
| + | \\ | ||
| + | In a directed graph, each edge has a direction. Since you can only follow the edge in the direction it points, this graph is considered directed. We represent directed graphs with two adjacency lists: one representing nodes that have edges pointing //in//, and one representing nodes that have edges pointing // | ||
| + | \\ | ||
| + | The BFS and DFS strategies discussed for undirected graphs work almost identically for directed graphs. However, the graphs will appear slightly different depending on whether or not you can reach one node from another. | ||
