[[courses:cs211:winter2018:journals:melkersonr:chapter3]]
Trace: • chapter5 • ch2 • 4.1.4 • chapter6 • 3.2.6 • preface • chapter3 • chapter6 • preface • chapter3
Show pagesource
Recent ChangesSitemap

This is an old revision of the document!

Table of Contents

Chapter 3 - Graphs

Section 3.1

  • Summary: Section 3.1 is Basic Definitions and Applications. Graphs consist of nodes and edges, where the edges join two nodes. Graphs can be undirected or directed, and graphs are assumed to be undirected unless stated otherwise. Technically, an edge between nodes u and v in an undirected graph is represented as the set {u,v}, but the authors warn that the notation for a directed edge, (u,v), will sometimes be used even for undirected edges. The directed edge (u,v) is an edge from u to v. Transportation, communication, information, social, and dependency networks are examples the authors provide for where graphs are used. The section also addresses paths (simple or cyclical), connectivity (including strong connectivity for directed graphs), and shortest path/distance between two nodes. Trees are connected graphs that have no cycles - they're “the simplest kind of connected graph: deleting any edge from a tree will disconnect it” (p77). While on the topic of trees, the authors state that “rooted trees are fundamental objects in computer science, because they encode the notion of a hierarchy” (p78). The section closes with a list of three statements about undirected graphs with n nodes, such that if any two are true so also is the third.
  • My Questions: Not exactly a question, but I wonder why the authors introduced trees in this section after we've already seen balanced binary trees when talking about the heap implementation of the priority queue. For example, it's an information repeat to tell us about parents and children.
  • Second Time Around: Honestly, everything in this chapter I'd seen before in MATH301 (except the Note to Self) and/or it was crystal clear in class.
  • Note to Self: In the information networks example (p75), it says that search engines use hyperlink edges between webpage nodes to determine what webpages are the most important. I didn't know that, but makes sense and it's certainly cool.
  • Readability: 10 - super straightforward. A relief after section 2.5.

Section 3.2

  • Summary: Section 3.2 is Graph Connectivity and Graph Traversal. Given two nodes s and t of a graph G = (V,E), connectivity is defined as there being a path from s to t. There are two algorithms for answering whether s and t are connected: breadth-first search (BFS) and depth-first search (DFS). BFS starts with node s, and then adds nodes in layers based on them being connected to the node(s) in the previous layer. Layer zero, then, is just node s. Layer one consists of all nodes connected to s. Layer two consists of all nodes connected to the nodes connected to s. And so on until there are no nodes left that aren't already in a layer. Because the distance between two nodes is defined as the “minimum number of edges on a path joining them” and a node will be absent from all layers “if and only if there is no path to it” (p 80), then BFS not only determines if there is a path between nodes s and t, but it also determines the shortest path. BFS is a method for finding a connected component, which is the set of all nodes reachable from starting node. Another method for finding a connected component is DFS. In DFS, you traverse as deeply as possible and only backtrack when you hit a dead end. While the BFS tree shows the shortest path from s to t and ends up being short and bushy, the DFS tree will usually be long and spindly. Finally, we can also determine the set of all connected components. Because for two nodes in a graph their connected components will either be identical or disjoint (3.8), we can start with any node, find its connected component, then if there were any nodes not visited in that search we find its connected component. If we continue until all nodes are visited, we will find the set of all connected components of the graph.
  • My Questions: So, how do we say that two search trees are equal? Or is that even a question that we ask? Are two BFS trees are equal if the same nodes appear in the same layers, or must the connections all be identical? This relates to question 1.d. on PS 3.
  • Second Time Around: Theorem 3.4, which says that if (x,y) is an edge in the graph, then the layers in which they appear for BFS differ by at most 1, made more sense the second time around. In class I was a little lost, but now that I've seen it twice I think I've got it.
  • Note to Self: I want to remember Theorem 3.8. It makes sense, I just hadn't thought about it before.
  • Readability: 7. I think the u's, v's, s's, and t's running around the section were hard to keep track of at times.

