大话数据结构学习笔记（二）

图

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

关于图的一些术语解释

顶点（Vertex）：
图中的结点又称为顶点。

无边图：
若顶点Vi到Vj之间的边没有方向，则称这条边为无项边（Edge），用序偶对(Vi,Vj)标示。
对于下图无向图G1来说，G1=(V1, {E1})，其中顶点集合V1={A,B,C,D}；边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}:

有向图：
若从顶点Vi到Vj的边是有方向的，则成这条边为有向边，也称为弧（Arc）。用有序对（Vi，Vj）标示，Vi称为弧尾，Vj称为弧头。如果任意两条边之间都是有向的，则称该图为有向图。
有向图G2中，G2=（V2,{E2}），顶点集合（A,B,C,D）,弧集合E2={,{B,A},,}.

有向和无向完全图

权（Weight）：
有些图的边和弧有相关的数，这个数叫做权（Weight）。这些带权的图通常称为网（Network）

度（Degree）：
无向图中顶点v的度是关联于该顶点的边的数目，记为TD(v)。
入度（Indegree）：若G为有向图，则把以顶点v为终点的边的数目，称为v的入度，记为ID(v)。
出度（Outdegree）：若G为有向图，则把以顶点v为始点的边的数目，称为v的出度，记为OD(v)。
如图①：A的度为3。
如图②：A的入度为2，出度为1，所以A的度为3。

子图（Subgraph：
设G=(V,E)是一个图，若E’是E的子集，V’是V的子集，使得E’中的边仅与V’中顶点相关联，则图G’=(V’,E’)称为图G的子图。
如图：②为①的4个子图

路径（Path
无向图G=(V,E)中从顶点v到顶点v’的路径是一个顶点序列(v=vi0,vi1,…,vin=v’)，其中(vij-1,vij)∈E，1≤j≤n。有向图G=(V,E)中从顶点v到顶点v’的路径是一个顶点序列(v=vi0,vi1,…,vin=v’)，其中〈vij-1,vij〉∈E，1≤j≤n。
　简单路径：序列中顶点不重复出现的路径。
　环（Cycle）：又称回路，第一个顶点和最后一个顶点相同的路径。
　简单回路：又称简单环，除了第一个顶点和最后一个顶点外，其余顶点不重复的回路。

连通：
在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。
连通图（Connected Graph）：如果对于图中的任意两个顶点vi、vj∈V，vi和vj都是连通的，则称该图为连通图。
连通分量（Connected Component）：无向图中的极大连通子图。
强连通图：在有向图G中，如果对于每一对vi，vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
强连通分量：有向图中的极大连通子图

生成树（Spanning Tree）：
含有连通图的全部顶点的一个极小连通子图。

图的存储结构

邻接矩阵：
图的邻接矩阵存储方式是用两个数组来标示图。一个一位数组存储图顶点的信息，一个二维数组（称为邻接矩阵）存储图中边或者弧的信息。

设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

实例如下，左图是一个无向图。右图是邻接矩阵表示：

无向网图的创建代码，时间复杂度为O{n + n2 + e}。

邻接表
用数组和链表结合的存储方式来标示图的方法称为邻接表。

原理：（类似于树的孩子表示法的第三种存储方式）
图中顶点用一个一维数组存储，当然也可以用单链表存储。
图中每个顶点 Vi 的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。无向图成为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

十字链表（OrthogonalList）
十字链表把邻接表与逆邻接表结合起来，解决了出度和入度的问题。

图的遍历

从图中某个顶点出发访遍图中其余顶点，且使每个顶点仅被访问依次，这一过程叫做图的遍历.

遍历方法：深度优先遍历和广度优先遍历

深度优先遍历 O(n^2)：从图中某个顶点出发v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先便利图，直到图中所有和v有相同路径的顶点都被访问。

广度优先遍历（Breadth_First_Search）O(n^2) 又称为广度优先搜索，简称BFS

深度优先更适合目标比较明确，以找到目标为主要目的的情况。
广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

图的应用

最小生成树（普里姆算法 O(n^2)）

我们把构造连通图的最小代价生成树称为最小生成树

最小生成树实现算法：普利姆算法和克鲁斯卡尔算法

普利姆算法

