图(2)—— 邻接矩阵表示法

图的存储结构

图的存储结构比较复杂，其复杂性主要表现在：

◆任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。

◆图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。

图的常用的存储结构有：邻接矩阵、邻接链表、十字链表、邻接多重表和边表，其中邻接矩阵和邻接链表是比较常用的表示方法。

邻接矩阵(数组)表示法

基本思想：对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。

1无向图的数组表示

(1)无权图的邻接矩阵

无向无权图G=(V，E)有n(n≧1)个顶点，其邻接矩阵是n阶对称方阵，如下图所示。其元素的定义如下：

(2)带权图的邻接矩阵

无向带权图G=(V，E)的邻接矩阵如下图所示。其元素的定义如下：

(3)无向图邻接矩阵的特性

◆邻接矩阵是对称方阵；

◆对于顶点vi，其度数是第i行的非0元素的个数；

◆无向图的边数是上(或下)三角形矩阵中非0元素个数。

2有向图的数组表示

(1)无权图的邻接矩阵

若有向无权图G=(V，E)有n(n≧1)个顶点，则其邻接矩阵是n阶对称方阵，如图7-7所示。元素定义如下：

(2)带权图的邻接矩阵

有向带权图G=(V，E)的邻接矩阵如图所示。其元素的定义如下：

⑶有向图邻接矩阵的特性

◆对于顶点vi，第i行的非0元素的个数是其出度OD(vi)；第i列的非0元素的个数是其入度ID(vi)。

◆邻接矩阵中非0元素的个数就是图的弧的数目。

邻接矩阵表示法

上一节讲了图的定义和基本概念，以及接口的定义，现在对上一节中的接口进行类的实现，如下。

MatrixEdge.java

package datastructure.graph;
/**
 * 邻接矩阵表示法表示的图
 * @author luoweifu
 *
 */
public class MatrixEdge extends Edge {
	private Object v1, v2;
	/**
	 * 构造函数
	 * @param weight 权值
	 */
	public MatrixEdge(double weight) {
		v1 = null;
		v2 = null;
		this.info = null;
		this.weight = weight;
	}
	/**
	 * 构造函数
	 * @param v1 第一个顶点
	 * @param v2 第二个顶点
	 * @param info 边的信息
	 * @param weight 权值
	 */
	public MatrixEdge( Object v1, Object v2, Object info, double weight ) {
		super(info, weight);
		this.v1 = v1;
		this.v2 = v2;
	}
	@Override
	public Object getFirstVertex() {
		return v1;
	}

	@Override
	public Object getSecondVertex() {
		return v2;
	}

	@Override
	public int compareTo(Object o) {
		Edge e = (Edge)o;
		if(this.weight > e.getWeight())
			return 1;
		else if(this.weight < e.getWeight())
			return -1;
		else
			return 0;
	}
	@Override
	public boolean equals(Object obj) {
		return ((Edge)obj).info.equals(info) &&  ((Edge)obj).getWeight() == this.weight;
	}
	@Override
	public String toString() {
		//return "边信息：" + info + "\t权值：" + weight + "\t顶点1:" + getFirstVertex() + "\t顶点2：" + getSecondVertex();
		return "" + weight;
	}
}

MatrixGraph.java

package datastructure.graph;

import datastructure.list.ArrayList;
import datastructure.list.List;
import datastructure.queue.ArrayQueue;
import datastructure.queue.Queue;
/**
 * 邻接矩阵法表示图
 * @author luoweifu 
 *
 */
public class MatrixGraph implements Graph {
	private static final int defaultSize = 10;
	private int maxLen;  //矩阵的最大长度
	private int edgeNum; //边的条数 
	private List vertexs;
	private Edge edges[][];
	
	private enum Visit{unvisited, visited};
	
	/**
	 * 构造函数
	 */
	public MatrixGraph() {
		maxLen = defaultSize;
		vertexs  = new ArrayList();
		edges = new MatrixEdge[maxLen][maxLen];
	}
	/**
	 * 构造函数
	 * @param vexs 顶点的数组
	 */
	public MatrixGraph(Object vexs[]) {
		maxLen = vexs.length;
		vertexs  = new ArrayList();
		edges = new MatrixEdge[maxLen][maxLen];
		for(int i=0; i<maxLen; i++) {
			vertexs.add(vexs[i]);
		}
	}
	@Override
	public void addEdge(Object v1, Object v2, double weight) {
		int i1 = vertexs.indexOf(v1);
		int i2 = vertexs.indexOf(v2);
		//System.out.println("i1: " + i1 + "  i2:" + i2);
		if(i1>=0 && i1<vertexs.size() && i2 >=0 && i2<vertexs.size()) {
			edges[i1][i2] = new MatrixEdge(v1, v2, null, weight);
			edgeNum ++;
		} else {
			throw new ArrayIndexOutOfBoundsException("顶点越界或对应的边不合法！");
		}
	}
	@Override
	public void addEdge(Object v1, Object v2, Object info, double weight) {
		int i1 = vertexs.indexOf(v1);
		int i2 = vertexs.indexOf(v2);
		if(i1>=0 && i1<vertexs.size() && i2 >=0 && i2<vertexs.size()) {
			edges[i1][i2] = new MatrixEdge( v1, v2, info, weight);
			edgeNum ++;
		} else {
			throw new ArrayIndexOutOfBoundsException("顶点越界或对应的边不合法！");
		}
	}
	@Override
	public void addVex(Object v) {
		vertexs.add(v);
		if(vertexs.size() > maxLen) {
			expand();
		}
	}
	private void expand() {
		MatrixEdge newEdges[][] = new MatrixEdge[2*maxLen][2*maxLen];
		for(int i=0; i<maxLen; i++) {
			for(int j=0; j<maxLen; j++) {
				newEdges[i][j] = (MatrixEdge) edges[i][j];
			}
		}
		edges = newEdges;
	}
	
