数据结构-图（定义、存储结构、遍历、求最短路径、拓扑排序）
图是很有用的数据结构，在解决最短路径、工程规划时有很重要的作用。
一、图的定义
1.1图的定义
image.png
图是由顶点的有穷非空集合和顶点指点的边的集合组成，通常表示尾：G(V,E)，其中，G表示一个图，V是图G中的顶点的集合，E是图G中边的集合。
下面三个数据结构都可以称为图
image.png
1.2有向图、无向图和网
无向图：图中所有的边都没有方向。
完全无向图：图中任意两个顶点之间都存在边。含有n个顶点的完全无向图的边的总数是n（n-1）/2。
有向图：图中所有边都有方向。假设顶点A到顶点B之前存在有向边，从A指向B，则边可以用有序偶<A,B>来表示,A为弧尾，B为弧头。有向边也称为弧。
完全有向图：图中任意两点都有方向相反的两条有向边。含有n个顶点的完全有向图的边的总是是n(n-1)。
网：有些图的边具有与它相关的数字，这种与图的边相关的数字叫做权。这些权可以表示从一个顶点到另外一个顶点的距离或耗费。这种带权的图通常称为网。
度、入度、出度
度：对于无向图来说，一个顶点的度就是与该顶点相关联的边的数量。有n个顶点的无向图的度等于边数的两倍。
入度：对于有向图来说，一个顶点的入度是弧头是该顶点的弧的数量。
出度：对于有向图来说，一个顶点的出度是弧尾是该顶点的弧的数量。
1.3路径、环
路径：图G=(V,E)中从顶点A到顶点D的路径是一个顶点序列。路径的长度是路径上边的数量。
环：第一个顶点到最后一个顶点相同的路径称为回路或环。
1.4连通图
在无向图中，如果顶点A到顶点B有路径，则称A和B是联通的。如果图中任意两个顶点都是联通的，则该图称为连通图。
在有向图中，对于每一对顶点A，B，从A到B和从B到A都存在路径，则称该图是强联通图。
二、图的存储结构
我们可以在纸上把图画出来，但是图在程序中应该怎样表示？
2.1 邻接矩阵
邻接矩阵存储方法是用一个一维数组和一个二维数组来表示图。一维数组存储图中顶点的信息，二维数组存储图的边或弧的信息。
无向图的邻接矩阵
有向图的邻接矩阵
上图中，假如我们要找以弧尾为顶点V0的弧，就看二维数组的第一行（V0 - V4）。加入我们要以弧头为V0的弧，就看第一列（V1 - V0，V2 - V0）。
2.2 邻接表
与HashMap的存储结构有些类似。用一个一维数组存储结点，每个结点的邻接点形成一个链表。
无向图的邻接表
有向图的邻接表
三、图的遍历
有时候我们需要从图的某一顶点出发，以某种方式遍历图的每个顶点，并且每个顶点只会被访问一次。
3.1深度优先遍历
以深度优先的方法来遍历图。主要用到深度优先搜索和回溯。
以邻接矩阵表示的图的深度优先搜索的伪代码
/**
* 邻接矩阵表示的图的深度优先搜索
* @author TinyMonster
*
*/
public class DFSAdjMat {
boolean[] visited;
public void DFSTraverse(int[][] graph) {
visited = new boolean[graph.length]; //初始化访问数组，记录每个结点的访问情况
for(int i=0;i<graph.length;i++) { //遍历每个结点，使用深度优先搜索
if(!visited[i]) {
DFS(graph,i);
}
}
}
private void DFS(int[][] graph,int i) {
int j = 0;
visited[i] = true;
System.out.println(i); //打印结点
for(j = 1;j<graph[i].length;j++) { //遍历该结点的所有邻接结点，如果邻接结点没有被访问过，访问该邻接结点
if(!visited[j] && graph[i][j] == 1)
DFS(graph,j);
}
}
}
以邻接表表示的图的深度优先搜索的伪代码
/**
* 邻接表表示的图的深度优先搜索
* @author TinyMonster
*
*/
public class DFSAdjList {
boolean[] visited;
public void DFSAdjListTraverse(Node[] AdjList) {
visited = new boolean[AdjList.length]; //初始化访问数组，记录每个结点的访问情况
for(int i = 0;i<AdjList.length;i++) {
if(visited[i]) //遍历每个结边表中的结点，如果结点没有访问过，对结点进行深度优先搜索
DFS(AdjList,i);
}
}
private void DFS(Node[] AdjList,int i) {
visited[i] = true; //将结点标记为已访问
Node cur = AdjList[i];
System.out.println(cur.data);
Node next = cur.next;
while(next!=null) { //遍历该结点的邻接结点，如果邻接结点没有被访问过，访问该邻接结点
if(!visited[next.data]) {
DFS(AdjList,next.data);
}else {
next = next.next;
}
}
}
private class Node{
int data;
Node next;
}
}
3.2 图的广度优先搜索
图的广度优先搜索使用了栈这一数据结构
邻接矩阵表示的图的深度优先搜索
/**
* 邻接矩阵表示的图的广度优先搜索
* @author TinyMonster
*
*/
public class BFSAdjMat {
boolean[] visited;
public void BFSTraverse(int[][] graph) {
visited = new boolean[graph.length]; //初始化访问数组，记录每个结点的访问情况
for(int i=0;i<visited.length;i++) { //遍历每个结边表中的结点，如果结点没有访问过，对结点进行广度优先搜索
if(!visited[i])
BFS(graph,i);
}
}
private void BFS(int[][] graph,int i) {
Queue<Integer> queue = new LinkedList<Integer>(); //使用栈来进行广度优先搜索
queue.offer(i);
while(!queue.isEmpty()) {
int cur = queue.poll();
visited[cur] = true;
System.out.println(cur);
for(int j=1;j<graph[cur].length;j++) { //将当前结点的所有邻接结点放入队列中
if(!visited[j]&&graph[cur][j]==1) {
queue.offer(j);
}
}
}
}
}
邻接表表示的图的广度优先搜索
/**
* 邻接表表示的图的广度优先搜索
* @author TinyMonster
*
*/
public class BFSAdjList {
boolean[] visited;
public void BFSTraverse(Node[] AdjList) {
visited = new boolean[AdjList.length]; //初始化访问数组，记录每个结点的访问情况
for(int i=0;i<visited.length;i++) { //遍历每个结边表中的结点，如果结点没有访问过，对结点进行广度优先搜索
if(!visited[i])
BFS(AdjList,i);
}
}
private void BFS(Node[] AdjList,int i) {
Queue<Integer> queue = new LinkedList<Integer>(); //使用栈来进行广度优先搜索
queue.offer(i);
while(!queue.isEmpty()) {
int j = queue.poll();
Node cur = AdjList[j];
visited[j] = true; //打印数据
System.out.println(j);
Node next = cur.next;
while(next!=null) { //遍历该结点的所有邻接结点，压入队列中
queue.offer(next.data);
next = next.next;
}
}
}
private class Node{
int data;
Node next;
}
}
四、图的最小生成树
加入你是电信的实施工程师，需要为一个镇的九个村庄假设通信网络做设计，村庄位置大致如下图所示。其中每个结点表示一个村庄，边上的数据表示路径长短。我们要设计一个最短的路径。这就需要最小生成树的知识。
我们知道一个图的生成树是一个极小的连接子图，它含有图中的全部顶点，但是只有足以构成一颗树的n-1条边。
我们把构造连通网的最小代价生成树称为最小生成树。
求一个图的最小生成树可以用以下方法。
普里姆算法
该算法主要一个数组来保存每个结点在路径中的前一个结点，使用另外一个数组来保存到达每个结点的最短距离。通过广度优先搜索，不断扩大搜索范围，不断更新两个数组，最终完成最小生成树的搜索。
一个图和它的邻接矩阵如下图所示。邻接矩阵中，∞表示两个结点之间没有边。
image.png
我们定义两个数组adjvex和lowcost。其中adjvex表示每个结点在最小生成树中路径的上一个结点。lowcost表示每个结点在最小生成树中上一个结点到达该结点的最短路径。
image.png
伪代码
/**
* 图的最小生成树
* @author TinyMonster
*
*/
public class MiniSpanTreePrim {
public void MiniSpanTreePrim(int[][] graph) {
int min;
int[] adjvex = new int[graph.length];
int[] lowcost = new int[graph.length];
for(int i=1;i<graph.length;i++) { //初始化lowcost数组
lowcost[i] = graph[0][i];
}
for(int i=1;i<graph.length;i++) {
min = Integer.MAX_VALUE;
int nextNode = 0;
for(int j=1;j<graph.length;j++) { //找到当前最短的路径
if(lowcost[j]!=0&&lowcost[j]<min) {
min = lowcost[j];
nextNode = j;
}
}
lowcost[nextNode]=0;
System.out.println("路径:"+adjvex[nextNode]+"->"+nextNode); //打印路径
for(int j=1;j<graph.length;j++) { //更新最短路径和adjvex
if(lowcost[j]!=0&&graph[nextNode][j]<lowcost[j]) {
lowcost[j]=graph[nextNode][j];
adjvex[j]=nextNode;
}
}
}
}
}
五、图中两个结点的最短路径
生活中我们经常会需要找到从一个点到另外一个点的最短距离，这时候可以用图的最短路径来解决。
5.1迪杰斯特拉算法
与普里姆算法类似，通过不断搜索周围结点，找到最短路径。
public class ShortestPath {
public void ShortestPath(int[][] graph,int v0,int[] Patharc,int[] ShortPathValue) {
boolean[] finish = new boolean[graph.length];
int min = Integer.MIN_VALUE;
int next = v0;
for(int i=0;i<graph[v0].length;i++) {
ShortPathValue[i] = graph[v0][i];
Patharc[i] = v0;
}
ShortPathValue[v0] = 0;
finish[v0] = true;
for(int i=1;i<graph[v0].length;i++) {
min = Integer.MIN_VALUE;
for(int j=0;j<graph.length;j++) {
if(!finish[j]&&ShortPathValue[j]<min) {
next = j;
min = ShortPathValue[j];
}
}
finish[min] = true;
for(int j=0;j<graph.length;j++) {
if(!finish[j]&&(min+graph[min][j])<ShortPathValue[j]) {
ShortPathValue[j] = min+graph[min][j];
Patharc[j] = min;
}
}
}
}
}
六、拓扑排序
在生活中，完成一个事情可以分为若干个步骤，但是这些步骤之前有依赖关系。比如要拍摄一部电影，可以分为完成据本，确定演员，进行拍摄。首先要在完成据本和确定演员之后才能进行拍摄。
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。
拓扑排序的定义：设G=（V,E）是一个具有n个顶点的有序列向图，V中顶点序列v1,v2...vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必定在顶点vj之前。则我们称这样的顶点序列为一个拓扑排序。
一个AOV网的拓扑排序可能不止一条。所谓拓扑排序，其实就是对一个有向图构造拓扑排序的过程。构造时会有两个结果。如果拓扑序列包含了AOV网的所有结点，那么这个AOV网中不存在环，否则，这个AOV网存在环。
6.1拓扑排序算法
对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此操作，知道输出全部顶点或者AOV网中不存在入度尾0的顶点为止。
在拓扑排序中需要删除顶点，我们用邻接表的存储结构更加方便。
/**
* AOV网的拓扑排序
* @author TinyMonster
*
*/
public class TopoSort {
public boolean TopoSort(EdgeNode[] head) {
Stack<EdgeNode> stack = new Stack<EdgeNode>(); //存储入度等于0的结点
EdgeNode cur = null; //当前顶点结点
Node next = null; //当前边结点
int count = 0; //拓扑序列中结点数量
for(int i=0;i<head.length;i++) { //将所有入度为0的结点压栈
if(head[i].in==0) {
stack.push(head[i]);
}
}
while(stack.isEmpty()) {
cur = stack.pop();
System.out.println(cur.data); //打印序列
count++; //拓扑序列数量+1
next = cur.next; //获取顶点结点的下一个边结点
while(next!=null) { //遍历所有边结点，将入度-1，如果入度==0，将结点压入栈中
if(head[next.adjvex].in>0) {
head[next.adjvex].in --;
if(head[next.adjvex].in == 0) {
stack.push(head[next.adjvex]);
}
}
}
}
return count == head.length; //如果拓扑序列元素数量等于AOV网结点总数，该AOV网可以进行拓扑排序，AOV网中没有环
}
private class EdgeNode{ //邻接表的顶点
int in;//入度
int data;//数据
Node next;
}
private class Node{ //连接表的边结点
int adjvex; //该点对应的顶点的下标
Node next;
}
}
