Depth First Paths
“Depth First Search” is a more general term for any graph search algorithm that traverses a graph as deep as possible before backtracking.
- The term is used for several slightly different algorithms. For example:
- DFS may refer to the version from the previous lecture that doesn’t use any marks (and thus can get caught in a loop).
- DFS may refer to the version where vertices are marked.
- DFS may refer to a version where vertices are marked and source edges recorded (as in Depth First Paths).
- DFS may refer to other algorithms like the “topological sort algorithm” well discuss later in lecture.
And more!
space 分析可能是要考虑runtime的内存占用，因为DFS算法需要递归调用，每一次递归调用都会消耗一定的内存。
Graph Traversals
应该讲的是BFS
Topological Sorting
DFS, then reverse the order of the vertices.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
public class DepthFirstOrder {
private boolean[] marked;
private Stack<Integer> reversePostorder;
public DepthFirstOrder(Digraph G) {
reversePostorder = new Stack<Integer>();
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) { dfs(G, v); }
/**
* Perform DFS of all unmarked vertices.
* Note: Our algorithm earlier started at vertices with indegree zero. It turns out this
* algorithm works no matter where you start!
* */
}
private void dfs(Digraph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) { dfs(G, w); }
}
reversePostorder.push(v); // After each DFS is done, ‘visit’ vertex by putting on a stack.
}
public Iterable<Integer> reversePostorder()
{ return reversePostorder; }
}
|
now graph problem summary
本质上还是 DFS
Breadth First Search
“fringe”（边缘）通常指的是一个数据结构，用于存储等待处理的节点。see
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
...
private void bfs(Graph G, int s) {
Queue<Integer> fringe =
new Queue<Integer>();
fringe.enqueue(s); // set up starting vertex
marked[s] = true;
while (!fringe.isEmpty()) {
int v = fringe.dequeue();
/**
* for freshly dequeued vertex v, for each neighbor that is unmarked:
* Enqueue that neighbor to the fringe.
* Mark it.
* Set its edgeTo to v.
*/
for (int w : G.adj(v)) {
if (!marked[w]) {
fringe.enqueue(w);
marked[w] = true;
edgeTo[w] = v;
}
}
}
}
|
space 分析可能是要考虑runtime的内存占用，因为DFS算法需要递归调用，每一次递归调用都会消耗一定的内存。
DFS, then reverse the order of the vertices.
“fringe”（边缘）通常指的是一个数据结构，用于存储等待处理的节点。see
