CS计算机代考程序代写 Java data structure algorithm Note

Note
This lecture is the last lecture in scope for Spring 2021 midterm 2.
datastructur.es

CS61B, 2021
Lecture 22: Graphs II: Graph Traversal Implementations
¡ñ BreadthFirstPaths
¡ñ Graph API
¡ñ Graph Representations and Graph Algorithm Runtimes
¡ñ Graph Traversal Runtimes
¡ñ Layers of Abstraction

Tree and Graph Traversals
Just as there are many tree traversals:
¡ñ Preorder: DBACFEG
¡ñ Inorder: ABCDEFG
¡ñ Postorder: ACBEGFD
¡ñ Level order: DBFACEG
D
B
AC
F
EG
3
6
7
datastructur.es
So too are there many graph traversals, given some source:
¡ñ DFS Preorder: 012543678 (dfs calls).
¡ñ DFS Postorder: 347685210 (dfs returns).
¡ñ BFS order: Act in order of distance from s.
s
0
1
4
¡ð BFS stands for ¡°breadth first search¡±.
¡ð Analogous to ¡°level order¡±. Search is wide, not deep.
¡ð 0 1 24 53 68 7
2
5
8

Shortest Paths Challenge
s
1
2
3
4
7
5
6
Goal: Given the graph above, find the shortest path from s to all other vertices.
¡ñ Give a general algorithm.
¡ñ Hint: You¡¯ll need to somehow visit vertices in BFS order.
¡ñ Hint #2: You¡¯ll need to use some kind of data structure.
¡ñ Hint #3: Don¡¯t use recursion.
0
datastructur.es

BFS Answer
Breadth First Search.
¡ñ Initialize a queue with a starting vertex s and mark that vertex.
¡ð A queue is a list that has two operations: enqueue (a.k.a. addLast) and
dequeue (a.k.a. removeFirst).
¡ð Let¡¯s call this the queue our fringe. A queue is the opposite of a stack. Stack
has push (addFirst) and pop (removeFirst).
¡ñ Repeat until queue is empty:
¡ð Remove vertex v from the front of the queue.
¡ð For each unmarked neighbor n of v:
¡ö Mark n.
¡ö Set edgeTo[n] = v (and/or distTo[n] = distTo[v] + 1).
¡ö Add n to end of queue.
Demo: Breadth First Paths
Do this if you want to track distance value.
datastructur.es

One use of BFS: Kevin Bacon
Graph with two types of vertices: ¡ñ Movies
¡ñ Actors
Perform BFS from s=Kevin Bacon.
datastructur.es

BreadthFirstSearch for Google Maps
Would breadth first search be a good algorithm for a navigation tool (e.g. Google Maps)?
¡ñ Assume vertices are intersection and edges are roads connecting intersections.
Some roads are longer than others. ¡ñ BAD!
Will discuss how to deal with this in the next lecture.
¡ñ First, we should talk about how graphs and graph algorithms are actually implemented in a programming language.
datastructur.es

Graph API

Graph Representations
To Implement our graph algorithms like BreadthFirstPaths and DepthFirstPaths, we need:
¡ñ An API (Application Programming Interface) for graphs.
¡ð For our purposes today, these are our Graph methods, including their
signatures and behaviors.
¡ð Defines how Graph client programmers must think.
¡ñ An underlying data structure to represent our graphs. Our choices can have profound implications on:
¡ñ Runtime.
¡ñ Memory usage.
¡ñ Difficulty of implementing various graph algorithms.
datastructur.es

Graph API Decision #1: Integer Vertices
Common convention: Number nodes irrespective of ¡°label¡±, and use number throughout the graph implementation. To lookup a vertex by label, you¡¯d need to use a Map.
Dallas
1
0
2
Map: Austin: 0
Dallas: 1
Houston: 2
Austin
Houston Intended graph.
How you¡¯d build it.
datastructur.es

