上一次我們介紹了圖的相關(guān)的數(shù)據(jù)結(jié)構(gòu)辨图，今天我們來介紹圖的有關(guān)算法。
接下來我將以如下的順序介紹算法：1.圖的遍歷（廣度和深度）外帶解決拓?fù)渑判? 2.最小生成樹 3.最短路徑
一肢藐、圖的遍歷
1.基本思路
1).圖的遍歷：從圖中某一個頂點出發(fā)遍歷途中其余結(jié)點故河，每一 個頂點僅僅被遍歷 一次。
2).基本思路
（1）樹有四種遍歷方式吆豹，因為根結(jié)點只有一個鱼的。而圖的復(fù)雜情況是順著一個
點向下尋找，很有可能又找回到自己痘煤，容易形成回路造成死循環(huán)凑阶。
（2）所以要設(shè)置一個數(shù)組visited[n]，n是圖中頂點的個數(shù)衷快，初值為0宙橱，當(dāng)該頂
點被遍歷后，修改數(shù)組元素值為1.
（3）基于上面的思想烦磁，形成兩個遍歷方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷养匈。
2.深度優(yōu)先遍歷
深度優(yōu)先遍歷，就是從初始訪問結(jié)點出發(fā)都伪，我們知道初始訪問結(jié)點可能有多個鄰接結(jié)點呕乎，深度優(yōu)先搜索的策略是首先訪問第一個鄰接結(jié)點陨晶，再以這個被訪問的鄰接結(jié)點作為初始結(jié)點帝璧，訪問它的第一鄰接結(jié)點湿刽〉乃福總結(jié)來說：每次訪問當(dāng)前結(jié)點后首先訪問當(dāng)前結(jié)點的第一個鄰接結(jié)點。
這種策略是優(yōu)先縱向深度诈闺，而不是對一個結(jié)點的鄰接結(jié)點做橫向訪問渴庆。算法標(biāo)識如下：
（1）訪問初始結(jié)點雅镊，并標(biāo)記結(jié)點v為已訪問。
（2）查找結(jié)點v的第一個鄰接結(jié)點w仁烹。
（3）若w存在耸弄，則繼續(xù)執(zhí)行4，否則算法結(jié)束卓缰。
（4）若w未被訪問计呈，對w進(jìn)行深度優(yōu)先遞歸（即把w當(dāng)做另一個v征唬，執(zhí)行算法1，2总寒，3）。
（5）查找v的w鄰接結(jié)點的下一個鄰接結(jié)點偿乖，轉(zhuǎn)到步驟3。
例如下圖贪薪，深度優(yōu)先遍歷的順序是1->2->4->8->5->3->6->7
深度優(yōu)先算法代碼和廣度合在一起了，都在下面
3.廣度優(yōu)先遍歷
廣度優(yōu)先遍歷類似與一個分層搜索的過程竣稽，廣度優(yōu)先遍歷需要使用一個隊列以保持訪問過的結(jié)點的順序霍弹，以便按照這個順序來訪問這個結(jié)點的鄰接結(jié)點毫别。算法的表述如下：
（1）訪問初始結(jié)點v并標(biāo)記結(jié)點v為已訪問典格。
（2）結(jié)點v入隊列。
（3）當(dāng)隊列非空時耍缴，繼續(xù)執(zhí)行挽霉，否則算法結(jié)束变汪。
（4）出隊列，取得隊頭結(jié)點u裙盾。
（5）查找結(jié)點u的第一個鄰接結(jié)點w。
（6）若結(jié)點u的鄰接結(jié)點w不存在番官，則轉(zhuǎn)到步驟3鲤拿；否則執(zhí)行下面3個步驟：
1）若結(jié)點w未被訪問署咽，則訪問結(jié)點w并標(biāo)記為已訪問。
2）結(jié)點w入隊列宁否。
3）查找結(jié)點u的繼w鄰接結(jié)點后的下一個鄰接結(jié)點，轉(zhuǎn)到步驟6慕匠。
例如下圖，廣度優(yōu)先遍歷的順序為：1->2->3->4->5->6->7->8
深度蓉媳，廣度優(yōu)先算法代碼锅铅，這個代碼用的鄰接表
package com.xushu.Undirectedgraph;
/**
* Java: 鄰接表表示的"無向圖(List Undirected Graph)"
*/
import java.io.IOException;
import java.util.Scanner;
public class ListUDG {
// 鄰接表中表對應(yīng)的鏈表的頂點
private class ENode {
int ivex; // 該邊所指向的頂點的位置
ENode nextEdge; // 指向下一條弧的指針
}
// 鄰接表中表的頂點
private class VNode {
char data; // 頂點信息
ENode firstEdge; // 指向第一條依附該頂點的弧
};
private VNode[] mVexs; // 頂點數(shù)組
// /*
// * 創(chuàng)建圖(自己輸入數(shù)據(jù))
// */
// public ListUDG() {
//
// // 輸入"頂點數(shù)"和"邊數(shù)"
// 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++) {
// // 讀取邊的起始頂點和結(jié)束頂點
// 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);
// }
// }
/*
* 創(chuàng)建圖(用已提供的矩陣)
*
* 參數(shù)說明：
* vexs -- 頂點數(shù)組
* edges -- 邊數(shù)組
*/
public ListUDG(char[] vexs, char[][] edges) {
// 初始化"頂點數(shù)"和"邊數(shù)"
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++) {
// 讀取邊的起始頂點和結(jié)束頂點
char c1 = edges[i][0];
char c2 = edges[i][1];
// 讀取邊的起始頂點和結(jié)束頂點
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節(jié)點鏈接到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();
}
/*
* 深度優(yōu)先搜索遍歷圖的遞歸實現(xiàn)
*/
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;
}
}
/*
* 深度優(yōu)先搜索遍歷圖
*/
public void DFSTravel() {
boolean[] visited = new boolean[mVexs.length]; // 頂點訪問標(biāo)記
// 初始化所有頂點都沒有被訪問
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");
}
/*
* 廣度優(yōu)先搜索（類似于樹的層次遍歷）
*/
public void BFSTravel() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.length]; // 輔組隊列
boolean[] visited = new boolean[mVexs.length]; // 頂點訪問標(biāo)記
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) { //當(dāng)隊列不空
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(); // 深度優(yōu)先遍歷
pG.BFSTravel(); // 廣度優(yōu)先遍歷
}
}
