圖的存儲結(jié)構(gòu)中有兩種：
鄰接表和矩陣。通常鄰接表適用于邊比較少的圖中（邊多，查找效率低），矩陣通常適用于比較稠密的圖中（邊少浪費空間）。
本文就鄰接表存儲圖結(jié)構(gòu)對圖中比較重要的內(nèi)容（
圖構(gòu)建，深度、廣度遍歷，dijstra算法、prim算法以及kruskal算法進(jìn)行介紹和代碼實現(xiàn)java），水平有限,歡迎大家吐槽。主要內(nèi)容參考此文 ，對原作者表示感謝。
圖構(gòu)建
- 初始化方式
- 讓用戶輸入（比較繁瑣）
- 根據(jù)領(lǐng)點數(shù)組、邊數(shù)組自動進(jìn)行構(gòu)建
為了靈活，設(shè)置兩種初始化方式：
public ListUdg() {}
public ListUdg(char[] inodes, EData[] eData)
- ListUdg內(nèi)部成員：
程序中涉及到的數(shù)據(jù)結(jié)構(gòu)如下：
圖結(jié)構(gòu)
//表示一個節(jié)點
private class Vnode {
char data;
Edge firstEdge;
}
//鄰接邊
private class Edge {
int index;
int weight;
Edge next;
}
//表示輸入數(shù)據(jù)
private static class EData {
char start, end;
int weight;
}
//成員變量：
private Vnode[] Vnodes;
private Map<Character, Integer> map; //線性查找到Char對應(yīng)的數(shù)組下標(biāo)
private int edgeNumL; //記錄圖中總共的邊數(shù)
- 工具函數(shù)：
private char readChar()
private int readInt()
- 初始化：
//以數(shù)組構(gòu)建為例，用戶輸入也是一致的：
public ListUdg(char[] inodes, EData[] eData) {
//初始化內(nèi)部成員變量
int length = inodes.length;
map = new HashMap<>();
for (int i = 0; i < length; i++) {
map.put(inodes[i], i);
}
Vnodes = new Vnode[length];
for (int i = 0; i < length; i++) {
Vnodes[i] = new Vnode();
Vnodes[i].data = inodes[i];
Vnodes[i].firstEdge = null;
}
edgeNumL = eData.length;
//根據(jù)輸入邊，構(gòu)建圖結(jié)構(gòu)
for (int i = 0; i < eData.length; i++) {
int index1 = map.get(eData[i].start);
int index2 = map.get(eData[i].end);
//注意，無向圖，邊的末端對應(yīng)的下標(biāo)
Edge edge1 = new Edge(index2, eData[i].weight, null);
Edge edge2 = new Edge(index1, eData[i].weight, null);
if (Vnodes[index1].firstEdge == null) {
Vnodes[index1].firstEdge = edge1;
} else {
//將連接的多條邊，連接起來
linkEdge(Vnodes[index1].firstEdge, edge1);
}
if (Vnodes[index2].firstEdge == null) {
Vnodes[index2].firstEdge = edge2;
} else {
linkEdge(Vnodes[index2].firstEdge, edge2);
}
}
}
//插入到末端即可
private void linkEdge(Edge list, Edge next) {
while (list.next != null) {
list = list.next;
}
list.next = next;
}
編寫打印函數(shù)，驗證建表是否成功（具體代碼參見）
初始化數(shù)據(jù)如下：
圖初始化數(shù)據(jù)
遍歷方式
-
廣度遍歷
: 數(shù)據(jù)結(jié)構(gòu)使用隊列，鄰接表已經(jīng)將所有的連接邊串起來，迭代next即可，注意將已遍歷的點加入隊列。隊列使用array,設(shè)置head,rear兩個游標(biāo)。
public void bfs() {
int length = Vnodes.length;
int[] queue = new int[length];
int head = 0;
int rear = 0;
boolean[] visited = new boolean[length];
for (int i = 0; i < visited.length; i++) {
visited[i] = false;
}
System.out.println("BFS:");
for (int i = 0; i < length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.println("visited:" + Vnodes[i].data);
//訪問之后，插入隊列
queue[rear++] = i;
}
while (head != rear) {
int index = queue[head++];
Edge edge = Vnodes[i].firstEdge;
while (edge != null) {
int tIndex = edge.index;
if (!visited[tIndex]) {
visited[tIndex] = true;
System.out.println("visited:" + Vnodes[tIndex].data);
//訪問之后，插入隊列
queue[rear++] = tIndex;
}
edge = edge.next;
}
}
}
System.out.println();
}
-
深度遍歷
: 使用遞歸，同樣設(shè)置visited數(shù)組表示訪問情況
public void dfs() {
int length = Vnodes.length;
boolean[] visited = new boolean[length];
for (int i = 0; i < length; i++) {
visited[i] = false;
}
System.out.println("DFS:");
for (int i = 0; i < length; i++) {
if(!visited[i])
dfs(i, visited);
}
System.out.println();
}
private void dfs(int index, boolean[] visited) {
visited[index] = true;
System.out.println("visited:" + Vnodes[index].data);
Edge edge = Vnodes[index].firstEdge;
while (edge != null) {
// 快速迭代完成
if (!visited[edge.index]) {
dfs(edge.index, visited);
}
edge = edge.next;
}
}
圖中比較重要的幾種算法：
dijkstra算法
單源最短路徑，給定起點，輸出到所有其他的點最短的路徑。
算法思路
設(shè)置兩個集合S和U,S中保存的是已經(jīng)遍歷過的點，U中是未遍歷完成的（通過visited數(shù)組區(qū)分）；初始化S中只有起點，找到兩集合之間最短距離，并將邊的另一端加入集合S中，更新s到其他頂點的距離（兩種情況，未達(dá)->可達(dá)，距離變短,(s,v)的距離可能大于(s,k)+(k,v)的距離。
public void dijkstra(int vtex,int[] prev,int[] dist){
//初始化,visited數(shù)組和距離數(shù)組
int length = dist.length;
boolean[] visited = new boolean[length];
for (int i = 0; i < length; i++) {
visited[i] = false;
prev[i] = 0;
//獲取相連邊距離
dist[i] = getWeight(vtex,i);
}
visited[vtex] = true;
dist[vtex] = 0;
// 每次取出新的節(jié)點
int k = 0;
for (int i = 0; i < length - 1; i++) {
// 取出最小距離的點
int min = INF;
for (int j = 0; j < length; j++) {
if(!visited[j] && dist[j] < min){
min = dist[j];
k = j;
}
}
visited[k] = true;
// 對新加入的點進(jìn)行距離更新
for (int j = 0; j < length; j++) {
int tmp = getWeight(k,j);
//防止運(yùn)算溢出
tmp = (tmp == INF)?INF:(min+tmp);
if(!visited[j] && tmp < dist[j]){
//距離變短，更新前驅(qū)節(jié)點和距離
prev[j] = k;
dist[j] = tmp;
}
}
}
System.out.println("dist:");
for (int i = 0; i < dist.length; i++) {
System.out.print(dist[i]+" ");
}
System.out.println();
System.out.println("prev:");
for (int i = 0; i < prev.length; i++) {
System.out.print(prev[i]+" ");
}
System.out.println();
//根據(jù)前驅(qū)節(jié)點回溯，打印路徑
for (int i = 0; i < length ; i++) {
if(i != vtex){
System.out.printf("%s -> %s distance:%d\n\t",Vnodes[vtex].data,Vnodes[i].data,dist[i]);
// output the path from the right --> left
System.out.print(Vnodes[i].data+"-->");
int pre = prev[i];
while(pre != vtex){
System.out.printf("%s-->",Vnodes[pre].data);
pre = prev[pre];
}
System.out.printf("%s\n",Vnodes[vtex].data);
}
}
}
//相連邊距離
private int getWeight(int start,int end){
Edge edge = Vnodes[start].firstEdge;
while(edge != null){
if(edge.index == end){
return edge.weight;
}
edge = edge.next;
}
return INF;
}
prim算法
先介紹prim，prim算法在思想方法上和dijkstra很類似。
算法思路
同樣設(shè)置兩個集合，點集合U(存放最小生成樹中點），邊集合（最小生成樹邊）； 從所有u?U，v?(V-U)(V-U表示去除U的所有頂點)的邊中選取權(quán)值最小的邊(u,v)，將頂點v加入集合U中，將邊(u,v)加入集合T中，如此不斷重復(fù)，直到U=V為止，最小生成樹構(gòu)造完畢。
public void prim(int start){
//初始化點集合和邊集合
int length = Vnodes.length;
boolean[] visited = new boolean[length];
//為了方便打印路徑，設(shè)置EData數(shù)組表示距離
EData[] eData = new EData[length];
for (int i = 0; i < length; i++) {
int tmp = getWeight(start,i);
eData[i] = new EData(Vnodes[start].data,Vnodes[i].data,tmp);
}
visited[start] = true;
//得到V-U中最短邊的一端頂點
int u = getMin(visited,eData);
int sum = 0;
while(u != -1){
//加入集合U
visited[u] = true;
sum += eData[u].weight;
//進(jìn)行調(diào)整
for (int i = 0; i < length; i++) {
int tmp = getWeight(u,i);
//集合V-U邊的更新
if(!visited[i] && tmp < eData[i].weight){
eData[i].weight = tmp;
eData[i].start = Vnodes[u].data;
eData[i].end = Vnodes[i].data;
}
}
u = getMin(visited,eData);
}
//輸出路徑信息
System.out.println("prim distance:");
for (int i = 0; i < length; i++) {
if(i != start){
System.out.printf("%s-->%s %d\n",eData[i].start,eData[i].end,eData[i].weight);
}
}
System.out.println("total :"+sum);
}
//獲取最短邊
private int getMin(boolean[] visited,EData[] eData){
int index = -1;
int min = INF;
for (int i = 0; i < eData.length; i++) {
if(!visited[i] && eData[i].weight < min){
min = eData[i].weight;
index = i;
}
}
return index;
}
kruskal算法
對所有的邊進(jìn)行從小到大排序，n個頂點中選擇n-1條邊，并保證這n-1條邊不構(gòu)成回路。
算法關(guān)鍵之處在于如何保證不構(gòu)成回路，通過類似并查集(union-find)思路，將所有聯(lián)通的路徑端點的ends設(shè)置為同一個值,對于要加入的邊，如果邊兩端的點vends相同說明已經(jīng)有路徑可達(dá)，沒有必要添加此邊。
//獲取邊集合,也可以保存用戶輸入或者初始化的邊集合直接使用
private EData[] getEdata(){
EData[] edata = new EData[edgeNumL];
int index = 0;
for (int i = 0; i < Vnodes.length; i++) {
Edge edge = Vnodes[i].firstEdge;
while(edge!=null){
//去除無向圖中的重復(fù)邊，為邊集排序準(zhǔn)備
if(edge.index > i){
edata[index++]= new EData(Vnodes[i].data,Vnodes[edge.index].data,edge.weight);
}
edge = edge.next;
}
}
return edata;
}
//對邊集合進(jìn)行排序，可以使用快排、堆排，這里為了方便直接冒泡排序
private void sortEdges(EData[] eData){
for (int i = 0; i < edgeNumL; i++) {
for (int j = i+1; j < edgeNumL; j++) {
if(eData[i].weight > eData[j].weight){
EData tmp = eData[i];
eData[i] = eData[j];
eData[j] = tmp;
}
}
}
}
//算法實現(xiàn)
public void kruskal(){
//獲取邊集
EData[] edata = getEdata();
//邊集排序
sortEdges(edata);
//遞歸追溯數(shù)組
int[] ends = new int[edgeNumL];
//最短邊集
EData[] ret = new EData[edgeNumL];
int index = 0;
for (int i = 0; i < edgeNumL; i++) {
EData tmp = edata[i];
int start = map.get(tmp.start);
int end = map.get(tmp.end);
int m = getEnd(ends,start);
int n = getEnd(ends,end);
//如果對應(yīng)的ends值不同，需要添加此邊
if(m!=n){
ends[m] = n;
ret[index++] = tmp;
}
}
//打印結(jié)果
int sum = 0;
System.out.println("krusal distance:");
for (int i = 0; i < index; i++) {
System.out.printf("%s -> %s:%d\n",ret[i].start,ret[i].end,ret[i].weight);
sum+= ret[i].weight;
}
System.out.println("total :"+sum);
}
//
private int getEnd(int[] ends,int index){
while(ends[index] != 0){
index = ends[index];
}
return index;
}
本文只是基本實現(xiàn)，針對各個不同算法都有一定的改進(jìn)版本，后面有時間再添加補(bǔ)充。
參考資料：