Graph API
The Graph API from our optional textbook.
public class Graph {
public Graph(int V): Create empty graph with v vertices public void addEdge(int v, int w): add an edge v-w
Iterable adj(int v):
int V():
int E():
…
vertices adjacent to v
number of vertices
number of edges
Print client:
0 $ java printDemo 0 -1
31
2
0 -3 1 -0 1 -2 2 -1 3 -0
datastruct
public static void print(Graph G) {
for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + ¡°-¡± + w); } } } ur.es Graph API and DepthFirstPaths Our choice of Graph API has deep implications on the implementation of DepthFirstPaths, BreadthFirstPaths, print, and other graph ¡°clients¡±. ¡ñ Will come back to this in more depth, but first... datastructur.es Graph Representation and Graph Algorithm Runtimes Graph Representations To Implement our graph algorithms like BreadthFirstPaths and DepthFirstPaths, we need: ¡ñ An API (Application Programming Interface) for graphs. ¡ð For our purposes today, these are our Graph methods, including their signatures and behaviors. ¡ð Defines how Graph client programmers must think. ¡ñ An underlying data structure to represent our graphs. Our choices can have profound implications on: ¡ñ Runtime. ¡ñ Memory usage. ¡ñ Difficulty of implementing various graph algorithms. datastructur.es Graph Representations Just as we saw with trees, there are many possible implementations we could choose for our graphs. Let¡¯s review briefly some representations we saw for trees. datastructur.es Tree Representations We¡¯ve seen many ways to represent the same tree. Example: 1a. w w xyz z x y 1a: Fixed Number of Links (One Per Child) datastructur.es Tree Representations We¡¯ve seen many ways to represent the same tree. Example: 3. Key[] keys 3: Array of Keys w xyz w x y z Uses much less memory and operations will tend to be faster. ... but only works for complete trees. datastructur.es Graph Representations Graph Representation 1: Adjacency Matrix. t s 0 1 2 0 0 1 1 1 0 0 1 2 0 0 0 1 0 2 w v 0 1 2 3 0 0 1 0 0 1 1 0 1 0 2 0 1 0 1 3 0 0 1 0 For undirected graph: Each edge is represented twice in the matrix. Simplicity at the expense of space. 1 0 3 2 datastructur.es Graph Representations Graph Representation 1: Adjacency Matrix. ¡ñ G.adj(2) would return an iterator where we can call next() up to two times ¡ð next() returns 1 ¡ð next() returns 3 ¡ñ Total runtime to iterate over all neighbors of v is ¦¨(V). ¡ð Underlying code has to iterate through entire array to handle next() and hasNext() calls. w v 0 1 2 3 0 0 1 0 0 1 1 0 1 0 2 0 1 0 1 3 0 0 1 0 G.adj(2) returns an iterator that will ultimately provide 1, then 3. 1 0 3 2 datastructur.es Graph Printing Runtime: http://yellkey.com/allow What is the order of growth of the running time of the print client from before if the graph uses an adjacency-matrix representation, where V is the number of vertices, and E is the total number of edges? for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + ¡°-¡± + w); } } 0 1 2 3 0 0 1 0 0 1 1 0 1 0 2 0 1 0 1 3 0 0 1 0 A. ¦¨(V) B. ¦¨(V + E) C. ¦¨(V2) D. ¦¨(V*E) Runtime to iterate over v¡¯s neighbors? ¡ñ How many vertices do we consider? ¡ñ 1 0 3 2 datastructur.es Graph Printing Runtime: http://yellkey.com/allow What is the order of growth of the running time of the print client from before if the graph uses an adjacency-matrix representation, where V is the number of vertices, and E is the total number of edges? for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + ¡°-¡± + w); } } 0 1 2 3 0 0 1 0 0 1 1 0 1 0 2 0 1 0 1 3 0 0 1 0 A. ¦¨(V) B. ¦¨(V + E) C. ¦¨(V2) D. ¦¨(V*E) Runtime to iterate over v¡¯s neighbors? ¡ñ ¦¨(V). How many vertices do we consider? ¡ñ V times. 1 0 3 2 datastructur.es More Graph Representations Representation 2: Edge Sets: Collection of all edges. ¡ñ Example: HashSet, where each Edge is a pair of ints.
{(0, 1), (0, 2), (1, 2)}
1
0
2
datastructur.es

