Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2018:journals:hornsbym:chapter_3 [2018/01/30 04:52] – created hornsbym
+++ courses:cs211:winter2018:journals:hornsbym:chapter_3 [2018/02/07 04:42] (current) – hornsbym
@@ Line 1: / Line 1: @@
-====== Chapter 3(Graphs) ======
+====== Chapter 3 ======
 ===== Section 3.1(Basic definitions) =====
 As the title suggests, section 3.1 simply outlines the basic definitions that the book will use when discussing graphs.\\
@@ Line 12: / Line 12: @@
 \\
 Thus, we can then arrange any graph that follows these three requirements into a tree shape.
+===== Section 3.2 (Graph connectivity/Graph traversal) =====
+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 "correct" path.
+===== Section 3.3 (Graph traversal using queues and stacks) =====
+This section describes how graphs can be best represented, then moves on to discuss the implementations of BFS and DFS.\\
+\\
+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(//n//<sup>2</sup>) storage space. The adjacency list, however, is built as an array of linked lists. These lists expand dynamically, resulting in O(//m// + //n//) space. Thus, the adjacency list is the more space efficient way of representing a graph. Adjacency matrices can access their data in constant time, however, while adjacency lists must search each list linearly. Thus, adjacency matrices allow for faster access of data.\\
+\\
+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 //out//.\\
+\\
+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.