图的存储结构
图的存储结构比较复杂，其复杂性主要表现在：
◆ 任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。
◆ 图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。
图的常用的存储结构有：邻接矩阵、邻接链表、十字链表、邻接多重表和边表，其中邻接矩阵和邻接链表是比较常用的表示方法。
邻接矩阵(数组)表示法
基本思想：对于有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'));
}
}