More Graph Representations
Representation 3: Adjacency lists.
¡ñ Common approach: Maintain array of lists indexed by vertex number.
1
0
2
¡ñ Most popular approach for representing graphs.
[1, 2] 1 [2]
0 2
datastructur.es

Graph Printing Runtime: http://yellkey.com/just
What is the order of growth of the running time of the print client if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges?
for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + ¡°-¡± + w); } } A. ¦¨(V) B. ¦¨(V + E) C. ¦¨(V2) D. ¦¨(V*E) Runtime to iterate over v¡¯s neighbors? ¡ñ How many vertices do we consider? ¡ñ 0 [1, 2] 1 [2] 2 b a c datastructur.es Graph Printing Runtime: http://yellkey.com/just What is the order of growth of the running time of the print client if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges? Best case: ¦¨(V) Worst case: ¦¨(V2) A. ¦¨(V) B. ¦¨(V + E) C. ¦¨(V2) D. ¦¨(V*E) for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + ¡°-¡± + w); } } Runtime to iterate over v¡¯s neighbors? List can be between 1 and V items. ¡ñ ¦¸(1), O(V). How many vertices do we consider? ¡ñ V. 0 [1, 2] 1 [2] 2 b a c datastructur.es Graph Printing Runtime: http://yellkey.com/effort What is the order of growth of the running time of the print client if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges? Best case: ¦¨(V) Worst case: ¦¨(V2) for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + ¡°-¡± + w); } } A. ¦¨(V) B. ¦¨(V + E) C. ¦¨(V2) D. ¦¨(V*E) ? ? ? Runtime to iterate over v¡¯s neighbors? List can be between 0 and V items. ? ¡ñ ¦¸(1), O(V). ? How many vertices do we consider? ¡ñ V. 0 [1, 2] 1 [2] 2 b a c datastructur.es Graph Printing Runtime: http://yellkey.com/effort What is the order of growth of the running time of the print client if the graph uses an adjacency-list representation, where V is the number of vertices, and E is the total number of edges? for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + ¡°-¡± + w); } } A. ¦¨(V) B. ¦¨(V + E) C. ¦¨(V2) D. ¦¨(V*E) Best case: ¦¨(V) All cases: ¦¨(V + E) 0 1 2 [1, 2] [2] b a c Worst case: ¦¨(V2) ¡ñ Create V iterators. ¡ñ Print E times. datastructur.es Graph Printing Runtime Runtime: ¦¨(V + E) V is total number of vertices. E is total number of edges in the entire graph. How to interpret: No matter what ¡°shape¡± of increasingly complex graphs we generate, as V and E grow, the runtime will always grow exactly as ¦¨(V + E). ¡ñ Example shape 1: Very sparse graph where E grows very slowly, e.g. every vertex is connected to its square: 2 - 4, 3 - 9, 4 - 16, 5 - 25, etc. ¡ð E is ¦¨(sqrt(V)). Runtime is ¦¨(V + sqrt(V)), which is just ¦¨(V). ¡ñ Example shape 2: Very dense graph where E grows very quickly, e.g. every vertex connected to every other. ¡ð E is ¦¨(V2). Runtime is ¦¨(V + V2), which is just ¦¨(V2). for (int v = 0; v < G.V(); v += 1) { for (int w : G.adj(v)) { System.out.println(v + ¡°-¡± + w); } } datastructur.es Graph Representations Runtime of some basic operations for each representation: idea addEdge(s, t) for(w : adj(v)) print() hasEdge(s, t) space used adjacency matrix ¦¨(1) ¦¨(V) ¦¨(V2) ¦¨(1) ¦¨(V2) list of edges ¦¨(1) ¦¨(E) ¦¨(E) ¦¨(E) ¦¨(E) adjacency list ¦¨(1) ¦¨(1) to ¦¨(V) ¦¨(V+E) ¦¨(degree(v)) ¦¨(E+V) In practice, adjacency lists are most common. ¡ñ Many graph algorithms rely heavily on adj(s). ¡ñ Most graphs are sparse (not many edges in each bucket). Note: These operations are not part of the Graph class¡¯s API. datastructur.es Bare-Bones Undirected Graph Implementation Cannot create array of anything involving generics, so have to use weird cast as with project 1A. datastructur.es public class Graph { private final int V; private List[] adj;
public Graph(int V) { this.V = V;
adj = (List[]) new ArrayList[V]; for (int v = 0; v < V; v++) { adj[v] = new ArrayList(); }
}
public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v);
}
public Iterable adj(int v) { return adj[v];
} }