假设 N=(P, {E})是连通网， TE是N上最小生成树中边的集合。算法从 U={u0}（u0∈V），TE={}开始。重复执行下述操作：在所有 u∈U,v∈V-U的边（u,v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有 n-1条边。则T=（V,{TE}）为最小生成树。

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Prim {
	public static List<Vertex> vertexList = new ArrayList<Vertex>();//结点集
	public static List<Edge> EdgeQueue = new ArrayList<Edge>();//边集
	public static List<Vertex> newVertex = new ArrayList<Vertex>();//已经 访问过的结点
	
	public static void main(String[] args) {
		primTree();
	}
	public static void buildGraph() {
		Vertex v1 = new Vertex("a");
		Prim.vertexList.add(v1);
		Vertex v2 = new Vertex("b");
		Prim.vertexList.add(v2);
		Vertex v3 = new Vertex("c");
		Prim.vertexList.add(v3);
		Vertex v4 = new Vertex("d");
		Prim.vertexList.add(v4);
		Vertex v5 = new Vertex("e");
		Prim.vertexList.add(v5);
		addEdge(v1, v2, 6);
		addEdge(v1, v3, 7);
		addEdge(v2, v3, 8);
		addEdge(v2, v5, 4);
		addEdge(v2, v4, 5);
		addEdge(v3, v4, 3);
		addEdge(v3, v5, 9);
		addEdge(v5, v4, 7);
		addEdge(v5, v1, 2);
		addEdge(v4, v2, 2);
	}
	public static void addEdge(Vertex a, Vertex b, int w) {
		Edge e = new Edge(a, b, w);
		Prim.EdgeQueue.add(e);
	}
	public static void primTree(){
		buildGraph();
		Vertex start = vertexList.get(0);
		newVertex.add(start);
		for(int n=0;n<vertexList.size()-1;n++){
			Vertex temp = new Vertex(start.key);
			Edge tempedge = new Edge(start,start,1000);
			for(Vertex v : newVertex){
				for(Edge e : EdgeQueue){
					if(e.start==v && !containVertex(e.end)){
						if(e.key<tempedge.key){
							temp = e.end;
							tempedge = e;
						}	
					}
				}
			}
			newVertex.add(temp);
		}
		Iterator it = newVertex.iterator();
		while(it.hasNext()){
			Vertex v =(Vertex) it.next();
			System.out.println(v.key);
		}
	}
	public static boolean containVertex(Vertex vte){
		for(Vertex v : newVertex){
			if(v.key.equals(vte.key))
				return true;
		}
		return false;
	}
}
class Vertex {
	String key;
	Vertex(String key){
		this.key = key;
	}
}
class Edge{
	Vertex start;
	Vertex end;
	int key;
	Edge(Vertex start,Vertex end,int key){
		this.start = start;
		this.end  = end;
		this.key = key;
		
	}
}

克鲁斯卡尔算法

假设 N=（V, {E}）是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图 T={V,{}}，图中每个顶点自成一格连通分量。在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。

1、新建图G，G中拥有原图中相同的节点，但没有边
2、将原图中所有的边按权值从小到大排序
3、从权值最小的边开始，如果这条边连接的两个节点于图G中不在同一个连通分量中，则添加这条边到图G中
4、重复3，直至图G中所有的节点都在同一个连通分量中

最短路径

对于网图来说，最短路径是指两个顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点式源点，最后一个顶点是终点。

两种计算最短路径算法：迪杰斯特拉(Djikstra)算法和佛洛伊德算法

迪杰斯特拉(Djikstra)算法 O(n^2)
迪杰斯特拉算法并不是一下子求出开始节点到尾节点的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。运用的是贪心算法，如果v1->..->vi->…->vn 是最短路径，那v1->vi,vi->vn也是最短路径。

佛洛依德算法 O(n^3)

通过Floyd计算图G=(V,E)中各个顶点的最短路径时，需要引入一个矩阵S，矩阵S中的元素a[i][j]表示顶点i(第i个顶点)到顶点j(第j个顶点)的距离。
假设图G中顶点个数为N，则需要对矩阵S进行N次更新。初始时，矩阵S中顶点a[i][j]的距离为顶点i到顶点j的权值；如果i和j不相邻，则a[i][j]=∞。接下来开始，对矩阵S进行N次更新。第1次更新时，如果”a[i][j]的距离” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i与j之间经过第1个顶点的距离”)，则更新a[i][j]为”a[i][0]+a[0][j]”。同理，第k次更新时，如果”a[i][j]的距离” > “a[i][k]+a[k][j]”，则更新a[i][j]为”a[i][k]+a[k][j]”。更新N次之后，操作完成！
详见佛洛依德算法，算法推导过程就是构建矩阵的过程。

拓扑排序

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网(Activity On Vertex)。
设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1,V2…..,Vn满足若从顶点Vi到顶点Vj有一条路径，则在顶点序列中Vi必在Vj顶点之前。则我们称这样的顶点序列为拓扑序列。
所谓拓扑序列，其实就是对一个有向图构造拓扑序列的过程。

拓扑排序：是将一个AOV网的各个顶点按一定顺序排列，要求满足若存在，则排序中的顶点Vi必在顶点Vj之前。对于同一幅图，拓扑排序可有多个拓扑排序。

算法：
（1）从有向图中选择一个无前驱（入度为0）的顶点输出。
（2）删除此顶点，并删除已此顶点为为尾的弧。
（3）重复（1），（2）步骤，知道输出全部顶点或者AOV网中不存在入度为0的顶点。

关键路径

在一个表示工程的带权有向图中，用顶点表示事件，用有向图表示活动，用边上的权值表示活动的持续事件，这种这种有向图的边表示活动图，我们称之为AOE网(Activity On Edge Network)。
我们把路径上各个活动所持续的时间之和称为路径的长度，从原点到汇点具有最大长度的路径叫做关键路径，在关键路径上的活动叫关键活动。

算法:
(1) 从开始顶点V0出发，假设ve(0)=0，然后按照拓扑有序求出其他各顶点i的最早开始时间ve(i)，如果得到拓扑序列中顶点数目小于图中的顶点数，则表示图中存在回路，算法结束，否则继续执行。
(2) 从结束顶点Vn出发，假设vl(n-1) = ve(n-1);然后求出各顶点i的最晚发生时间。
(3) 根据顶点的最早发生时间，和最晚发生时间，依次求出出每条弧的最早开始时间和最晚开始时间，如果两只相等，则为关键活动。关键活动组成的路径则为关键路径。

拓扑排序和关键路径使用邻接表存储数据，最小生成树和最短路径用邻接矩阵存储数据。