Chapter 5 - Graph Traversal.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 5: Graph Traversal (Completed 10/32: 31%)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Notes:\n",
    "\n",
    "Note that BFS and DFS differ regarding when a node is marked as \"discovered\", when the parent relation is encoded, and therefore when nodes/edges are added to the search tree. This is partly due to the fact that DFS does not use a stack, even though it is occasionally helpful to think of it this way, in contrast to the queue used in BFS; DFS is implemented recursively.\n",
    "\n",
    "In BFS, all of a node's adjacent undiscovered vertices are immediately marked as \"discovered\", marked as a child of the current node (added with Tree edges to the tree), and put on the queue. In BFS, nodes are added to the tree while the *parent* is being processed.\n",
    "\n",
    "In DFS however, when processing a node, at first all but one of its nodes are *completely ignored*; they aren't put on the stack because there is no stack; no parent relation is recorded and nothing is marked as \"discovered\". Instead, the single node chosen to be first is recorded as a child (adding it with a Tree edge to the tree), then DFS is called on this child node, and then it is marked as \"discovered\". In DFS, nodes are added to the tree, essentially, when they themselves are being processed, when they have been \"entered into\". Thinking of a stack gives the false impression that when a node is being processed, all of its edges are looked at up front, before diving into the next node.\n",
    "\n",
    "This incorrect thinking was confusing me for a bit. Because if a path from the first child can lead back to another child of the same parent (think of a triangle with 3 edges), the other child will still be undiscovered; it is then marked as a descendant of the other child and a Back edge is created back to the original parent. If you imagine a stack being used, you may think both nodes were at first made as children of the parent, leading to a Cross edge between them. This cannot be correct: on undirected graphs, DFS labels every edge as either a Tree edge or a Back edge; no Cross edges."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simulating Graph Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 [3]\n",
    "\n",
    "For the following graphs $G_1$ (left) an $G_2$ (right):\n",
    "\n",
    "(a): Report the order of the vertices encountered on a breadth-first search starting from vertex $A$. Break all ties by picking the vertices in alphabetical order (i.e., $A$ before $Z$).  \n",
    "(b): Report the order of the vertices encountered on a depth-first search starting from vertex $A$. Break all ties by picking the vertices in alphabetical order (i.e., $A$ before $Z$).\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Skiena_Fig_5-1.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:* \n",
    "\n",
    "**(a):**\n",
    "\n",
    "On left: $A\n",
    "\\rightarrow B\n",
    "\\rightarrow D\n",
    "\\rightarrow I\n",
    "\\rightarrow C\n",
    "\\rightarrow E\n",
    "\\rightarrow G\n",
    "\\rightarrow J\n",
    "\\rightarrow F\n",
    "\\rightarrow H$\n",
    "\n",
    "On right: $A\n",
    "\\rightarrow B\n",
    "\\rightarrow E\n",
    "\\rightarrow C\n",
    "\\rightarrow F\n",
    "\\rightarrow I\n",
    "\\rightarrow D\n",
    "\\rightarrow G\n",
    "\\rightarrow J\n",
    "\\rightarrow M\n",
    "\\rightarrow H\n",
    "\\rightarrow K\n",
    "\\rightarrow N\n",
    "\\rightarrow L\n",
    "\\rightarrow O\n",
    "\\rightarrow P$\n",
    "\n",
    "**(b):**\n",
    "\n",
    "On left: $A\n",
    "\\rightarrow B\n",
    "\\rightarrow C\n",
    "\\rightarrow E\n",
    "\\rightarrow D\n",
    "\\rightarrow G\n",
    "\\rightarrow H\n",
    "\\rightarrow F\n",
    "\\rightarrow J\n",
    "\\rightarrow I$\n",
    "\n",
    "On right: $A\n",
    "\\rightarrow B\n",
    "\\rightarrow C\n",
    "\\rightarrow D\n",
    "\\rightarrow H\n",
    "\\rightarrow G\n",
    "\\rightarrow F\n",
    "\\rightarrow E\n",
    "\\rightarrow I\n",
    "\\rightarrow J\n",
    "\\rightarrow K\n",
    "\\rightarrow L\n",
    "\\rightarrow P\n",
    "\\rightarrow O\n",
    "\\rightarrow N\n",
    "\\rightarrow M$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 [3]\n",
    "\n",
    "Do a topological sort of the following graph $G$:\n",
    "\n",
    "![Skiena Fig 5-2](Figures/Skiena_Fig_5-2.png)\n",
    "\n",
    "Errata: \"this graph is not acyclic. Reverse the edge $(F,H)$.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "To find a topological sort, we perform a Depth-First Search and reverse the order the vertices were labeled \"processed\".\n",
    "\n",
    "A DFS starting at vertex $A$ will pass through the nodes in the following order:\n",
    "\n",
    "$A\n",
    "\\rightarrow B\n",
    "\\rightarrow C\n",
    "\\rightarrow F\n",
    "\\rightarrow D\n",
    "\\rightarrow E\n",
    "\\rightarrow G\n",
    "\\rightarrow I\n",
    "\\rightarrow J\n",
    "\\Rightarrow H$\n",
    "\n",
    "where \"$\\Rightarrow$\" indicates we had to initialize a new component, since with the correction there is no way of reaching vertex $H$.\n",
    "\n",
    "What order were they labeled \"processed\"? Vertices are labeled \"processed\" when the search exits from them (backtracks from them). In the traversal order above, they are labeled \"processed\" in the following order:\n",
    "\n",
    "$F\n",
    "\\rightarrow C\n",
    "\\rightarrow J\n",
    "\\rightarrow I\n",
    "\\rightarrow G\n",
    "\\rightarrow E\n",
    "\\rightarrow D\n",
    "\\rightarrow B\n",
    "\\rightarrow A\n",
    "\\rightarrow H$\n",
    "\n",
    "Reversing the direction of the arrows produces a topological sort:\n",
    "\n",
    "$H\n",
    "\\rightarrow A\n",
    "\\rightarrow B\n",
    "\\rightarrow D\n",
    "\\rightarrow E\n",
    "\\rightarrow G\n",
    "\\rightarrow I\n",
    "\\rightarrow J\n",
    "\\rightarrow C\n",
    "\\rightarrow F$\n",
    "\n",
    "One can check that for every edge $(x,y)$ in the graph, vertex $x$ appears before vertex $y$ in the given topological sort."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 [3]\n",
    "\n",
    "Prove by induction that there is a unique path between any pair of vertices in a tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Let $K$ be the number of levels in the tree.\n",
    "\n",
    "**Base case: $K = 1$.**\n",
    "\n",
    "If there is only one level in the tree, there can only be one node in the tree, otherwise the tree would be disconnected. This follows from the fact that all edges connect parents to children, and so all edges connect one level to another. If there is only one level, there can't be any edges. This case is trivially true since there are no pairs of vertices in a tree with only one node.\n",
    "\n",
    "**Base case: $K = 2$.**\n",
    "\n",
    "In this case there is a single parent, and the rest of the nodes are children connected directly to the parent. For a given pair of nodes $(x,y)$, if one of them is the parent, then there is a single edge connecting them. An alternate route between them would have to enter/exit the parent from another child, and therefore would require there to be a edges directly between children, which is not allowed. Therefore the edge between child and parent is a unique path between them. If neither $x$ nor $y$ is the parent, then they are both children. Since edges directly between children are not allowed, any path between them must pass through the parent. Because the path from child to parent is unique, the path from one child, to the parent, to a different child is also unique.\n",
    "\n",
    "Therefore there is a unique path between any pair of vertices in a tree with only $2$ levels.\n",
    "\n",
    "**General case: $K = K$.**\n",
    "\n",
    "Suppose there is a unique path between any pair of vertices in a tree with less than $K$ levels.\n",
    "\n",
    "A tree with $K$ levels can be viewed as multiple subtrees with $K-1$ levels with their roots connected directly to the overall root.\n",
    "\n",
    "For any pair of vertices $(x,y)$, if they are both in the same subtree, then by our induction hypothesis there is a unique path between them.\n",
    "\n",
    "If $x$ is the overall root, let $p$ be the root of the subtree with $K-1$ levels containing $y$. $p$ must be connected directly to $x$, and the edge between them is a unique path from $x$ to $p$; otherwise there would have to be edges between subtrees, which is not possible since all edges are edges between parents and children. Put another way, the root of a subtree provides the only (that is, unique) access point to that subtree. Now there is also a unique path from $p$ to $y$ by our induction hypothesis, since they are both in a tree with $K-1$ levels. Therefore there is a unique path from $x$ to $p$ to $y$, which is from $x$ to $y$. \n",
    "\n",
    "If $x$ and $y$ are in different subtrees, any path between them must pass through the overall root $p$, otherwise there would have had to have been an edge directly connecting subtrees. As argued above, the path from $x$ to the overall root $p$ is unique, and so is the path between $y$ and $p$. Therefore connecting them into a path from $x$ to $p$ to $y$ provides a unique path from $x$ to $y$.\n",
    "\n",
    "Therefore there is a unique path between any pair of vertices in any tree with an arbitrary number of levels."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.4 [3]\n",
    "\n",
    "Prove that in a breadth-first search on a undirected graph $G$, every edge is either a tree edge or a cross edge, where $x$ is neither an ancestor nor descendant of $y$, in cross edge $(x, y)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "BFS and DFS classify all edges $(x,y)$ into 4 possible classes:\n",
    "\n",
    "- **Tree edge**: $y$ was discovered or \"enterered into\" directly from $x$; $x$ is $y$'s parent in the traversal tree\n",
    "- **Forward edge**: $y$ was already a descendant of $x$ when edge $(x,y)$ was processed\n",
    "- **Back edge**: $y$ was an ancestor of $x$ when edge $(x,y)$ was processed\n",
    "- **Cross edge**: $y$ was already discovered or \"entered into\" when edge $(x,y)$ was processed, but is not an ancestor or descendant of $x$\n",
    "\n",
    "On undirected graphs, DFS can only produce Tree and Back edges, as described on page 178. Here we wish to show that BFS can only produce Tree and Cross edges. The simplest example that shows this differing behavior is computing the traversal tree for a simple dense triangle with 3 nodes and 3 edges. DFS produces 2 Tree edges and 1 Back edge, while BFS produces 2 Tree edges and 1 Cross edge.\n",
    "\n",
    "**No Forward Edges:** Suppose $(x,z)$ is an potential Forward edge, meaning $z$ is already a descendant of $x$. We assume that this graph is \"simple\", meaning there are no multi-edges. Then there must be an intermediate node $y$ such that $y$ is a descendant of $x$ and $z$ is a descendant of $y$. But in BFS, the edges of node $x$ would have been completely processed before those of $y$, and $z$ would have been made a direct child of $x$ rather than a descendant of $y$. The edge $(x,z)$ would therefore be a Tree edge, and could not be a Forward edge.\n",
    "\n",
    "** No Back Edges:** Similarly, suppose edge $(z,x)$ is being processed from node $z$, and $z$ is already a descendant of $x$, suggesting this should be a Back edge. Since this is BFS, all of $x$'s edges would have been processed before those of any of its descendants. Therefore this edge would have been processed while processing node $x$, not node $z$, making it a Tree edge."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.5 [3]\n",
    "\n",
    "Give a linear algorithm to compute the chromatic number of graphs where each vertex has degree at most $2$. Must such graphs be bipartite?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**Chromatic number:** the smallest number of colors sufficient to vertex-color a graph, meaning no adjacent nodes are the same color.\n",
    "\n",
    "**Bipartite graph:** A graph where every node can be divided into two groups such that every edge in the graph connects a node in one group with a node in the other; or equivalently, no edge in the graph contains 2 nodes in the same group. Or equivalently, the chromatic number of the graph is $2$.\n",
    "\n",
    "In our graph $G$, every node is of degree $0$, $1$, or $2$. The nodes of degree $0$ can be colored any color without incident, since they have no adjacent nodes. Therefore assume that no node has degree $0$. In this case, the graph is either a line, with 2 nodes of degree $1$, or a circle, with no nodes of degree $1$. The rest of the nodes are of degree $2$. The graph could also contain multiple components, with some of either type. But in this case we could just color the components separately; the coloring of one component cannot affect the coloring of the others. Therefore we assume our graph is connected, and must be either a circle or a line.\n",
    "\n",
    "The restriction to nodes of degree at most $2$ makes this problem easy, because when entering a node from a parent, there is at most one way out. The complexity of graph problems often arises from the multiplicity of possible paths through the graph. But in this case, once a starting node and direction are chosen, there is a unique path.\n",
    "\n",
    "Before we develop an algorithm, we can work out what cases arise to what chromatic numbers. If $G$ is a line, we could traverse it from one end to the other, coloring the nodes alternating colors. Therefore a line has chromatic number $2$.\n",
    "\n",
    "If $G$ is a circle, we can color one vertex one color, say, blue, then move around the circle alternating colors between blue and another color, say, red. However, we might end up back at our starting vertex with 2 adjacent blues. This will happen if the circle has an odd number of vertices. (For example, look at a triangle with 3 edges.) In this case we will need a third color to color the last vertex.\n",
    "\n",
    "To summarize, lines have chromatic number 2, circles with an even number of vertices have chromatic number 2, and circles with an odd number of vertices have chromatic number 3. A line can be differentiated from a circle by the presence of 2 nodes with degree $1$.\n",
    "\n",
    "Therefore we have the following algorithm:\n",
    "\n",
    "$\\hspace{2em} \\text{For each component:}$  \n",
    "$\\hspace{4em} \\text{Pick a random starting node}$  \n",
    "$\\hspace{4em} \\text{If the node has degree 0:}$  \n",
    "$\\hspace{6em} \\text{The chromatic number of that component is 1}$  \n",
    "$\\hspace{6em} \\text{Continue to next component}$  \n",
    "$\\hspace{4em} \\text{Traverse the component, counting the number of vertices}$  \n",
    "$\\hspace{4em} \\text{If a node of degree 1 is reached:}$  \n",
    "$\\hspace{6em} \\text{The chromatic number of that component is 2}$  \n",
    "$\\hspace{4em} \\text{If the starting node is reached and there was an even number of nodes:}$  \n",
    "$\\hspace{6em} \\text{The chromatic number of that component is 2}$  \n",
    "$\\hspace{4em} \\text{If the starting node is reached and there was an odd number of nodes:}$  \n",
    "$\\hspace{6em} \\text{The chromatic number of that component is 3}$  \n",
    "$\\hspace{6em} \\text{Return 3}$  \n",
    "$\\hspace{2em} \\text{Return the maximum chromatic number over all components}$  \n",
    "\n",
    "In this algorithm, each node is touched at most once, less if a node of degree 1 is reached and the starting vertex wasn't the other end of the line. Each node is processed in constant time (check degree number, increment number of nodes, and change chromatic number if necessary). Therefore this is a linear-time algorithm.\n",
    "\n",
    "Another possible algorithm would be to actually color the vertices with alternating colors until they are all colored or until 2 adjacent nodes would be colored the same color, in that case short circuit and return 3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.9 [3]\n",
    "\n",
    "Suppose an arithmetic expression is given as a tree. Each leaf is an integer and each internal node is one of the standard arithmetical operations $(+,−, *, /)$. For example, the expression $2 + 3 * 4 + (3 * 4)/5$ is represented by the tree in Figure 5.17(a). Give an $O(n)$ algorithm for evaluating such an expression, where there are $n$ nodes in the tree.\n",
    "\n",
    "![Skiena Fig 5-1](Figures/Skiena_Fig_5-5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Note that if a node's value is an operator, it must have exactly $2$ children; if its value is a number, then it must have exactly $0$ children. The algorithm below is recursive and would be called on the root of the tree. The convention is that if node $p$ has 2 children, they are labeled $p1$ and $p2$.\n",
    "\n",
    "$\\hspace{2em} \\text{Solve(node p):}$  \n",
    "$\\hspace{4em} \\text{If Value is a number:}$  \n",
    "$\\hspace{6em} \\text{Return Value}$  \n",
    "$\\hspace{4em} \\text{If Value is an operator:}$  \n",
    "$\\hspace{6em} \\text{A = Solve(node p1)}$  \n",
    "$\\hspace{6em} \\text{B = Solve(node p2)}$  \n",
    "$\\hspace{6em} \\text{Return (A operator B)}$  \n",
    "\n",
    "In this algorithm, each node is processed exactly once. Other than recursive calls and passing back return values, the only computations are the binary operations computing \"$\\text{(A operator B)}$\" for the nodes that contain operators. Therefore this algorithm will be linear in the number of nodes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm Design"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.14 [3]\n",
    "\n",
    "A *vertex cover* of a graph $G = (V,E)$ is a subset of vertices $V' \\in V$ such that every edge in $E$ contains at least one vertex from $V'$. Delete all the leaves from any depth-first search tree of $G$. Must the remaining vertices form a vertex cover of $G$? Give a proof or a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "Upon deleting all leaf nodes from a Depth-First Search tree, only edges between these deleted nodes are at risk of not being covered. Therefore the question reduces to whether or not there can be edges between leaf nodes. Edges between leaf nodes are not Tree Edges, since they do not define parent/child relations nor express the order of discovery during traversal. Nor are they Forward or Back Edges, which must point to ansestors or descendants. Therefore they are Cross Edges. These edges can only be present in directed graphs. **Therefore if $G$ is undirected, deleting the leaf nodes will result in a vertex cover.**\n",
    "\n",
    "Suppose $G$ is directed. Can there be cross edges between leaf nodes? Yes. A counterexample can be found in the book (Figure 5.14, weird since this is problem 5.14):\n",
    "\n",
    "![Skiena Fig 5-2](Figures/Skiena_Fig_5-4.png)\n",
    "\n",
    "The \"Cross Edges\" case on the right contains an edge between leaf nodes. A graph that has that search tree can be produced from the tree itself by making all the Tree Edges be directed downward. This shows that if the graph $G$ is directed, then deleting the leaf nodes from *any* DFS tree does not always produce a vertex cover."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Directed Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.24 [3]\n",
    "\n",
    "Adding a single directed edge to a directed graph can reduce the number of weakly connected components, but by at most how many components? What about the number of strongly connected components?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**Weakly connected components:** disjoint subsets of vertices such that *if all directed edges were replaced with undirected edges*, for any pair of vertices $(x,y)$ in the component, you could travel between $x$ and $y$ in either direction without leaving the component.\n",
    "\n",
    "Adding the edge $(x,y)$ connects all nodes previously connected with node $x$ with those connected with node $y$. If they were already connected, there is no change in the number of weakly connected components. If not, then 2 components are now 1, a reduction of 1.\n",
    "\n",
    "**Strongly connected components:** disjoint subsets of vertices such that for any pair of vertices $(x,y)$ in the component, you can travel between $x$ and $y$ in either direction without leaving the component; directed cycles are the smallest non-trivial strongly connected components.\n",
    "\n",
    "When addressing *strongly* connected components, it is important to note that the number of components ranges from $V$ to $1$, where $V$ is the number of vertices in the graph. Initially, each vertex is its own component, and as directed cycles are identified, the nodes in the cycle are merged into the same component. Therefore it is never the case that a graph has NO strongly connected components, but rather we say there are $V$ such components. In support of this convention is the fact that as the number of components decreases, the graph is increasingly connected. Therefore the lowest such possible number of connected components should refer to a maximally strongly connected graph. In keeping with this pattern, the minimally strongly connected graph has $V$ components and the maximally connected graph has $1$ component.\n",
    "\n",
    "Suppose we have a circle of $V$ vertices with edges along the perimeter all pointing in the same direction. This is a single strongly connected graph, since any vertex can be reached from any other simply by traversing around the circle. But suppose we remove one edge, essentially creating a directed line of vertices. Now for any pair of vertices $(x,y)$, either $x$ can be reached from $y$ or vice versa, but never both, since you can only travel in one direction and you never loop back. Therefore in this case there are $V$ strongly connected components (or 0 in the intuitive but erronious convention described above). Inserting back in the edge that was removed reduces the number of components from $V$ back down to 1, a reduction of $V-1$. Since $V$ is arbitrary, we see that adding a single directed edge can reduce the number of strongly connected components by *any* number greater than or equal to 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Articulation Vertices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.30 [3]\n",
    "\n",
    "Suppose $G$ is a connected undirected graph. An edge $e$ whose removal disconnects the graph is called a *bridge*. Must every bridge $e$ be an edge in a depth-first search tree of $G$? Give a proof or a counterexample."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "DFS labels edges as either Tree or Back, with only Tree edges being explicitly included in the search tree. Therefore an equivalent question is whether or not a bridge can be a Back edge.\n",
    "\n",
    "If $(y,x)$ is a Back edge, this means that $y$ was already a descendant of $x$, which in turn means there exists an alternate route from $x$ to $y$. Therefore deleting edge $(y,x)$ does not disconnect $x$ from $y$. So the edge cannot be a bridge.\n",
    "\n",
    "We have just shown that BACK implies NOT BRIDGE. This is logically equivalent to BRIDGE implies NOT BACK. And since every edge in a DFS search tree is either a Tree edge or Back edge, this means that BRIDGE implies TREE. In other words, yes, every bridge $e$ must be an edge in a depth-first search tree of $G$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interview Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 5.31 [3]\n",
    "\n",
    "Which data structures are used in depth-first and breath-first search?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Solution:*\n",
    "\n",
    "**Adjacency lists or matrices** to represent the graph.\n",
    "\n",
    "**Arrays** to record which nodes have been discovered, which have been processed, and the entry/exit times in the case of depth-first search, and to record the parent relationships for the search tree.\n",
    "\n",
    "A **queue** in the case of breadth-first search to organize the traversal order.\n",
    "\n",
    "DFS can be implemented with a **stack**, but instead should be implemented recursively."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}