Graph Traversal Implementations and Runtime

Depth First Search Implementation
Common design pattern in graph algorithms: Decouple type from processing algorithm.
¡ñ Create a graph object.
¡ñ Pass the graph to a graph-processing method (or constructor) in a client
class.
¡ñ Query the client class for information.
public class Paths {
public Paths(Graph G, int s): Find all paths from G boolean hasPathTo(int v): is there a path from s to v? Iterable pathTo(int v): path from s to v (if any)
}
Paths.java
datastructur.es

Example Usage
Start by calling: Paths P = new Paths(G, 0);
¡ñ P.hasPathTo(3); //returns true
¡ñ P.pathTo(3); //returns {0, 1, 4, 3}
Paths.java
public class Paths {
public Paths(Graph G, int s): Find all paths from G boolean hasPathTo(int v): is there a path from s to v? Iterable pathTo(int v): path from s to v (if any)
}
datastructur.es

DepthFirstPaths
Let¡¯s review DepthFirstPaths by running the demo again. Will then discuss:
¡ñ Implementation. ¡ñ Runtime.
datastructur.es

DepthFirstPaths, Recursive Implementation
public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private int s;
public DepthFirstPaths(Graph G, int s) { …
dfs(G, s); }
private void dfs(Graph G, int v) { marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) { edgeTo[w] = v; dfs(G, w);
} }
} …
}
marked[v] is true iff v connected to s
edgeTo[v] is previous vertex on path from s to v
not shown: data structure initialization find vertices connected to s.
recursive routine does the work and stores results in an easy to query manner!
Question to ponder: How would we write pathTo(v) and hasPathTo(v)?
¡ñ Answer on next slide. datastructur.es

DepthFirstPaths, Recursive Implementation
public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private int s;
…
public Iterable pathTo(int v) {
if (!hasPathTo(v)) return null; List path = new ArrayList<>(); for (int x = v; x != s; x = edgeTo[x]) {
path.add(x);
}
path.add(s);
Collections.reverse(path);
return path;
}
public boolean hasPathTo(int v) { return marked[v];
} }
marked[v] is true iff v connected to s
edgeTo[v] is previous vertex on path from s to v
datastructur.es

Runtime for DepthFirstPaths
Give a O bound for the runtime for the DepthFirstPaths constructor.
public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private int s;
public DepthFirstPaths(Graph G, int s) { …
dfs(G, s); }
private void dfs(Graph G, int v) { marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) { edgeTo[w] = v; dfs(G, w);
} }
} … }
Assume graph uses adjacency list!
datastructur.es

Runtime for DepthFirstPaths
Give a O bound for the runtime for the DepthFirstPaths constructor. O(V + E)
¡ñ Each vertex is visited at most once (O(V)).
¡ñ Each edge is considered at most twice (O(E)).
vertex visits (no more than V calls)
edge considerations, each constant time (no more than 2E calls)
Cost model in analysis above is the sum of:
¡ñ Number of dfs calls.
¡ñ marked[w] checks.
public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private int s;
public DepthFirstPaths(Graph G, int s) { …
dfs(G, s); }
private void dfs(Graph G, int v) { marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) { edgeTo[w] = v; dfs(G, w);
} }
} … }
Assume graph uses adjacency list!
datastructur.es

