文档章节

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

自由的角马
 自由的角马
发布于 2015/01/10 13:57
字数 1577
阅读 25
收藏 1

 图的存储结构

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

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

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

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

  邻接矩阵(数组)表示法

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

1无向图的数组表示

(1)  无权图的邻接矩阵

无向无权图G=(VE)n(n1)个顶点,其邻接矩阵是n阶对称方阵,如下图所示。其元素的定义如下:

(2)  带权图的邻接矩阵

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

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

 ◆ 邻接矩阵是对称方阵;

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

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

2有向图的数组表示

(1)  无权图的邻接矩阵

若有向无权图G=(VE)n(n1)个顶点,则其邻接矩阵是n阶对称方阵,如图7-7所示。元素定义如下:


(2)  带权图的邻接矩阵

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


⑶ 有向图邻接矩阵的特性

◆ 对于顶点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'));
	}
}


本文转载自:http://blog.csdn.net/luoweifu/article/details/9270693

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
Java实现无向图的建立与遍历

一、基于邻接矩阵表示法的无向图   邻接矩阵是一种利用一维数组记录点集信息、二维数组记录边集信息来表示图的表示法,因此我们可以将图抽象成一个类,点集信息和边集信息抽象成类的属性,...

牛cattle
06/09
0
0
漫画:什么是 “图”?(修订版)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/bjweimengshu/article/details/88801670

程序员小灰
03/25
0
0
小蚂蚁学习数据结构(29)——图的存储表示

图的数组(邻接矩阵)存储表示 方法:将图的顶点信息存储在一个一维数组中,并将它的邻接矩阵存储在一个二位数组中即构成图的数组(邻接矩阵)表示。 无向图的邻接矩阵具有如下特点: 1,它是...

嗜学如命的小蚂蚁
2016/02/04
55
0
数据结构与算法(图)

基本概念: 顶点(Vertex):V表示顶点的集合 边(Edge):E表示边的集合 无向边:用圆括号(v,w)∈E,其中v,w∈V 有向边:用尖括号 带权重(例如边表示长度),带权的图通常称为网 抽象数据...

李文良
2016/05/24
91
0