上一次我们介绍了图的相关的数据结构，今天我们来介绍图的有关算法。
接下来我将以如下的顺序介绍算法：1.图的遍历（广度和深度）2.最小生成树 3.最短路径 4.拓扑排序 5.关键路径
一、图的遍历
1.基本思路
1).图的遍历：从图中某一个顶点出发遍历途中其余结点，每一 个顶点仅仅被遍历 一次。
2).基本思路
（1）树有四种遍历方式，因为根结点只有一个。而图的复杂情况是顺着一个
点向下寻找，很有可能又找回到自己，容易形成回路造成死循环。
（2）所以要设置一个数组visited[n]，n是图中顶点的个数，初值为0，当该顶
点被遍历后，修改数组元素值为1.
（3）基于上面的思想，形成两个遍历方案：深度优先遍历和广度优先遍历。
2.深度优先遍历
深度优先遍历，就是从初始访问结点出发，我们知道初始访问结点可能有多个邻接结点，深度优先搜索的策略是首先访问第一个邻接结点，再以这个被访问的邻接结点作为初始结点，访问它的第一邻接结点。总结来说：每次访问当前结点后首先访问当前结点的第一个邻接结点。
这种策略是优先纵向深度，而不是对一个结点的邻接结点做横向访问。算法标识如下：
（1）访问初始结点，并标记结点v为已访问。
（2）查找结点v的第一个邻接结点w。
（3）若w存在，则继续执行4，否则算法结束。
（4）若w未被访问，对w进行深度优先递归（即把w当做另一个v，执行算法1，2，3）。
（5）查找v的w邻接结点的下一个邻接结点，转到步骤3。
例如下图，深度优先遍历的顺序是1->2->4->8->5->3->6->7
深度优先算法代码和广度合在一起了，都在下面
3.广度优先遍历
广度优先遍历类似与一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按照这个顺序来访问这个结点的邻接结点。算法的表述如下：
（1）访问初始结点v并标记结点v为已访问。
（2）结点v入队列。
（3）当队列非空时，继续执行，否则算法结束。
（4）出队列，取得队头结点u。
（5）查找结点u的第一个邻接结点w。
（6）若结点u的邻接结点w不存在，则转到步骤3；否则执行下面3个步骤：
1）若结点w未被访问，则访问结点w并标记为已访问。
2）结点w入队列。
3）查找结点u的继w邻接结点后的下一个邻接结点，转到步骤6。
例如下图，广度优先遍历的顺序为：1->2->3->4->5->6->7->8
深度，广度优先算法代码，这个代码用的邻接矩阵
package com.xushu.Undirectedgraph;
/**
* Java: 邻接表表示的"无向图(List Undirected Graph)"
*/
import java.io.IOException;
import java.util.Scanner;
public class ListUDG {
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
}
// 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
private VNode[] mVexs; // 顶点数组
// /*
// * 创建图(自己输入数据)
// */
// public ListUDG() {
//
// // 输入"顶点数"和"边数"
// System.out.printf("input vertex number: ");
// int vlen = readInt();
// System.out.printf("input edge number: ");
// int elen = readInt();
// if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
// System.out.printf("input error: invalid parameters!\n");
// return ;
// }
//
// // 初始化"顶点"
// mVexs = new VNode[vlen];
// for (int i = 0; i < mVexs.length; i++) {
// System.out.printf("vertex(%d): ", i);
// mVexs[i] = new VNode();
// mVexs[i].data = readChar();
// mVexs[i].firstEdge = null;
// }
//
// // 初始化"边"
// //mMatrix = new int[vlen][vlen];
// for (int i = 0; i < elen; i++) {
// // 读取边的起始顶点和结束顶点
// System.out.printf("edge(%d):", i);
// char c1 = readChar();
// char c2 = readChar();
// int p1 = getPosition(c1);
// int p2 = getPosition(c2);
// // 初始化node1
// ENode node1 = new ENode();
// node1.ivex = p2;
// // 将node1链接到"p1所在链表的末尾"
// if(mVexs[p1].firstEdge == null)
// mVexs[p1].firstEdge = node1;
// else
// linkLast(mVexs[p1].firstEdge, node1);
// // 初始化node2
// ENode node2 = new ENode();
// node2.ivex = p1;
// // 将node2链接到"p2所在链表的末尾"
// if(mVexs[p2].firstEdge == null)
// mVexs[p2].firstEdge = node2;
// else
// linkLast(mVexs[p2].firstEdge, node2);
// }
// }
/*
* 创建图(用已提供的矩阵)
*
* 参数说明：
* vexs -- 顶点数组
* edges -- 边数组
*/
public ListUDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new VNode[vlen];
for (int i = 0; i < mVexs.length; i++) {
mVexs[i] = new VNode();
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = null;
}
// 初始化"边"
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
char c1 = edges[i][0];
char c2 = edges[i][1];
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 将node2链接到"p2所在链表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2;
else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 将node节点链接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while(p.nextEdge!=null)
p = p.nextEdge;
p.nextEdge = node;
}
/*
* 返回ch位置
*/
private int getPosition(char ch) {
for(int i=0; i<mVexs.length; i++)
if(mVexs[i].data==ch)
return i;
return -1;
}
/*
* 读取一个输入字符
*/
private char readChar() {
char ch='0';
do {
try {
ch = (char)System.in.read();
} catch (IOException e) {
e.printStackTrace();
}
} while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
return ch;
}
/*
* 读取一个输入字符
*/
private int readInt() {
Scanner scanner = new Scanner(System.in);
return scanner.nextInt();
}
/*
* 深度优先搜索遍历图的递归实现
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.printf("%c ", mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
if (!visited[node.ivex])
DFS(node.ivex, visited);
node = node.nextEdge;
}
}
/*
* 深度优先搜索遍历图
*/
public void DFSTravel() {
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("DFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i])
DFS(i, visited);
}
System.out.printf("\n");
}
/*
* 广度优先搜索（类似于树的层次遍历）
*/
public void BFSTravel() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.length]; // 辅组队列
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("BFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.printf("%c ", mVexs[i].data);
queue[rear++] = i; // 入队列
}
while (head != rear) { //当队列不空
int j = queue[head++]; // 出队列
ENode node = mVexs[j].firstEdge;
while (node != null) {
int k = node.ivex;
if (!visited[k])
{
visited[k] = true;
System.out.printf("%c ", mVexs[k].data);
queue[rear++] = k;
}
node = node.nextEdge;
}
}
}
System.out.printf("\n");
}
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("List Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("%d(%c): ", i, mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char[][] edges = new char[][]{
{'A', 'C'},
{'A', 'D'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'F', 'G'}};
ListUDG pG;
// 自定义"图"(输入矩阵队列)
//pG = new ListUDG();
// 采用已有的"图"
pG = new ListUDG(vexs, edges);
pG.print(); // 打印图
pG.DFSTravel(); // 深度优先遍历
pG.BFSTravel(); // 广度优先遍历
}
}