	@Override
	public int getEdgeSize() {
		return edgeNum;
	}
	@Override
	public int getVertexSize() {
		return vertexs.size();
	}
	@Override
	public void removeEdge(Object v1, Object v2) {
		int i1 = vertexs.indexOf(v1);
		int i2 = vertexs.indexOf(v2);
		if(i1>=0 && i1<vertexs.size() && i2 >=0 && i2<vertexs.size()) {
			if(edges[i1][i2] == null) {
				try {
					throw new Exception("该边不存在！");
				} catch (Exception e) {
					e.printStackTrace();
				}
			} else {
				edges[i1][i2] = null;
				edgeNum --;
			}
		} else {
			throw new ArrayIndexOutOfBoundsException("顶点越界或对应的边不合法！");
		}
	}
	@Override
	public void removeVex(Object v) {
		int index = vertexs.indexOf(v);
		int n = vertexs.size();
		vertexs.remove(index);
		for(int i=0; i<n; i++){
			edges[i][n-1] = null;
			edges[n-1][i] = null;
		}
	}
	@Override
	public String printGraph() {
		StringBuilder sb = new StringBuilder();
		int n = getVertexSize();
		for (int i = 0; i < n; i++) {
			for(int j=0; j<n; j++) {
				sb.append("  " + edges[i][j]);
			}
			sb.append("\n");
		}
		return sb.toString();
	}
	@Override
	public void clear() {
		maxLen = defaultSize;
		vertexs.clear();
		edges = null;
	}
	@Override
	public String bfs(Object o) {
		Visit visit[] = new Visit[vertexs.size()];
		for(int i=0; i<vertexs.size(); i++)
			visit[i] = Visit.unvisited;
		StringBuilder sb = new StringBuilder();
		bfs(o, visit, sb);
		return sb.toString();
	}
	private void bfs(Object o, Visit[] visit, StringBuilder sb) {
		Queue queue = new ArrayQueue();
		
		int n = vertexs.indexOf(o);
		sb.append(o + "\t");
		visit[n] = Visit.visited;
		
		queue.push(o);
		while(!queue.isEmpty()) {
			Object u = queue.deQueue();
			Object v = getFirstVertex(u);
			while(null != v) {
				if(Visit.unvisited == visit[vertexs.indexOf(v)]) {
					sb.append(v + "\t");
					visit[vertexs.indexOf(v)] = Visit.visited;
					queue.push(v);
				}
				v = getNextVertex(u, v);
			}
		}
	}
	@Override
	public String dfs(Object o) {
		Visit visit[] = new Visit[vertexs.size()];
		for(int i=0; i<vertexs.size(); i++)
			visit[i] = Visit.unvisited;
		StringBuilder sb = new StringBuilder();
		dfs(o, visit, sb);
		return sb.toString();
	}
	private void dfs(Object o, Visit[] visit, StringBuilder sb) {
		int n = vertexs.indexOf(o);
		sb.append(o + "\t");
		visit[n] = Visit.visited;
		
		Object v = getFirstVertex(o);
		while(null != v) {
			if(Visit.unvisited == visit[vertexs.indexOf(v)])
				dfs(v, visit, sb);
			v = getNextVertex(o, v);
		}
	}
	@Override
	public Object getFirstVertex(Object v) {
		int i = vertexs.indexOf(v);
		if(i<0)
			throw new ArrayIndexOutOfBoundsException("顶点v不存在！");
		for(int col=0; col<vertexs.size(); col++)
			if(edges[i][col] != null)
				return vertexs.get(col);
		return null;
	}
	@Override
	public Object getNextVertex(Object v1, Object v2) {
		int i1 = vertexs.indexOf(v1);
		int i2 = vertexs.indexOf(v2);
		if(i1<0 || i2<0)
			throw new ArrayIndexOutOfBoundsException("顶点v不存在！");
		for(int col=i2+1; col<vertexs.size(); col++)
			if(edges[i1][col] != null)
				return vertexs.get(col);
		return null;
	}
}

测试程序Test.java

package datastructure.graph;

public class Test {

	public static void main(String args[]) {
		
		Object obj[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
		
		//Graph graph = new MatrixGraph(obj);
		Graph graph = new MatrixGraph(obj);

		//graph.addVex('F');
		graph.addEdge('A','C',5);
		graph.addEdge('B','A',2);
		graph.addEdge('C','B',15);
		graph.addEdge('E','D',4);
		graph.addEdge('F','E',18);
		graph.addEdge('A', 'F', 60);
		graph.addEdge('C', 'F', 70);
		System.out.println(graph.printGraph());
		/*graph.removeEdge('A', 'C');
		System.out.println(graph.printGraph());
		graph.removeVex('E');
		System.out.println(graph.printGraph());*/
		System.out.println(graph.dfs('A'));
		System.out.println(graph.bfs('A'));
	}
}