Various Cost Models for DFS
Four cost models for DFS:
¡ñ Number of DFS calls: O(V)
¡ð Is an underestimate for families of graphs with tons of edges, e.g. we
have genGraph(N) with N vertices and an edge between all pairs of
vertices. Runtime would be worse than V.
¡ñ Number of DFS + marked checks: O(V + E), but can simplify to O(E)
¡ð Also underestimates for families of graphs with very few edges. ¡ñ Number of marked checks: O(E)
¡ð Is an underestimate for families of graphs with very few edges. So imagine, we have genGraph(N) which generates a graph with N nodes and sqrt(N) edges. As N grows, runtime would be worse than E.
¡ñ Initialization of marked to false + marked checks: O(V + E) ¡ð This one does not underestimate.
We never formally defined asymptotics on multiple variables, and it turns out to datastructur.es

Runtime for DepthFirstPaths
Very hard question: Could we say the runtime is O(E)?
Argument: Can only visit a vertex if there is an edge to it.
¡ñ # of DFS calls is bounded above by E.
¡ñ So why not just say O(E)?
public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private int s;
public DepthFirstPaths(Graph G, int s) { …
dfs(G, s); }
private void dfs(Graph G, int v) { marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) { edgeTo[w] = v; dfs(G, w);
} }
} … }
Assume graph uses adjacency list!
datastructur.es

Runtime for DepthFirstPaths
Very hard question: Could we say the runtime is O(E)? No. Can¡¯t say O(E)!
¡ñ Constructor has to create an all false marked array.
¡ñ This marking of all vertices as false takes ¦¨(V) time.
Our cost model earlier (dfs calls + marked checks) does not provide a tight bound.
public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private int s;
public DepthFirstPaths(Graph G, int s) { …
dfs(G, s); }
private void dfs(Graph G, int v) { marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) { edgeTo[w] = v; dfs(G, w);
} }
} … }
Assume graph uses adjacency list!
datastructur.es

Graph Problems
Problem
Problem Description
Solution
Efficiency (adj. list)
s-t paths
Find a path from s to every reachable vertex.
DepthFirstPaths.java Demo [update]
O(V+E) time ¦¨(V) space
Runtime is O(V+E)
¡ñ Based on cost model: O(V) dfs calls and O(E) marked[w] checks.
¡ñ Can¡¯t say O(E) because creating marked array
¡ñ Note, can¡¯t say ¦¨(V+E), example: Graph with no edges touching source.
Space is ¦¨(V).
¡ñ Need arrays of length V to store information.
datastructur.es

BreadthFirstPaths Implementation
marked[v] is true iff v connected to s
edgeTo[v] is previous vertex on path from s to v
set up starting vertex
for freshly dequeued vertex v, for each neighbor that is unmarked:
¡ñ Enqueue that neighbor to the fringe.
¡ñ Mark it.
¡ñ Set its edgeTo to v.
datastructur.es
public class BreadthFirstPaths { private boolean[] marked; private int[] edgeTo;
…
private void bfs(Graph G, int s) { Queue fringe =
new Queue(); fringe.enqueue(s);
marked[s] = true;
while (!fringe.isEmpty()) {
int v = fringe.dequeue(); for (int w : G.adj(v)) {
if (!marked[w]) { fringe.enqueue(w); marked[w] = true; edgeTo[w] = v;
} }
} }

Graph Problems
Problem
Problem Description
Solution
Efficiency (adj. list)
s-t paths
Find a path from s to every reachable vertex.
DepthFirstPaths.java
Demo
O(V+E) time ¦¨(V) space
s-t shortest paths
Find a shortest path from s to every reachable vertex.
BreadthFirstPaths.java
Demo
O(V+E) time ¦¨(V) space
Runtime for shortest paths is also O(V+E)
¡ñ Based on same cost model: O(V) .next() calls and O(E) marked[w] checks.
Space is ¦¨(V).
¡ñ Need arrays of length V to store information.
datastructur.es

Layers of Abstraction

Clients and Our Graph API
Our choice of Graph API has deep implications on the implementation of DepthFirstPaths, BreadthFirstPaths, print, and other graph ¡°clients¡±.
datastructur.es

Our Graph API and Implementation
Our choice of how to implement the Graph API has profound implications on runtime.
¡ñ Example: Saw that DepthFirstPaths on Adjacency Lists was O(V + E).
datastructur.es

Our Graph API and Implementation
Our choice of how to implement the Graph API has profound implications on runtime.
¡ñ What happens if to DepthFirstPaths runtime if we use an adjacency matrix?
datastructur.es

Runtime for DepthFirstPaths
Give a tight O bound for the runtime for the DepthFirstPaths constructor.
public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private int s;
public DepthFirstPaths(Graph G, int s) { …
dfs(G, s); }
private void dfs(Graph G, int v) { marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) { edgeTo[w] = v; dfs(G, w);
} }
} …
}
Assume graph uses adjacency matrix!
datastructur.es

