上一節我們已經看到了圖的邊可以有方向，這一節裡，我們將探討邊的另一個特性：權值。例如，如果帶權圖的頂點代表城市，邊的權可能代表城市之間的距離，或者城市之間的路費，或者之間的車流量等等。
帶權圖歸根究底還是圖，上一節那些圖的基本操作，例如廣度優先搜索和深度優先搜索等都是一樣的，在這一節裡，我們主要來探討一下帶權圖的最小生成樹最短路徑問題。
首先探討下最小生成樹問題，它與上一節所提到的最小生成樹不同。上一節的最小生成樹是個特例，即所有邊的權值都一樣。那麼算法如何設計呢？建議用優先級隊列來實現這個反復選擇最小的路徑，而不是鏈表或數組，這是解決最小生成樹的有效方式。在正式的程序中，優先級隊列可能基於堆來實現，這會加快在較大的優先級隊列中的操作。但是在本例中，我們使用數組實現優先級隊列，僅僅為了說明算法。算法要點如下：
從一個頂點開始，把它放入樹的集合中，然後重復做下面的事情：
1. 找到從最新的頂點到其他頂點的所有邊，這些頂點不能在樹的集合中，把這些邊放入優先級隊列中。
2. 找出權值最小的邊，把它和它所達到的頂點放入樹的集合中。
重復這些步驟，直到所有的頂點都在樹的集合中，這時工作完成。
下面先看一下最小生成樹的代碼，然後再解釋一些細節上的問題：
//邊界路徑類，主要記錄了邊的始末頂點，以及邊的權值
class Edge {
public int srcVert; //index of vertex starting edge
public int destVert; //index of vertex ending edge
public int distance; //distance from src to dest
public Edge(int sv, int dv, int d) {
srcVert = sv;
destVert = dv;
distance = d;
}
}
//自定義優先隊列，用來存儲邊
class PriorityQ {
private final int SIZE = 20;
private Edge[] queArray; //存儲邊界的數組
private int size;
public PriorityQ() {
queArray = new Edge[SIZE];
size = 0;
}
public void insert(Edge item) { //有序的插入邊界
int j;
for(j = 0; j < size; j++) { //找到插入的位置，從0到size-1，逐漸減小
if(item.distance >= queArray[j].distance)
break;
}
//比item.distance小的往後挪一位，給騰出個空間
for(int k = size-1; k >= j; k--) {
queArray[k+1] = queArray[k];
}
queArray[j] = item; //插入item
size++;
}
public Edge removeMin() { //刪除最小的邊界並返回
return queArray[--size];
}
public void removeN(int n) { //刪除n位置的邊界
for(int j = n; j < size-1; j++) {
queArray[j] = queArray[j+1];
}
size--;
}
public Edge peekMin() { //返回最小邊界，不刪除
return queArray[size-1];
}
public Edge peekN(int n) { //返回n位置的邊界
return queArray[n];
}
public int size() {
return size;
}
public boolean isEmpty() {
return (size == 0);
}
public int find(int findDex) { //尋找特定disVert的邊界索引
for(int j = 0; j < size; j++) {
if(queArray[j].destVert == findDex)
return j;
}
return -1;
}
}
//帶權圖類
public class WeightedGraph {
private final int MAX_VERTS = 20; //最大頂點數
private final int INFINITY = 100000; //最遠距離...表示無法達到
private Vertex[] vertexArray; //存儲頂點的數組
private int adjMat[][]; //存儲頂點之間的邊界
private int nVerts; //頂點數量
private int currentVert; //當前頂點索引
private PriorityQ thePQ; //存儲邊的優先級隊列
private int nTree; //最小生成樹中的頂點數量
public WeightedGraph() {
vertexArray = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
for(int i = 0; i < MAX_VERTS; i++) {
for(int j = 0; j < MAX_VERTS; j++) {
adjMat[i][j] = INFINITY; //初始化所有邊界無窮遠
}
}
thePQ = new PriorityQ();
}
public void addVertex(char lab) { //添加頂點
vertexArray[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end, int weight) {//添加帶權邊
adjMat[start][end] = weight;
adjMat[end][start] = weight;
}
public void displayVertex(int v) {
System.out.print(vertexArray[v].label);
}
/*
* 帶權圖的最小生成樹,要選擇一條最優的路徑
*/
public void MinSpanningTree() {
currentVert = 0; //從0開始
while(nTree < nVerts-1) { //當不是所有節點都在最小生成樹中時
//isInTree是上一節Vertex類中新添加的成員變量 private boolean isInTree;
//表示有沒有加入到樹中，初始化為false
vertexArray[currentVert].isInTree = true; //將當前頂點加到樹中
nTree++;
//往PQ中插入與當前頂點相鄰的一些邊界
for(int i = 0; i < nVerts; i++) {
if(i == currentVert) //如果是本頂點，跳出
continue;
if(vertexArray[i].isInTree) //如果頂點i已經在樹中，跳出
continue;
int distance = adjMat[currentVert][i]; //計算當前頂點到i頂點的距離
if(distance == INFINITY)
continue; //如果當前頂點與i頂點無窮遠，跳出
putInPQ(i, distance); //將i節點加入PQ中
}
if(thePQ.size() == 0) { //如果PQ為空，表示圖不連接
System.out.println("Graph not connected!");
return;
}
Edge theEdge = thePQ.removeMin();
int sourceVert = theEdge.srcVert;
currentVert = theEdge.destVert;
System.out.print(vertexArray[sourceVert].label);
System.out.print(vertexArray[currentVert].label);
System.out.print(" ");
}
}
private void putInPQ(int newVert, int newDist) {
int queueIndex = thePQ.find(newVert);//判斷PQ中是否已經有到相同目的頂點的邊界
if(queueIndex != -1) { //如果有則與當前頂點到目的頂點的距離作比較，保留短的那個
Edge tempEdge = thePQ.peekN(queueIndex);//get edge
int oldDist = tempEdge.distance;
if(oldDist > newDist) { //如果新的邊界更短
thePQ.removeN(queueIndex); //刪除舊邊界
Edge theEdge = new Edge(currentVert, newVert, newDist);
thePQ.insert(theEdge);
}
}
else { //如果PQ中沒有到相同目的頂點的邊界
Edge theEdge = new Edge(currentVert, newVert, newDist);
thePQ.insert(theEdge);//直接添加到PQ
}
}
}
算法在while循環中執行，循環結束條件是所有頂點都已在樹中。
1. 當前頂點放在樹中。
2. 連接這個頂點的邊放到優先級隊列中（如果合適）。
3. 從優先級隊列中刪除權值最小的邊，這條邊的目的頂點變成當前頂點。
再看看這些步驟的細節：1中，通過標記currentVert所指頂點的isInTree字段來表示該頂點放入樹中，2中，連接這個頂點的邊插入優先級隊列。通過在鄰接矩陣中掃描行號是currentVert的行尋找需要的邊。只要下面任意一個條件為真，這條邊就不能放入隊列中：
1．源點和終點相同；
2. 終點在樹中；
3. 源點和終點之間沒有邊（鄰接矩陣中對應的值等於無窮大）。
如果沒有一個條件為真，調用putInPQ()方法把這條邊放入隊列中。實際上並不一定會將這條邊放入隊列中，還得進行判斷。步驟3中，將最小權值的邊從優先級隊列中刪除。把這條邊和該邊的重點加入樹，並顯示源點和終點。
最後，所有頂點的isInTree變量被重置，即從樹中刪除。在該程序這樣做，是因為根據這些數據只能創建一棵樹。然後在完成一項工作後，最好把數據恢復到原始的形態。
接下來探討下最短路徑問題：
在帶權圖中最常遇到的問題就是尋找兩點間的最短路徑問題，這個問題的解決方法可應用於現實生活中的很多地方。但是它比前面遇到的問題更加復雜一些。為了解決最短路徑問題而提出的方法叫做Djikstra算法。這個算法的實現基於圖的鄰接矩陣表示法，它不僅能夠找到任意兩點間的最短路徑，還可以找到某個指定點到其他所有頂點的最短路徑。
為了實現這個算法，首先得建一個輔助類DistPar類，這個類中封裝了到初始頂點的距離以及父頂點的信息。
//DistPar類記錄了當前頂點到起始頂點點的距離和當前頂點的父頂點
class DistPar {
public int distance; //distance from start to this vertex
public int parentVert; //current parent of this vertex
public DistPar(int pv, int d) {
distance = d;
parentVert = pv;
}
}
另外還得有個數組，這是最短路徑算法中的一個關鍵數據結構，它保持了從源點到其他頂點（終點）的最短路徑。在算法的執行過程中這個距離是變化的，知道最後，它存儲了從源點開始的真正最短距離。這個數組定義為WeightedGraph的一個私有成員變量：private DistPar[] sPath; //存儲最短路徑數據，存儲的是上面的DistPar對象 private int startToCurrent; //到當前頂點的距離
另外需要在構造函數中將其初始化：sPath =new DistPar[MAX_VERTS];
下面詳細分析最短路徑算法中涉及的幾個方法，這都是WeightedGraph類中的方法，在這裡我抽出來分析的，最後會附上完整的WeightedGraph類代碼
/************************** 最短路徑問題 ****************************/
/**
* path()方法執行真正的最短路徑算法。
*/
public void path() { //尋找所有最短路徑
/*
* 源點總在vertexArray[]數組下標為0的位置，path()方法的第一個任務就是把這個頂點放入樹中。
* 算法執行過程中，將會把其他頂點也逐一放入樹中。把頂點放入樹中的操作是設置一下標志位即可。
* 並把nTree變量增1，這個變量記錄了樹中有多少個頂點。
*/
int startTree = 0; //從vertex 0開始
vertexArray[startTree].isInTree = true;
nTree = 1;
/*
* path()方法把鄰接矩陣的對應行表達的距離復制到sPath[]中，實際總是先從第0行復制
* 為了簡單，假定源點的下標總為0。最開始，所有sPath[]數組中的父節點字段為A，即源點。
*/
for(int i = 0; i < nVerts; i++) {
int tempDist = adjMat[startTree][i];
//sPath中保存的都是到初始頂點的距離，所以父頂點默認都是初始頂點，後面程序中會將其修改
sPath[i] = new DistPar(startTree, tempDist);
}
/*
* 現在進入主循環，等到所有的頂點都放入樹中，這個循環就結束，這個循環有三個基本動作：
* 1. 選擇sPath[]數組中的最小距離
* 2. 把對應的頂點（這個最小距離所在列的題頭）放入樹中，這個頂點變成“當前頂點”currentVert
* 3. 根據currentVert的變化，更新所有的sPath[]數組內容
*/
while(nTree < nVerts) {
//1. 選擇sPath[]數組中的最小距離
int indexMin = getMin(); //獲得sPath中的最小路徑值索引
int minDist = sPath[indexMin].distance; //獲得最小路徑
if(minDist == INFINITY) {
System.out.println("There are unreachable vertices");
break;
}
//2. 把對應的頂點（這個最小距離所在列的題頭）放入樹中，這個頂點變成“當前頂點”currentVert
else { //reset currentVert
currentVert = indexMin;
startToCurrent = sPath[indexMin].distance;
}
vertexArray[currentVert].isInTree = true;
nTree++;
//3. 根據currentVert的變化，更新所有的sPath[]數組內容
adjust_sPath();
}
displayPaths();
nTree = 0;
for(int i = 0; i < nVerts; i++) {
vertexArray[i].isInTree = false;
}
}
//獲取sPath中最小路徑的索引
private int getMin() {
int minDist = INFINITY;
int indexMin = 0;
for(int i = 0; i < nVerts; i++) {
if(!vertexArray[i].isInTree && sPath[i].distance < minDist) {
minDist = sPath[i].distance;
indexMin = i;
}
}
return indexMin;
}
/*調整sPath中存儲的對象的值，即頂點到初始頂點的距離，和頂點的父頂點
* 這是Dijkstra算法的核心
*/
private void adjust_sPath() {
int column = 1;
while(column < nVerts) {
if(vertexArray[column].isInTree) {
column++;
continue;
}
int currentToFringe = adjMat[currentVert][column]; //獲得當前頂點到其他頂點的距離，其他頂點不滿足isInTree
int startToFringe = startToCurrent + currentToFringe; //計算其他頂點到初始頂點的距離=當前頂點到初始頂點距離+當前頂點到其他頂點的距離
int sPathDist = sPath[column].distance; //獲得column處頂點到起始頂點的距離，如果不與初始頂點相鄰，默認值都是無窮大
if(startToFringe < sPathDist) {
sPath[column].parentVert = currentVert; //修改其父頂點
sPath[column].distance = startToFringe; //以及到初始頂點的距離
}
column++;
}
}
//顯示路徑
private void displayPaths() {
for(int i = 0; i < nVerts; i++) {
System.out.print(vertexArray[i].label + "=");
if(sPath[i].distance == INFINITY)
System.out.print("infinity");
else
System.out.print(sPath[i].distance);
char parent = vertexArray[sPath[i].parentVert].label;
System.out.print("(" + parent + ") ");
}
System.out.println("");
}
由於圖的表示法有兩種，鄰接矩陣和鄰接表。是的圖的算法效率問題變得相對復雜。如果使用鄰接矩陣，前面討論的算法大多需要O(V2)的時間級，V表示頂點數量。因為這些算法幾乎都檢查了一遍所有的頂點，具體方法是在鄰接矩陣中掃描每一行，一次查看每一條邊。換句話說，鄰接矩陣的V2個單元都被掃描過。
對於大規模的矩陣，O(V2)的時間基本是非常好的性能。如果圖是密集的，那就沒什麼提高性能的余地了（密集意味著圖有很多邊，而它的鄰接矩陣的許多或大部分單元被占）。然而，許多圖是稀疏的，其實並沒有一個確定數量的定義說明多少條邊的圖才是密集的或稀疏的，但如果在一個大圖中每個頂點只有很少幾條邊相連，那麼這個圖通常被認為是稀疏的。
在稀疏圖中，使用鄰接表的表示方法代替鄰接矩陣，可以改善運行時間，因為不必浪費時間來檢索鄰接矩陣中沒有邊的單元。對於無權圖，鄰接表的深度優先搜索需要O(V+E)的時間級，V是頂點數量，E是邊數。對於帶權圖，最小生成樹算法和最短路徑算法都需要O(E+V)logV)的時間級，在大型的稀疏圖中，與鄰接矩陣方法的時間級O(V2)相比，這樣的時間級可使性能大幅提升，但是算法會復雜一些。
package graph;
/**
* @desciption 帶權圖的完整代碼
* @author eson_15
*/
//邊界路徑類
class Edge {
public int srcVert; //index of vertex starting edge
public int destVert; //index of vertex ending edge
public int distance; //distance from src to dest
public Edge(int sv, int dv, int d) {
srcVert = sv;
destVert = dv;
distance = d;
}
}
//優先隊列
class PriorityQ {
private final int SIZE = 20;
private Edge[] queArray; //存儲邊界的數組
private int size;
public PriorityQ() {
queArray = new Edge[SIZE];
size = 0;
}
public void insert(Edge item) { //有序的插入邊界
int j;
for(j = 0; j < size; j++) { //找到插入的位置，從0到size-1，逐漸減小
if(item.distance >= queArray[j].distance)
break;
}
//比item.distance小的往後挪一位，給騰出個空間
for(int k = size-1; k >= j; k--) {
queArray[k+1] = queArray[k];
}
queArray[j] = item; //插入item
size++;
}
public Edge removeMin() { //刪除最小的邊界並返回
return queArray[--size];
}
public void removeN(int n) { //刪除n位置的邊界
for(int j = n; j < size-1; j++) {
queArray[j] = queArray[j+1];
}
size--;
}
public Edge peekMin() { //返回最小邊界，不刪除
return queArray[size-1];
}
public Edge peekN(int n) { //返回n位置的邊界
return queArray[n];
}
public int size() {
return size;
}
public boolean isEmpty() {
return (size == 0);
}
public int find(int findDex) { //尋找特定disVert的邊界索引
for(int j = 0; j < size; j++) {
if(queArray[j].destVert == findDex)
return j;
}
return -1;
}
}
//DistPar類記錄了當前頂點到起始頂點點的距離和當前頂點的父頂點
class DistPar {
public int distance; //distance from start to this vertex
public int parentVert; //current parent of this vertex
public DistPar(int pv, int d) {
distance = d;
parentVert = pv;
}
}
//帶權圖類
public class WeightedGraph {
private final int MAX_VERTS = 20; //最大頂點數
private final int INFINITY = 100000; //最遠距離...表示無法達到
private Vertex[] vertexArray; //存儲頂點的數組
private int adjMat[][]; //存儲頂點之間的邊界
private int nVerts; //頂點數量
private int currentVert; //當前頂點索引
private PriorityQ thePQ; //
private int nTree; //最小生成樹中的頂點數量
private DistPar[] sPath; //存儲最短路徑數據
private int startToCurrent; //到當前頂點的距離
public WeightedGraph() {
vertexArray = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
for(int i = 0; i < MAX_VERTS; i++) {
for(int j = 0; j < MAX_VERTS; j++) {
adjMat[i][j] = INFINITY; //初始化所有邊界無窮遠
}
}
thePQ = new PriorityQ();
sPath = new DistPar[MAX_VERTS];
}
public void addVertex(char lab) { //添加頂點
vertexArray[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end, int weight) {//添加帶權邊界
adjMat[start][end] = weight;
adjMat[end][start] = weight; //最優路徑的時候不需要這句
}
public void displayVertex(int v) {
System.out.print(vertexArray[v].label);
}
/************************ 帶權圖的最小生成樹 ***************************/
public void MinSpanningTree() {
currentVert = 0; //從0開始
while(nTree < nVerts-1) { //當不是所有節點都在最小生成樹中時
vertexArray[currentVert].isInTree = true; //將當前頂點加到樹中
nTree++;
//往PQ中插入與當前頂點相鄰的一些邊界
for(int i = 0; i < nVerts; i++) {
if(i == currentVert) //如果是本頂點，跳出
continue;
if(vertexArray[i].isInTree) //如果頂點i已經在樹中，跳出
continue;
int distance = adjMat[currentVert][i]; //計算當前頂點到i頂點的距離
if(distance == INFINITY)
continue; //如果當前頂點與i頂點無窮遠，跳出
putInPQ(i, distance); //將i節點加入PQ中
}
if(thePQ.size() == 0) { //如果PQ為空，表示圖不連接
System.out.println("Graph not connected!");
return;
}
Edge theEdge = thePQ.removeMin();
int sourceVert = theEdge.srcVert;
currentVert = theEdge.destVert;
System.out.print(vertexArray[sourceVert].label);
System.out.print(vertexArray[currentVert].label);
System.out.print(" ");
}
}
private void putInPQ(int newVert, int newDist) {
int queueIndex = thePQ.find(newVert);//判斷PQ中是否已經有到相同目的頂點的邊界
if(queueIndex != -1) { //如果有則與當前頂點到目的頂點的距離作比較，保留短的那個
Edge tempEdge = thePQ.peekN(queueIndex);//get edge
int oldDist = tempEdge.distance;
if(oldDist > newDist) { //如果新的邊界更短
thePQ.removeN(queueIndex); //刪除舊邊界
Edge theEdge = new Edge(currentVert, newVert, newDist);
thePQ.insert(theEdge);
}
}
else { //如果PQ中沒有到相同目的頂點的邊界
Edge theEdge = new Edge(currentVert, newVert, newDist);
thePQ.insert(theEdge);//直接添加到PQ
}
}
/************************** 最短路徑問題 ****************************/
/**
* path()方法執行真正的最短路徑算法。
*/
public void path() { //尋找所有最短路徑
/*
* 源點總在vertexArray[]數組下標為0的位置，path()方法的第一個任務就是把這個頂點放入樹中。
* 算法執行過程中，將會把其他頂點也逐一放入樹中。把頂點放入樹中的操作是設置一下標志位即可。
* 並把nTree變量增1，這個變量記錄了樹中有多少個頂點。
*/
int startTree = 0; //從vertex 0開始
vertexArray[startTree].isInTree = true;
nTree = 1;
/*
* path()方法把鄰接矩陣的對應行表達的距離復制到sPath[]中，實際總是先從第0行復制
* 為了簡單，假定源點的下標總為0。最開始，所有sPath[]數組中的父節點字段為A，即源點。
*/
for(int i = 0; i < nVerts; i++) {
int tempDist = adjMat[startTree][i];
//sPath中保存的都是到初始頂點的距離，所以父頂點默認都是初始頂點，後面程序中會將其修改
sPath[i] = new DistPar(startTree, tempDist);
}
/*
* 現在進入主循環，等到所有的頂點都放入樹中，這個循環就結束，這個循環有三個基本動作：
* 1. 選擇sPath[]數組中的最小距離
* 2. 把對應的頂點（這個最小距離所在列的題頭）放入樹中，這個頂點變成“當前頂點”currentVert
* 3. 根據currentVert的變化，更新所有的sPath[]數組內容
*/
while(nTree < nVerts) {
//1. 選擇sPath[]數組中的最小距離
int indexMin = getMin(); //獲得sPath中的最小路徑值索引
int minDist = sPath[indexMin].distance; //獲得最小路徑
if(minDist == INFINITY) {
System.out.println("There are unreachable vertices");
break;
}
//2. 把對應的頂點（這個最小距離所在列的題頭）放入樹中，這個頂點變成“當前頂點”currentVert
else { //reset currentVert
currentVert = indexMin;
startToCurrent = sPath[indexMin].distance;
}
vertexArray[currentVert].isInTree = true;
nTree++;
//3. 根據currentVert的變化，更新所有的sPath[]數組內容
adjust_sPath();
}
displayPaths();
nTree = 0;
for(int i = 0; i < nVerts; i++) {
vertexArray[i].isInTree = false;
}
}
//獲取sPath中最小路徑的索引
private int getMin() {
int minDist = INFINITY;
int indexMin = 0;
for(int i = 0; i < nVerts; i++) {
if(!vertexArray[i].isInTree && sPath[i].distance < minDist) {
minDist = sPath[i].distance;
indexMin = i;
}
}
return indexMin;
}
/*調整sPath中存儲的對象的值，即頂點到初始頂點的距離，和頂點的父頂點
* 這是Dijkstra算法的核心
*/
private void adjust_sPath() {
int column = 1;
while(column < nVerts) {
if(vertexArray[column].isInTree) {
column++;
continue;
}
int currentToFringe = adjMat[currentVert][column]; //獲得當前頂點到其他頂點的距離，其他頂點不滿足isInTree
int startToFringe = startToCurrent + currentToFringe; //計算其他頂點到初始頂點的距離=當前頂點到初始頂點距離+當前頂點到其他頂點的距離
int sPathDist = sPath[column].distance; //獲得column處頂點到起始頂點的距離，如果不與初始頂點相鄰，默認值都是無窮大
if(startToFringe < sPathDist) {
sPath[column].parentVert = currentVert; //修改其父頂點
sPath[column].distance = startToFringe; //以及到初始頂點的距離
}
column++;
}
}
//顯示路徑
private void displayPaths() {
for(int i = 0; i < nVerts; i++) {
System.out.print(vertexArray[i].label + "=");
if(sPath[i].distance == INFINITY)
System.out.print("infinity");
else
System.out.print(sPath[i].distance);
char parent = vertexArray[sPath[i].parentVert].label;
System.out.print("(" + parent + ") ");
}
System.out.println("");
}
}
下面是測試用例：
package test;
import graph.WeightedGraph;
public class Test {
public static void main(String[] args){
WeightedGraph arr = new WeightedGraph();
arr.addVertex('A');
arr.addVertex('B');
arr.addVertex('C');
arr.addVertex('D');
arr.addVertex('E');
arr.addEdge(0, 1, 50); //AB 50
arr.addEdge(0, 3, 80); //AD 80
arr.addEdge(1, 2, 60); //BC 60
arr.addEdge(1, 3, 90); //BD 90
arr.addEdge(2, 4, 40); //CE 40
arr.addEdge(3, 2, 20); //DC 20
arr.addEdge(3, 4, 70); //DE 70
arr.addEdge(4, 1, 50); //EB 50
arr.MinSpanningTree(); //最小生成樹
System.out.println(" ");
arr.path(); //最短路徑
}
}
輸出結果為：
AB BE EC CD A=infinity(A) B=50(A) C=100(D) D=80(A) E=100(B)
