阅读大话数据结构（6）

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解图，代码均为自己实现。

图

图（Graph）是由定点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

线性表中将数据元素称为元素，树中将数据元素称为结点，图中将数据元素称为顶点。

线性表中可以没有数据元素，称为空表。树中可以没有结点，称为空树。在图结构中，不允许没有顶点。在定义中，顶点集合有穷非空。

线性表中，相邻数据元素之间有线性关系。树结构中，相邻两层结点之间有层次关系。在图中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系有边来表示。边集可以为空。

各种图的相关概念

无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(vi , vj)来表示。

无向图：若图中任意两个顶点之间的边都是无向边，则称该图为无向图。

有向边：若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc），用有序偶对来表示，vi 称为弧尾（Tail），vj 称为弧头（Head）。

有向图：若图中任意两个顶点之间的边都是有向边，则称该图为有向图。

简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。

无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

权：与图的边或弧相关的数叫做权（Weight）。

网：带权的图称为网（Network）。

图的存储结构

邻接矩阵

​ 图的邻接矩阵（Adjacency Matrix）存储方式使用过两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

邻接矩阵有向图和邻接矩阵无向图结构一样，只是在存储矩阵值时只存储对应方向的点。

缺点：对于边数相对顶点较少的图，这种结构是存在对存储空间的极大浪费。

邻接矩阵无向图

public class MatrixNDG {
	int size;
    char[] vertexs;
    int[][] matrix;
	public MatrixNDG(char[] vertexs,char[][] edges){
		this.vertexs = vertexs;
		this.size = vertexs.length;
		this.matrix = new int[size][size];
		for(char[] c : edges){
			int p = getPostion(c[0]);
			int q = getPostion(c[1]);
			matrix[p][q] = 1;
			matrix[q][p] = 1;
		}
	}
	public MatrixNDG(char[] vertexs,char[][] edges,int[] weight){
		int i , j ,k = 0;
		this.vertexs = vertexs;
		this.size = vertexs.length;
		this.matrix = new int[size][size];
		for(i = 0 ; i < size ; i++){
			for(j = 0 ; j <size; j++){
				matrix[i][j] =Integer.MAX_VALUE;
			}
		}
		for(j = 0 ; j < size; j++){
			matrix[j][j] = 0;
		}
		for(char[] c : edges){
			int p = getPostion(c[0]);
			int q = getPostion(c[1]);
			matrix[p][q] = weight[k];
			matrix[q][p] = weight[k];
			k++;
		}
	}
	private int getPostion(char c){
		for ( int i = 0; i < vertexs.length ; i++){
			if (c == vertexs[i]) {
				return i;
			}
		}
		return -1;
	}	
}

邻接矩阵有向图

public class MatrixNDG {
	int size;
    char[] vertexs;
    int[][] matrix;
	public MatrixNDG(char[] vertexs,char[][] edges){
		this.vertexs = vertexs;
		this.size = vertexs.length;
		this.matrix = new int[size][size];
		for(char[] c : edges){
			int p = getPostion(c[0]);
			int q = getPostion(c[1]);
			matrix[p][q] = 1;
		}
	}
	public MatrixNDG(char[] vertexs,char[][] edges,int[] weight){
		int i , j ,k = 0;
		this.vertexs = vertexs;
		this.size = vertexs.length;
		this.matrix = new int[size][size];
		for(i = 0 ; i < size ; i++){
			for(j = 0 ; j <size; j++){
				matrix[i][j] =Integer.MAX_VALUE;
			}
		}
		for(j = 0 ; j < size; j++){
			matrix[j][j] = 0;
		}
		for(char[] c : edges){
			int p = getPostion(c[0]);
			int q = getPostion(c[1]);
			matrix[p][q] = weight[k];
			k++;
		}
	}
	private int getPostion(char c){
		for ( int i = 0; i < vertexs.length ; i++){
			if (c == vertexs[i]) {
				return i;
			}
		}
		return -1;
	}	
}

邻接表

数组与链表相结合的存储方法称为邻接表（Adjacency List）。

邻接表无向图

邻接表有向图

十字链表

把邻接表和逆邻接表结合

邻接多重表

略

边集数组

略

图的遍历

深度优先遍历

（Depth_First_Search）DFS，顾名思义，就是从一个顶点出发，往最深里找。

邻接矩阵的深度优先遍历

无向图和有向图

邻接表的深度优先遍历

无向图和有向图

广度优先遍历

（Breath_First_Search）BFS，也就是从一个顶点出发，一层层找。

邻接矩阵的广度优先遍历

无向图和有向图

public List<Character> breadthFirstSearch(char v){
		hasVisit = new boolean[vertexs.length];
		List<Character> res =new ArrayList<Character>();
		Queue<Character> queue = new LinkedList<Character>();
		hasVisit[getPostion(v)] = true;
		queue.offer(v);
		while(!queue.isEmpty()){
			Character ch = queue.poll();
			int i = getPostion(ch);
			res.add(ch);
			for (int j = 0; j < vertexs.length; j++ ) {
				if (matrix[i][j] != 0 && matrix[i][j] != Integer.MAX_VALUE && !hasVisit[j]) {
					hasVisit[j] = true;
					queue.offer(vertexs[j]);
				}
			}
		}
		return res;
	}

邻接表的广度优先遍历

无向图和有向图

最小生成树

最短路径

迪杰斯特拉算法

弗洛伊德算法

关键路径