1、无向图的API
| public class | Graph | |
|---|---|---|
| Graph(int V) | 创建一个含有V个顶点但不含有边的无向图 | |
| Graph(In in) | 从标准输入流in读入一幅图 | |
| int | V() | 顶点数 |
| int | E() | 边数 |
| void | addEdge(int v, int w) | 向图中添加一条边v-w |
| Iterable<Integer> | adj(int v) | 和v相邻的所有顶点 |
| String | toString() | 对象的字符串表示 |
2、Graph的数据结构
/**
* 类说明
* 无向图数据类型
* @author Zoye
* @date 2018年7月5日 新建
*/
public class Graph {
private final int V; // 顶点数目
private int E; // 边的数目
private Bag<Integer>[] adj;
public Graph(int V) {
this.V = V; this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for(int v = 0; v < V; v++)
adj[v] = new Bag<Integer>();
}
public Graph(In in) {
this(in.readInt());
this.E = in.readInt();
for(int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
addEdge(v, w);
}
}
public int V() { return V; }
public int E() { return E; }
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
3、深度优先搜索
在访问一个顶点时：
- 将它标记为已访问；
- 递归地访问它的所有没有被标记过的邻居顶点。
命题A。深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。
4、寻找路径
4.1 路径的API
| public class | Paths | |
|---|---|---|
| Paths(Graph G, int s) | 在G中找出所有起点为s的路径 | |
| boolean | hasPathTo(int v) | 是否存在从s到v的路径 |
| Iterable<Integer> | pathTo(int v) | s到v的路径，如果不存在则返回null |
4.2 实现
算法4.1 使用深度优先搜索查找图中的路径
/**
* 类说明
* 使用深度优先搜索的应用：查找从s点出发的所有路径
* @author Zoye
* @date 2018年7月5日 新建
*/
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 w) {
return marked[w];
}
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;
}
}
5、广度优先搜索
5.1 实现
它使用了一个队列来保存所有已经被标记过但邻接表还未被检查过得顶点。先将起点加入队列，然后重复以下步骤直到队列为空：
- 取队列中的下一个顶点v并标记它；
- 将与v相邻的所有未被标记过的顶点加入队列。
算法4.2 使用广度优先搜索查找图中的路径
/**
* 类说明
* 使用宽度优先搜索查找最短路劲
* @author Zoye
* @date 2018年7月5日 新建
*/
public class BreadthFirstPath {
private boolean[] marked;
private int[] edgeTo;
private final int s;
public BreadthFirstPath(Graph G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G, s);
}
private void bfs(Graph G, int s) {
marked[s] = true;
Queue<Integer> queue = new Queue<Integer>();
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;
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;
}
}
命题B。对于s可达的任意顶点v，广度优先搜索都能找到一条从s到v的最短路径（没有其他从s到v的路径所含的边比这条路径更少）。
命题B（续）。广度优先搜索所需的时间在最坏情况下和V+E成正比。
6、连通分量
深度优先搜索的直接应用：找出一幅图的连通分量。
连通分量的API
| public class CC | ||
|---|---|---|
| CC(Graph G) | 预处理构造函数 | |
| boolean | connected(int v, int w) | v和w连通吗 |
| int | count() | 连通分量数 |
| int | id(int v) | v所在的连通分量的标识符（0——count()-1） |
6.1 实现
使用marked[]数组来寻找一个顶点作为每个连通分量中深度优先搜索的起点。
使用id[]数组将同一个连通分量中的顶点和连通分量的标识符关联起来（int值）。
算法4.3 使用深度优先搜索找出图中的所有连通分量
import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.introcs.StdOut;
/**
* 类说明
* 使用深度优先搜索的应用：查找连通分量
* @author Zoye
* @date 2018年7月5日 新建
*/
public class CC {
private boolean[] marked;
private int[] id; // v所在连通分量的标识符
private int count; // 连通分量数
public CC(Graph G) {
marked = new boolean[G.V()];
id = new int[G.V()];
for(int s = 0; s < G.V(); s++) {
if(!marked[s]) {
dfs(G, s); // 使用深度优先搜索查找该顶点的路径，并将其标记
count++; // 更新标记
}
}
}
private void dfs(Graph G, int v) {
marked[v] = true;
id[v] = count;
for(int w : G.adj(v))
if(!marked[w])
dfs(G, w);
}
public boolean connected(int v, int w) {
return id[v] == id[w];
}
public int id(int v) {
return id[v];
}
public int count() {
return count;
}
public static void main(String[] args) {
Graph G = new Graph(new In(args[0]));
CC cc = new CC(G);
int M = cc.count();
StdOut.println(M + " components");
Bag<Integer>[] components;
components = (Bag<Integer>[]) new Bag[M];
for (int i = 0; i < M; i++) {
components[i] = new Bag<Integer>();
}
for (int v = 0; v < G.V(); v++) {
components[cc.id(v)].add(v);
}
for (int i = 0; i < M; i++) {
for (int v : components[i]) {
StdOut.print(v + " ");
}
StdOut.println();
}
}
}
命题C。深度优先搜索的预处理使用的时间和空间与V+E成正比而且可以在常数时间内处理关于图的连通性查询。
7、符号图
用符号作为顶点名的图的API
| public class | SymbolGraph | |
|---|---|---|
| SymbolGraph(String filename, String delim) | 根据filename制定的文件构造图，使用delim来分隔顶点名 | |
| boolean | contains(String key) | key是一个顶点吗 |
| int | index(String key) | key的索引 |
| String | name(int v) | 索引v的顶点名 |
| Graph | G() | 隐藏的Graph对象 |
7.1 实现
使用以下3种数据结构：
- 一个符号表st，键的类型为String（顶点名），值的类型为int（索引）；
- 一个数组keys[]，用作反向索引，保存每个顶点索引所对应的顶点名；
- 一个Graph对象G，它使用索引来引用图中的顶点。
SymbolGraph会遍历两遍数据来构造以上数据结构，这主要是因为构造Graph对象需要顶点总数V。
符号图的数据类型
import edu.princeton.cs.algs4.ST;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.introcs.In;
import edu.princeton.cs.introcs.StdIn;
/**
* 类说明
* 用符号作为顶点名的图
* @author Zoye
* @date 2018年7月5日 新建
*/
public class SymbolGraph {
private ST<String, Integer> st; // 符号名->索引
private String[] keys; // 索引->符号名
private Graph G; // 图
public SymbolGraph(String stream, String sp) {
st = new ST<String, Integer>();// 第一遍读取文件,建立符号表
In in = new In(stream);
while(in.hasNextLine()) {
String[] a = in.readLine().split(sp);
for(int i = 0; i < a.length; i++)
if(!st.contains(a[i])) st.put(a[i], st.size());
}
keys = new String[st.size()]; // 建立反向索引
for(String name : st.keys())
keys[st.get(name)] = name;
G = new Graph(st.size()); // 第二遍读取文件,建立图
in = new In(stream);
while(in.hasNextLine()) {
String[] a = in.readLine().split(sp);
int v = st.get(a[0]);
for(int i = 1; i < a.length; i++)
G.addEdge(v, st.get(a[i]));
}
}
public boolean contains(String key) { return st.contains(key); }
public int index(String key) { return st.get(key); }
public String name(int v) { return keys[v]; }
public Graph G() { return G; }
public static void main(String[] args) {
String filename = args[0];
String delim = args[1];
SymbolGraph sg = new SymbolGraph(filename, delim);
Graph G = sg.G();
while(StdIn.hasNextLine()) {
String source = StdIn.readLine();
for(int w : G.adj(sg.index(source)))
StdOut.println(" " + sg.name(w));
}
}
}
