Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:hornsbym:chapter_3 [2018/02/07 03:55] – [Section 3.1(Basic definitions)] hornsbym | courses:cs211:winter2018:journals:hornsbym:chapter_3 [2018/02/07 04:42] (current) – hornsbym | ||
|---|---|---|---|
| Line 13: | Line 13: | ||
| Thus, we can then arrange any graph that follows these three requirements into a tree shape. | Thus, we can then arrange any graph that follows these three requirements into a tree shape. | ||
| - | ===== Section 3.2 (Graph connectivity/ | + | ===== Section 3.2 (Graph connectivity/ |
| - | + | This section covers two important strategies for reaching every node in a fully connected graph: breadth-first and depth-first search (BFS and DFS, respectively).\\ | |
| + | \\ | ||
| + | Breadth-first search explores every node directly connected to the starting node, then moves on to do the same for each of these newly explored nodes. The resulting tree shows layers that coincide with the distance from the starting node. For example, the first layer includes all nodes directly connected to the start node, the second layer includes all nodes twice removed from the start node, etc. This strategy is good for finding the shortest path from one node to another, as it always organizes itself around the distance from the start node.\\ | ||
| + | \\ | ||
| + | Depth-first search does the opposite. BFS chooses a node to traverse to, then traverses to another node connected to it. It does this process recursively until it reaches a dead end, then backs up until it reaches an unexplored node. This results in a long, spindly tree. This tree is good for showing all of possible options, like solving a maze. It might not show the shortest path, but it will inevitably show the " | ||
| + | ===== Section 3.3 (Graph traversal using queues and stacks) ===== | ||
| + | This section describes how graphs can be best represented, | ||
| + | \\ | ||
| + | Graphs can be represented two ways: they can be stored in either an adjacency matrix or an adjacency list. The adjacency matrix is built as an array of arrays, resulting in O(// | ||
| + | \\ | ||
| + | Both the BFS and DFS algorithms put forward by this section run in O(//m// + //n//) time when stored in adjacency lists (pp. 91 and 93 for specific details). | ||
| + | ===== Section 3.4 (Bipartiteness) ===== | ||
| + | This section describes bipartite graphs, and describes a strategy for determining whether a complex graph is bipartite. \\ | ||
| + | \\ | ||
| + | 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. | ||
| + | ===== 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. | ||