Section 3.3

  • Summary: Section 3.3 is Implementing Graph Traversal Using Queues and Stacks. This section finally addresses using lists vs arrays to represent graphs, and whether s queue or s stack is better for implementing BFS and DFS. There are two ways to represent a graph: adjacency matrix or adjacency list. While the authors introduce both, they use the adjacency list. Before weighing the pros and cons of using an adjacency matrix vs list, the authors comment on using both input parameters (number of nodes and number of edges) to determine runtime because it is difficult to say, for example, whether O(m^2) or O(n^3) is better. It depends on the relationship between the number of nodes and edges, but even that varies by graph. Since we aim for polynomial runtime in general, we aim for O(m+n) runtimes in this section. In terms of space requirements, the adjacency list wins. The adjacency matrix requires O(n^2) space, whereas the adjacency list require O(m+n) space. In terms of accessing information, the authors also argue in favor of the adjacency list. They say that “if the algorithm is currently looking at a node u, it can read the list of neighbors in constant time per neighbor” (p 89), which leads to a natural sense of “exploring” the graph. Before moving on to the implementation details of BFS and DFS, the section reviews queues and stacks: queues are FIFO, stacks are LIFO, and both can be implemented with a doubly-linked list which keeps pointers to both the head and the tail. BFS will be implemented using a queue, and DFS with a stack.
  • About the Algorithms: There are two algorithms in this section: implementing BFS and implementing DFS.
    • In BFS, we need to scan edges and only add one to a layer if it has not yet been added. As such, we create an array Discovered to maintain knowledge about which nodes have been discovered. Recall, BFS builds layers based on which nodes are connected to each other. We maintain the layers in an array. L[0] contains the starting node; L[1] contains the nodes in layer 1. It actually does not matter how the lists of nodes are implemented (as queues or stacks) because “the algorithm is allowed to consider the nodes in a layer L_i in any order” (p 91). To set up, the algorithm sets Discovered[s] to true for the starting node s and false for all other nodes, initializes L[0] to include only s, sets layer counter i to 0, and sets the BFS tree to an empty tree. The algorithm runs by checking if the current layer L[i] is empty or not. If it's nonempty, it initializes an empty list in L[i+1]. Then for each node in L[i], it considers each edge incident to that node, and if the node is not already discovered, it sets it to discovered, adds the edge to the tree, and adds the node to L[i+1]. Because the graph is represented as an adjacency list, it can consider the next neighbor of a node in constant time (as mentioned in Section 3.2). If the graph is represented using an adjacency list, BFS is O(m+n). Using a queue in the algorithm is mostly a side note, where the authors say that it doesn't change anything if you use a single list L implemented as a queue rather than an array L of lists L[i].
    • The last section defined DFS as a recursive process, but in this section we see that we're really maintaining the to-be-processed nodes in a stack. There are two main differences between BFS and DFS. DFS is “more impulsive” than BFS, so when “it explores a node u, it scans the neighbors of u until it finds the first not-yet-explored node v (if any), and then it immediately shifts attention to exploring v” (p 92). Contrast that with BFS where neighboring nodes aren't explored until all neighboring nodes are discovered. BFS keeps track of Discovered nodes, whereas DFS keeps track of Explored nodes. The other difference is that we have to keep track of a node's parent and only add edges (u, parent[u]) to the tree when u becomes Explored. To set up, the algorithm initializes the stack to contain the starting node s. The algorithm runs by checking if the stack is nonempty. While it's nonempty, it pops a node u from the stack. If that node is not yet marked as Explored, it sets Explored to be true, and then adds each neighboring node to the stack.
    • If the graph is represented using an adjacency list, BFS is O(m+n)
  • My Questions: The authors note: “a running time of O(m+n) is the same as O(m), since m >= n-1” (p 87). Why, then, do we bother saying runtimes are O(m+n) when, according to the authors, it's the same as O(m)? Also, why did the authors decide to only write out a partial DFS algorithm? The algorithm on page 93 does not include the processes involved in adding edges to the tree.
  • Second Time Around: I don't think I was aware the first time talking about BFS in class that we're representing the layers like an adjacency list: an array of lists. That's clear to me now.
  • Note to Self:
  • Readability: 6. I don't think the authors did a great job of making the algorithm implementations clear. I had to read a few things multiple times. For example, its not clear whether the sentence, “The adjacency list data structure is ideal for implementing breadth-first search” (p 90), refers to having the graph in that form or making the layer data structure an adjacency list, or both. Also, the sentence, “each node occurs on at most one list” (p 91), confused me at first because I was thinking of the graph's adjacency lists where each node is actually represented twice, but it's talking about the layers. It's true that each node appears in only one layer. Other things are stated without much explanation. “Note that there are at most n lists L[i]” doesn't have an explanation, but I presume it's because in the worst case the graph is a line and there is only one node per layer. Also, “we spend O(1) time considering each edge” doesn't have an explanation, but I presume that's true because we're assuming the graph is represented using an adjacency list and you can get to the next edge in the list of a node's edges in constant time.

Section 3.4

  • Summary: Section 3.4 is Testing Bipartiteness: An Application of Breadth-First Search.
  • Problem Motivations:
  • About the Algorithms:
  • My Questions:
  • Second Time Around:
  • Note to Self:
  • Readability:

Section 3.5

  • Summary: Section 3.5 is Connectivity in Directed Graphs.
  • Problem Motivations:
  • About the Algorithms:
  • My Questions:
  • Second Time Around:
  • Note to Self:
  • Readability:

Section 3.6

  • Summary: Section 3.6 is Directed Acyclic Graphs and Topological Ordering.
  • Problem Motivations:
  • About the Algorithms:
  • My Questions:
  • Second Time Around:
  • Note to Self:
  • Readability:
courses/cs211/winter2018/journals/melkersonr/chapter3.1517937261.txt.gz · Last modified: by melkersonr
Show pagesourceOld revisions
Media ManagerBack to top
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0