无向图----无向图的实现

术语表：

• 多重图：将含有平行边的图称为多重图。
• 简单图：将没有平行边和自环的图称为简单图。
• 相邻：当两个顶点通过一条边相连时，称这两个顶点相邻，并称这条边依附于这两个顶点。
• 度数：一个顶点的度数即依附于它的边的总数。
• 简单路径：是一条没有重复顶点的路径。
• 简单环：是一条（除了起点和终点必须相同外）没有相同顶点的环。
• 路径或环的长度：其中所包含的边数。（有权无向图则为边的权重和）
• 连通图：从任一顶点能够达到另一个任意顶点。

无向图的API：

public class Graph Graph(int V)        创建一个含有V个顶点但不含有边的图 int V()        顶点数 int E()        边数 void addEdge(int v,int w)        向图中添加一条边v--w Iterable<Integer> adj(int v)        和v相邻的所有顶点 String toString()        对象的字符串表示

选用数据结构：

• 邻接矩阵：占用空间太大。对于含有上百万个顶点的图，V^2的空间需求是不能满足的。
• 邻接表数组：可以实现。使用一个以顶点为索引的列表数组，其中每个元素都是和该顶点相邻的顶点列表。

典型Graph实现的性能复杂度

使用邻接表实现Graph性能有如下特点：

• 使用的空间和V+E成正比
• 添加一条边所需要的时间为常数
• 遍历顶点v所需要的时间和v的度数成正比

邻接表的Java语言实现：

public class Graph {
	private int V;//顶点数
	private int E;//边数
	private Bag<Integer>[] adj;//邻接表
	public Graph(int V) {
		this.V = V;
		adj = (Bag<Integer>[]) new Bag[V];
		for(int i=0;i<adj.length;i++) {
			adj[i] = new Bag<Integer>();
		}
	}
	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];}
}

图处理算法的设计模式：

一般我们会将数据结构和基于数据结构的算法分离。为此，我们会为相关的任务创建相关的类，然后采用组合的方式，在算法类中组合使用数据结构类。在接下来的深度优先遍历和广度优先遍历中可以看到相关实现。