# 算法系列 图数据结构探索（无向图搜索）

#算法基础#选择和插入排序

```public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int s;

public DepthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = 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);
}
}
}

public boolean hasPathTo(int v) {
return marked[v];
}

public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}

public static void main(String[] args) {
Graph G = new Graph(new In(args[0]));
int s = Integer.parseInt(args[1]);
DepthFirstPaths search = new DepthFirstPaths(G, s);
for (int v = 0; v < G.V(); v++) {
StdOut.print(s + " to " + v + ": ");
if (search.hasPathTo(v)) {
for (int x : search.pathTo(v)) {
if (x == s) {
StdOut.print(x);
} else {
StdOut.print("-" + x);
}
}
}
StdOut.println();
}
}```

```public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private int[] distTo; // Add for Exercise 4.1.13
private final int s;

public BreadthFirstPaths(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
distTo = new int[G.V()]; // Add for Exercise 4.1.13
this.s = s;
bfs(G, s);
}

private void bfs(Graph G, int s) {
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
for (int v = 0; v < G.V(); v++) {
distTo[v] = Integer.MAX_VALUE;
}
distTo[s] = 0;
queue.enqueue(s);
while (!queue.isEmpty()) {
int v = queue.dequeue();
for (int w : G.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
marked[w] = true;
distTo[w] = distTo[v] + 1; // Add for Exercise 4.1.13
queue.enqueue(w);
}
}
}
}

public boolean hasPathTo(int v) {
return marked[v];
}

public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<Integer>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}

/**
* Exercise 4.1.13
*
* @param v
* @return
*/
public int distTo(int v) {
return distTo[v];
}

public static void main(String[] args) {
Graph G = new Graph(new In(args[0]));
int s = Integer.parseInt(args[1]);
for (int v = 0; v < G.V(); v++) {
StdOut.print(s + " to " + v + ": ");
if (search.hasPathTo(v)) {
for (int x : search.pathTo(v)) {
if (x == s) {
StdOut.print(x);
} else {
StdOut.print("-" + x);
}
}
}
StdOut.println();
}
}
}```

243 篇文章65 人订阅

0 条评论

## 相关文章

1523

3668

30912

3185

1373

1995

### java核心技术——Exception和Error的区别

Exception 和 Error 都是继承了 Throwable 类，在 Java 中只有 Throwable 类型的实例才可以被抛出（throw）或者...

1651

1973

1062

### Coroutine，你究竟干了什么？

使用Unity已经有一段时间了，对于Component、GameObject之类的概念也算是有所了解，而脚本方面从一开始就选定了C#，目前来看还是挺明智的：...

501