Runtime for DepthFirstPaths
Give a tight O bound for the runtime for the DepthFirstPaths constructor. O(V2)
¡ñ In the worst case, we iterate over the neighbors of all vertices.
public class DepthFirstPaths { private boolean[] marked; private int[] edgeTo; private int s;
public DepthFirstPaths(Graph G, int s) { …
dfs(G, s); }
private void dfs(Graph G, int v) { marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) { edgeTo[w] = v; dfs(G, w);
} }
} …
}
Assume graph uses adjacency matrix!
We create ¡Ü V iterators.
¡ñ Each one takes a total of ¦¨
(V) time to iterate over.
Essentially, iterating over the entire adjacency matrix takes O(V2) time.
datastructur.es

Graph Problems for Adjacency Matrix Based Graphs
Problem
Problem Description
Solution
Efficiency (adj. matrix)
s-t paths
Find a path from s to every reachable vertex.
DepthFirstPaths.java
Demo
O(V2) time ¦¨(V) space
s-t shortest paths
Find a shortest path from s to every reachable vertex.
BreadthFirstPaths.java
Demo
O(V2) time ¦¨(V) space
If we use an adjacency matrix, BFS and DFS become O(V2).
¡ñ For sparse graphs (number of edges << V for most vertices), this is terrible runtime. ¡ñ Thus, we¡¯ll always use adjacency-list unless otherwise stated. datastructur.es Summary Summary BFS: Uses a queue instead of recursion to track what work needs to be done. Graph API: We used the Princeton algorithms book API today. ¡ñ This is just one possible API. We¡¯ll see other APIs in this class. ¡ñ Choice of API determines how client needs to think in order to write code. ¡ð e.g. Getting the degree of a vertex requires many lines of code with this choice of API. ¡ð Choice may also affect runtime and memory of client programs. public class Graph { public Graph(int V): Create empty graph with v vertices public void addEdge(int v, int w): add an edge v-w Iterable adj(int v):
int V():
int E():
vertices adjacent to v
number of vertices
number of edges … datastructur.es

Summary
Graph Implementations: Saw three ways to implement our graph API.
¡ñ Adjacency matrix.
¡ñ List of edges.
¡ñ Adjacency list (most common in practice).
Choice of implementation has big impact on runtime and memory usage!
¡ñ DFS and BFS runtime with adjacency list: O(V + E)
¡ñ DFS and BFS runtime with adjacency matrix: O(V2)
datastructur.es

Citations
http://www.gosidemount.com/Guided_Diving/images/guided_cavern.jpg
datastructur.es

Live Lecture Exercise

Switching Things Up
Breadth First Search.
¡ñ Initialize a queue with a starting vertex s and mark that vertex.
¡ð A queue is a list that has two operations: enqueue (a.k.a. addLast) and
dequeue (a.k.a. removeFirst).
¡ð Let¡¯s call this the queue our fringe.
¡ñ Repeat until queue is empty:
¡ð Remove vertex v from the front of the queue.
¡ð For each unmarked neighbor n of v:
¡ö Mark n.
¡ö Set edgeTo[n] = v (and/or distTo[n] = distTo[v] + 1).
¡ö Add n to end of queue.
Demo: Breadth First Paths
Do this if you want to track distance value.
datastructur.es

Switching Things Up
??? First Search.
¡ñ Initialize a queuestack with a starting vertex s and mark that vertex.
¡ð A stack is a list that has two operations: push (a.k.a. addLast) and pop
(a.k.a. removeLast).
¡ð Let¡¯s call this the queuestack our fringe.
¡ñ Repeat until queue is empty:
¡ð Pop vertex v from the top of the stack.
¡ð For each unmarked neighbor n of v:
¡ö Mark n.
¡ö Set edgeTo[n] = v (and/or distTo[n] = distTo[v] + 1).
¡ö Push n to the top of of the queuestack.
datastructur.es

Try running ??? first search. Assume adjacency lists are in numerical order. ¡ñ Dives down a rabbit hole. Then makes its way back.
¡ð Depth first!!
??? First Search Visit Order: []
Stack:
0
3
6
7
0
1
4
s
2
5
8
datastructur.es

Try running ??? first search. Assume adjacency lists are in numerical order. ¡ñ Dives down a rabbit hole. Then makes its way back.
¡ð Depth first!!
??? First Search Visit Order: [0]
Stack:
3
6
7
0
s
1
4
2
5
8
datastructur.es

Try running ??? first search. Assume adjacency lists are in numerical order. ¡ñ Dives down a rabbit hole. Then makes its way back.
¡ð Depth first!!
??? First Search Visit Order: [0, 1]
Stack:
3
6
7
0
s
1
4
2
5
8
datastructur.es

Try running ??? first search. Assume adjacency lists are in numerical order. ¡ñ Dives down a rabbit hole. Then makes its way back.
¡ð Depth first!!
5
3
2
??? First Search Visit Order: [0, 1, 4]
Stack:
3
6
7
0
1
4
s
2
5
8
datastructur.es

Try running ??? first search. Assume adjacency lists are in numerical order. ¡ñ Dives down a rabbit hole. Then makes its way back.
¡ð Depth first!!
8
6
3
2
??? First Search Visit Order: [0, 1, 4, 5]
Stack:
3
6
7
0
s
1
4
5
2
8
datastructur.es

Try running ??? first search. Assume adjacency lists are in numerical order. ¡ñ Dives down a rabbit hole. Then makes its way back.
¡ð Depth first!!
6
3
2
??? First Search Visit Order: [0, 1, 4, 5, 8]
Stack:
3
6
0
1
4
s
5
2
7
*
8
datastructur.es

Try running ??? first search. Assume adjacency lists are in numerical order. ¡ñ Dives down a rabbit hole. Then makes its way back.
¡ð Depth first!!
3
7
3
2
??? First Search Visit Order: [0, 1, 4, 5, 8, 6]
Stack:
0
1
4
6
s
5
2
7
8
datastructur.es

Try running ??? first search. Assume adjacency lists are in numerical order. ¡ñ Dives down a rabbit hole. Then makes its way back.
¡ð Depth first!!
3
??? First Search Visit Order: [0, 1, 4, 5, 8, 6, 7]
Stack:
0
1
4
6
3
2
s
5
7
2
8
datastructur.es

Try running R???R first search, which uses reverse order of adjacency lists. ¡ñ In other words, 5¡¯s adjacency list is: 2->4->6->8, so let¡¯s do it backwards
¡ñ EVEN THIS IS NOT classic DFS
??? First Search Visit Order: [0, 1, 4, 5, 8, 6, 7, 3, 2]
R???R First Search Visit Order:
[0, 1, 2, 5, 6 RRRHRHH (buzzer sound)]
DFS (Pre-order):
[0, 1, 2, 5, 4, 3, 6, 7, 8]
3
0
1
4
6
Stack:
s
5
7
2
8
datastructur.es

Interesting fact:
¡ñ ANY recursive algorithm can be implemented using iteration and a stack.
¡ñ So DFS (which we implemented recursively) can be implemented using a
stack data structure.
¡ð So far we¡¯ve uncovered ??? first search and R???R first search.
¡ð These two algorithms are close cousins of
DFS-breaking-ties-alphabetically search, but are NOT quite the same.
¡ð R???R is a closer cousin.
¡ð Tweaking the algorithm so that our iterative algorithm yields the exact
same output as our recursive one will require more work.
In 61C, you¡¯ll learn how recursive calls are implemented at a low level using a stack, i.e. in REAL recursive code, there is an explicit stack being utilized (but below the level of abstraction that you usually think about).
datastructur.es

Related Posts