无向图

含有平行边（连接同一对顶点的两条边）的图称为多重图，而将没有平行边或自环（一条连接一个顶点及其自身的边）的图称为简单图。

1.1 术语

某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。

在图中，路径是由边顺序组成的一系列顶点。简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径。简单环是一条不含重复顶点（除了起点和终点）和边的环。路径或者环的长度为其中包含的边数。

当两个顶点存在一条连通双方的路径时，称这两个点是连通的。

如果从任意一个顶点都存在一条路径到达任一个任意节点，称为连通图。一个非连通的图由若干个连通的部分组成，它们都是极大连通子图。

树是一个无环连通图。互不相连的树组成的集合称为森林。连通图生成树是它的一个子图，它含有图中所有顶点且是一棵树。图的生成树森林是它所有连通子图的生成树集合。

当且仅当一个含有V个节点的图G含有以下条件之一时，它就是一棵树：

G有V-1条边且不含有环。

G有V-1条边且是连通的。

G是连通的，但删除一条边都会使它不再连通。

G是无环图，但添加任意一条边都会产生一个环。

G中任意一个顶点之间仅存在一条简单路径。

图的密度是已经连接的顶点对占所有可能被连接的顶点对的比例。

二分图是一种能够将所有节点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。

1.2 深度优先搜索（DFS）

在访问其中一个节点时，将它标记为已访问，递归地访问它的所没有被标记的邻节点。这种方法被称为深度优先搜索。

深度优先搜索标记与起点连通的所有顶点所需的时间与顶点的度数之和成正比。

1.4 寻找路径

1.5 广度优先搜索

public class BreadthFirstPaths {
	private boolean[] marked;    // 到达该顶点的最短路径是否已知
	private int[] edgeTo;    //到达该顶点的已知路径上的最后一个顶点
	private final int s;    //起点

	public BreadthFirstPaths(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) {
		Queue<Integer> queue = new Queue<>();
		marked[s] = true;    // 标记起点
		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) {
		// 与上面深度优先搜索相同
	}
}

对于从s可达的任意顶点v，广度优先搜索都能找到一条从s到v的最短路径。

广度优先搜索所需的时间在最坏情况下和V+E成正比。

1.6 连通分量

以下代码是使用深度搜索找到图中所有连通分量：

public class CC {
	private boolean[] marked;    // 到达该顶点的最短路径是否已知
	private int[] id;    
	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[s] = 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;
	}
}