目錄

1、相關(guān)術(shù)語

2、圖的表示

2.1艳悔、鄰接矩陣

2.2、鄰接表

3萝挤、圖的遍歷

3.1、深度優(yōu)先搜索

3.2纸淮、廣度優(yōu)先搜索

3.3平斩、二者的比較

4、拓?fù)渑判?/h3>

5咽块、最短路徑算法

5.1绘面、無權(quán)圖中的最短路徑

5.2、有權(quán)圖中的最短路徑

5.3侈沪、Bellman-Ford算法

6揭璃、最小生成樹

6.1、Prim算法

6.2亭罪、Kruskal算法

正文

1瘦馍、相關(guān)術(shù)語

• 圖：一個圖可以表示為 （V，E）应役，其中 V 是結(jié)點(diǎn)的集合情组，稱為 頂點(diǎn) 燥筷；E是頂點(diǎn)對的集合，稱為 邊 院崇。頂點(diǎn)和邊代表位置和存儲元素肆氓，下述是相關(guān)定義：

• 有向邊：
  1）有序頂點(diǎn)對（u，v）底瓣。
  2）第一個頂點(diǎn)u是源點(diǎn)谢揪。
  3）第二個頂點(diǎn)v是終點(diǎn)。

  
  
  圖1-1 有向邊

• 無向邊
  1）無序頂點(diǎn)對（u捐凭，v）拨扶。

  
  
  圖1-2 無向邊

• 有向圖
  1）所有的邊都是有向邊。

  
  
  圖1-3 有向圖

• 無向圖
  1）所有的邊都是無向邊茁肠。

  
  
  圖1-4 無向圖
• 無環(huán)圖稱為 樹患民，樹是不包含環(huán)的連通圖。
  
  圖1-5 樹

• 自環(huán)指的是一條連接頂點(diǎn)及其自身的邊官套。

  
  
  圖1-6 自環(huán)
• 頂點(diǎn)的度是指關(guān)聯(lián)該頂點(diǎn)的邊的數(shù)目酒奶。
• 子圖是圖的邊（及邊所關(guān)聯(lián)的頂點(diǎn)）的子集形成的圖蚁孔。

• 圖中的路徑是指一系列的相鄰頂點(diǎn)奶赔。簡單路徑是一條不包含重復(fù)頂點(diǎn)的路徑。

  
  
  圖1-7 簡單路徑

• 環(huán)路是起點(diǎn)與終點(diǎn)相同的路徑杠氢。簡單環(huán)路是不包含重復(fù)頂點(diǎn)和邊的環(huán)（除了起點(diǎn)和終點(diǎn)外）站刑。

  
  
  圖1-8 簡單環(huán)路
• 如果兩個頂點(diǎn)之間存在一條路徑，則稱這兩個頂點(diǎn)是連通的鼻百。
• 如果圖中每對頂點(diǎn)之間都有路徑相連绞旅，則該圖是連通圖。

• 如果一個圖是非連通的温艇，那么它由一組連通分量構(gòu)成因悲。

  
  
  圖1-9 連通分量
• 連通圖的生成樹是一個包含所有頂點(diǎn)的子圖，并且是一棵單獨(dú)的樹勺爱。圖的生成森林是連通分量的生成樹的集合晃琳。

• 在一個有權(quán)圖中，給每條邊賦值一個整數(shù)（權(quán)重）來代表（距離或花費(fèi)）琐鲁。

  
  
  圖1-10 有權(quán)圖

2卫旱、圖的表示

• 圖有以下兩種表示形式：
  1）、鄰接矩陣
  2）围段、鄰接表

2.1顾翼、鄰接矩陣

• 圖的表示需要頂點(diǎn)數(shù)、邊數(shù)以及它們之間的連接關(guān)系奈泪。該方法采用一個大小為 V*V的矩陣Adj适贸，其中矩陣的指為布爾值灸芳。如果存在一條從u到v的邊，則設(shè)置Adj[u拜姿，v]=1耗绿，否則為0。

  
  
  圖2-1 有向圖

• 圖2-1的鄰接矩陣可以表示為：

  
  
  圖2-2 鄰接矩陣
• 讀無向圖的代碼實(shí)現(xiàn)如下：

    public class Graph {
        private bool[,] adjMatrix;

        private int vertexCount;

        public Graph(int vertexCount) {
            this.vertexCount = vertexCount;
            adjMatrix = new bool[vertexCount,vertexCount];
        }

        public void addEdge(int i,int j) {
            if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
                adjMatrix[i, j] = true;
                adjMatrix[j, i] = true;
            }
        }

        public void removeEdge(int i,int j) {
            if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
                adjMatrix[i, j] = false;
                adjMatrix[j, i] = false;
            }
        }

        public bool isEdge(int i,int j) {
            if (i >= 0 && i < vertexCount && j >= 0 && j < vertexCount) {
                return adjMatrix[i, j];
            }
            else {
                return false;
            }
        }
    }

2.2砾隅、鄰接表

• 圖的鄰接表表示方式如圖2-3所示误阻。在這種方式下，所有與某個頂點(diǎn)v相連的頂點(diǎn)都在v的鄰接表中列出晴埂，采用鏈表容易實(shí)現(xiàn)究反。

  
  
  圖2-3 鄰接表
• 代碼實(shí)現(xiàn)

    public class GraphByLinkList {
        private ArrayList<int> vertices;

        private ListNode[] edges;

        private int vertexCount;

        public GraphByLinkList(int vertexCount) {
            this.vertexCount = vertexCount;
            vertices = new ArrayList<int>();
            edges = new ListNode[vertexCount];
            for(int i = 0; i < vertexCount; i++) {
                vertices.add(i);
                edges[i] = new ListNode();
            }
        }

        public void addEdge(int source,int destination) {
            int i = vertices.indexOf(source);
            int j = vertices.indexOf(destination);
            if (i != -1 || j != -1) {
                edges[i].insertAtBeginning(destination);
                edges[j].insertAtBeginning(source);
            }
        }
    }

• 鄰接表的缺點(diǎn)：以刪除某個結(jié)點(diǎn)為例，如果直接刪除該結(jié)點(diǎn)是可以做到的儒洛，然而精耐，在鄰接表中當(dāng)該結(jié)點(diǎn)和其他結(jié)點(diǎn)有邊相連時，則必須搜索其他結(jié)點(diǎn)對應(yīng)的鏈表來刪除該結(jié)點(diǎn)琅锻。

3卦停、圖的遍歷

3.1、深度優(yōu)先搜索

• 深度優(yōu)先搜索的算法原理類似于樹的前序遍歷恼蓬，本質(zhì)上也是用棧來實(shí)現(xiàn)惊完。以 “迷宮” 為例子，為了走出迷宮处硬，這個人需要訪問每條 路徑 和每一個 十字路口（最壞情況下）小槐。假設(shè)此人使用兩種顏色的涂料來標(biāo)記已經(jīng)經(jīng)過的十字路口。當(dāng)發(fā)現(xiàn)一個十字路口時荷辕，將其標(biāo)為 灰色 凿跳，并且繼續(xù)往更深處走。當(dāng)?shù)竭_(dá)一個 “末端” 時疮方，則表明從標(biāo)記為 灰色 的十字路口出發(fā)的所有路徑都已經(jīng)訪問過控嗜，并且將該十字路口標(biāo)記為 黑色 。
• 迷宮的十字路口是圖的 頂點(diǎn) 骡显，而十字路口之間的路徑就是圖的 邊疆栏，從末端返回的過程叫作 “回溯”。算法便是嘗試從起點(diǎn)開始盡可能 深 地訪問圖中的結(jié)點(diǎn)蟆盐，直到 回溯到先前的灰色結(jié)點(diǎn)承边。在算法中，包括如下類型的邊：
  1）石挂、樹邊：遇到一個新頂點(diǎn)的邊博助。
  2）、前向邊：從祖先到子孫的邊痹愚。
  3）富岳、回退邊：從子孫到祖先的邊蛔糯。
  4）、交叉邊：在一棵樹或子樹之間的邊窖式。
• 初始時所有頂點(diǎn)都被標(biāo)記為未被訪問過（false）蚁飒。深度優(yōu)先搜索算法從圖中的一個頂點(diǎn)u開始，首先考慮從u到其它頂點(diǎn)的邊萝喘。如果該邊通往一個已經(jīng)被訪問過的頂點(diǎn)淮逻，則 回溯 到當(dāng)前頂點(diǎn)u。如果該邊通往一個 未曾訪問過的頂點(diǎn) 阁簸，則到達(dá)該頂點(diǎn)爬早，并從該頂點(diǎn)進(jìn)行訪問，即 將新的頂點(diǎn)變?yōu)楫?dāng)前頂點(diǎn) 启妹。重復(fù)這個過程直到算法到達(dá) “末端”筛严。然后從 “末端” 點(diǎn)開始 回溯 。當(dāng)回溯到 起始點(diǎn) 時結(jié)束饶米。
• 代碼實(shí)現(xiàn)

    public class Vertex {
        public char label { get; set; }
        public bool visited { get; set; }

        public Vertex(char label) {
            this.label = label;
            visited = false;
        }
    }

    public class Graph {
        private const int maxVertices = 20;

        /// <summary>
        /// 訪問表
        /// </summary>
        private Vertex[] vertexList;

        /// <summary>
        /// 鄰接表
        /// </summary>
        private int[,] adjMatrix;

        /// <summary>
        /// 頂點(diǎn)數(shù)
        /// </summary>
        private int vertexCount;

        /// <summary>
        /// 訪問路徑
        /// </summary>
        private Stack<int> theStack;

        public Graph() {
            vertexList = new Vertex[maxVertices];
            adjMatrix = new int[maxVertices, maxVertices];
            vertexCount = 0;
            for(int y = 0; y < maxVertices; y++) {
                for(int x = 0; x < maxVertices; x++) {
                    adjMatrix[x, y] = 0;
                }
            }
            theStack = new Stack<int>();
        }

        public void addVertex(char label) {
            vertexList[vertexCount++] = new Vertex(label);
        }

        public void addEdge(int start,int end) {
            adjMatrix[start, end] = 1;
            adjMatrix[end, start] = 1;
        }

        public void displayVertex(int v) {
            Console.Out.WriteLine(vertexList[v].label);
        }

        /// <summary>
        /// 深度優(yōu)先搜索算法
        /// </summary>
        public void dfs() {
            vertexList[0].visited = true;
            displayVertex(0);
            theStack.Push(0);
            while (theStack.Count > 0) {
                int v = getAdjUnvisitedVertex(theStack.Peek());
                if (v == -1) {
                    theStack.Pop();
                }
                else {
                    vertexList[v].visited = true;
                    displayVertex(v);
                    theStack.Push(v);
                }
            }
            for(int j = 0; j < vertexCount; j++) {
                vertexList[j].visited = false;
            }
        }

        /// <summary>
        /// 獲取從v頂點(diǎn)開始路徑中桨啃，未被訪問的頂點(diǎn)
        /// </summary>
        /// <param name="v">起始點(diǎn)</param>
        /// <returns>未訪問點(diǎn)</returns>
        public int getAdjUnvisitedVertex(int v) {
            for(int j = 0; j < vertexCount; j++) {
                if (adjMatrix[v, j] == 1 && vertexList[j].visited == false) {
                    return j;
                }
            }
            return -1;
        }
    }

• 在下圖示例中，灰色 表示該頂點(diǎn)被訪問過檬输，需要注意的是 訪問表 何時被更新照瘾。
  
  圖3-1

圖3-2

圖3-3

圖3-4

圖3-5

圖3-6

圖3-7

圖3-8

3.2、廣度優(yōu)先搜索

• 廣度優(yōu)先搜索算法的原理類似 樹的層次遍歷褪猛，并且算法使用了 隊(duì)列网杆。初始時羹饰，從一個給定的頂點(diǎn)出發(fā)伊滋，該頂點(diǎn)位于 第0層。第一步队秩，它將訪問所有處于 第一層 的頂點(diǎn)（即從圖中到起始頂點(diǎn)距離為1的頂點(diǎn)）笑旺。第二步，訪問 第二層 所有的頂點(diǎn)馍资，即與 第一層 相鄰的頂點(diǎn)筒主。算法重復(fù)該過程，直至圖的所有層訪問一遍鸟蟹。
• 假設(shè)初始時所有頂點(diǎn)都被標(biāo)記為未曾訪問過（false）乌妙，已經(jīng)處理過并且從隊(duì)列移除 的頂點(diǎn)標(biāo)記為已訪問過（true）。利用 另一個隊(duì)列 來表示已經(jīng)訪問過的頂點(diǎn)的集合建钥，該隊(duì)列記錄頂點(diǎn)第一次被訪問的順序藤韵。
• 代碼實(shí)現(xiàn)

    public class Vertex {
        public char label { get; set; }
        public bool visited { get; set; }
        public Vertex(char label) {
            this.label = label;
            visited = false;
        }
    }

    public class Graph {
        private const int maxVertices = 20;

        /// <summary>
        /// 訪問表
        /// </summary>
        private Vertex[] vertexList;

        /// <summary>
        /// 鄰接表
        /// </summary>
        private int[,] adjMatrix;

        /// <summary>
        /// 頂點(diǎn)數(shù)
        /// </summary>
        private int vertexCount;

        /// <summary>
        /// 訪問路徑
        /// </summary>
        private Queue<int> theQueue;

        public Graph() {
            vertexList = new Vertex[maxVertices];
            adjMatrix = new int[maxVertices, maxVertices];
            vertexCount = 0;
            for(int y = 0; y < maxVertices; y++) {
                for(int x = 0; x < maxVertices; x++) {
                    adjMatrix[x,y] = 0;
                }
            }
            theQueue = new Queue<int>();
        }

        public void addVertex(char label) {
            vertexList[vertexCount++] = new Vertex(label);
        }

        public void addEdge(int start, int end) {
            adjMatrix[start, end] = 1;
            adjMatrix[end, start] = 1;
        }

        public void displayVertex(int v) {
            Console.Out.WriteLine(vertexList[v].label);
        }

        /// <summary>
        /// 廣度優(yōu)先搜索算法
        /// </summary>
        public void bfs() {
            vertexList[0].visited = true;
            displayVertex(0);
            theQueue.Enqueue(0);
            int v2;
            while (theQueue.Count > 0) {
                int v1 = theQueue.Dequeue();
                while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
                    vertexList[v2].visited = true;
                    displayVertex(v2);
                    theQueue.Enqueue(v2);
                }
            }
            for (int j = 0; j < vertexCount; j++) {
                vertexList[j].visited = false;
            }
        }

        /// <summary>
        /// 獲取從v頂點(diǎn)開始路徑中，未被訪問的頂點(diǎn)
        /// </summary>
        /// <param name="v">起始點(diǎn)</param>
        /// <returns>未訪問點(diǎn)</returns>
        public int getAdjUnvisitedVertex(int v) {
            for (int j = 0; j < vertexCount; j++) {
                if (adjMatrix[v, j] == 1 && vertexList[j].visited == false) {
                    return j;
                }
            }
            return -1;
        }
    }

• 廣度優(yōu)先搜索算法的示例圖如下：

  
  
  圖3-9

圖3-10

圖3-11

3.3熊经、二者的比較

• 深度優(yōu)先搜索 的最大優(yōu)勢在于它的 內(nèi)存開銷 要遠(yuǎn)遠(yuǎn) 小于廣度優(yōu)先搜索 泽艘，因?yàn)樗恍枰鎯γ恳粚拥慕Y(jié)點(diǎn)的所有孩子結(jié)點(diǎn)指針欲险。但其實(shí)二者哪個更好？答案取決于需要解決的問題類型匹涮。廣度優(yōu)先搜索每次訪問一層天试，若預(yù)先知道需要搜索的結(jié)果處在一個 較低的深度，那么 廣度優(yōu)先搜索 是合適的然低。如果處于 較大深度喜每，那么 深度優(yōu)先搜索 是更好的選擇。

4来农、拓?fù)渑判?/h3>

• 拓?fù)渑判?/strong> 是在一個 有向無環(huán)圖 中對 頂點(diǎn) 的排序鞋真。在這個有向無環(huán)圖中，每個頂點(diǎn)都排在所有以它為起點(diǎn)的相鄰結(jié)點(diǎn)之前沃于。
• 如果排好序的 所有連續(xù)頂點(diǎn)對之間都是有邊相連涩咖，那么這些邊會在圖中形成一個 有向哈密頓路徑。若有 一條 哈密頓路徑存在繁莹，則拓?fù)渑判虻牡捻樞蚴?唯一的檩互。如果 沒有 形成哈密頓路徑，則圖中可能有 兩個或者多個 的拓?fù)渑判颉?/li>
• 圖4-1中咨演，7闸昨，5，3薄风，11饵较，8，2遭赂，9循诉，10 和 3，5撇他，7茄猫，8，11困肩，2划纽，9，10都是 拓?fù)渑判?/strong>锌畸。
  
  圖4-1 示例
• 初始時勇劣，計(jì)算所有頂點(diǎn)的入度，并從 入度為0的頂點(diǎn)出發(fā)蹋绽，因?yàn)檫@些頂點(diǎn)沒有任何先決條件芭毙〗畋停可以使用隊(duì)列來跟蹤這些入度為0的頂點(diǎn)。
• 將所有 入度為0 的頂點(diǎn)放入隊(duì)列中退敦，當(dāng)隊(duì)列不為空時粘咖，從隊(duì)列中移除頂點(diǎn)v，并將v的所有 相鄰頂點(diǎn)的入度減1 侈百。一旦某個頂點(diǎn) 入度變?yōu)?瓮下，就將其放入隊(duì)列中。因此钝域，拓?fù)渑判蚓褪顷?duì)列中的頂點(diǎn) 出隊(duì)的順序讽坏。
• 代碼實(shí)現(xiàn)

        public void TopologicalSort(Graph G) {
            LLQueue Q = new LLQueue();
            int counter;
            int v;
            counter = 0;
            //初始入隊(duì)所有入度為0的頂點(diǎn)
            for (v = 0; v < G.vertexCount; v++) {
                if (G.indegree[v] == 0) {
                    Q.enQueue(v);
                }
            }
            while (!Q.isEmpty()) {
                v = Q.deQueue();
                topologicalOrder[v] = ++counter;
                //獲取與v相鄰的所有頂點(diǎn)
                var list = GetAdjacentTo(v);
                foreach(int w in list) {
                    if (--G.indegree[w] == 0) {
                        Q.enQueue(w);
                    }
                }
            }
            if (counter != G.vertexCount) {
                Console.Out.Write("Graph has cycle");
            }
            Q.deleteQueue();
        }

5、最短路徑算法

• 給定一個圖G=（V例证，E）和一個特殊頂點(diǎn)s路呜，需要查找從s到圖中其它頂點(diǎn)的最短路徑。但是根據(jù)輸入圖形的類型不同织咧，最短路徑算法會有相應(yīng)的變化胀葱，主要包括以下三種：
  1）無權(quán)圖中的最短路徑
  2）有權(quán)圖中的最短路徑
  3）帶有負(fù)邊的有權(quán)圖中的最短路徑

5.1、無權(quán)圖中的最短路徑

• 假設(shè)要尋找 某個輸入頂點(diǎn)s 到所有其他頂點(diǎn)的 最短路徑 笙蒙。無權(quán)圖是有權(quán)圖最短路徑問題的特例抵屿，即邊的權(quán)重都是1。
• 算法實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)：
  1）距離表：①當(dāng)前頂點(diǎn)到源點(diǎn)的距離捅位；②路徑——包含最短路徑上經(jīng)過的頂點(diǎn)轧葛。
  2）一個用于實(shí)現(xiàn) 廣度優(yōu)先搜索的隊(duì)列,它包含到 源點(diǎn)距離已知的結(jié)點(diǎn) 以及 尚未訪問的相鄰頂點(diǎn)。
• 以圖5-1為例艇搀，設(shè)s=C尿扯，從C到C的距離是 0。初始時，C到其它頂點(diǎn)的距離未確定唉韭，將距離表上除了C以外的其它頂點(diǎn)的第二列（到源點(diǎn)的距離）設(shè)為 -1，如下表所示。
  
  圖5-1 無權(quán)圖示例

頂點(diǎn)	Distance[v]	獲得Distance[v]的前一個頂點(diǎn)
A	-1	——
B	-1	——
C	0	——
D	-1	——
E	-1	——
F	-1	——
G	-1	——

• 代碼實(shí)現(xiàn)：

        public void UnWeightedShortestPath(Graph G, int s) {
            LLQueue Q = new LLQueue();
            int v;
            Q.enQueue(s);
            for (int i = 0; i < G.vertexCount; i++) {
                Distance[i] = -1;
            }
            Distance[s] = 0;
            while (!Q.isEmpty()) {
                v = Q.deQueue();
                //獲取與頂點(diǎn)v相鄰的頂點(diǎn)集合
                var list = GetAdjacentTo(v);
                foreach (int w in list) {
                    //每個頂點(diǎn)最多檢查一次
                    if (Distance[w] == -1) {
                        Distance[w] = Distance[v] + 1;
                        //存放最短路徑中的上一個頂點(diǎn)
                        Path[w] = v;
                        //每個頂點(diǎn)最多入隊(duì)一次
                        Q.enQueue(w);
                    }
                }
            }
            Q.deleteQueue();
        }

• 如果使用 鄰接表 表示 拒垃，則運(yùn)行時間為 O（| E |+| V |）。在 for循環(huán)中难审，算法檢查每個頂點(diǎn)的 出邊沙绝；在while循環(huán)中所有訪問過的邊的和等于邊的數(shù)目，即為 O（| E |）亚再。
• 如果使用 矩陣 表示郭膛，則時間復(fù)雜度是 O（| V |^2），因?yàn)楸仨氃?長度為 | V | 的矩陣中讀入一整行氛悬，以便查找給定頂點(diǎn)的相鄰頂點(diǎn)则剃。

5.2耘柱、有權(quán)圖中的最短路徑（Dijkstra算法）

• 算法：與 5.1的無權(quán)圖的最短路徑 類似，也將會使用 距離表棍现。算法在距離表中保存從源點(diǎn)到頂點(diǎn)v的最短路徑调煎。Distance[v]記錄從s到v的距離。源點(diǎn)到它自身的最短距離為0己肮。而距離表中將一個頂點(diǎn)到另一個頂點(diǎn)的距離設(shè)為 -1 來表示 尚為訪問過的頂點(diǎn)士袄。
  1)采用貪婪法：總是選取最接近源點(diǎn)的頂點(diǎn)。
  2)使用優(yōu)先隊(duì)列并按照到s的距離來存儲未被訪問過的頂點(diǎn)谎僻。
  3)不能用于權(quán)值為負(fù)值的情況娄柳。
• 舉例說明：
  如圖5-2所示的有權(quán)圖中有A~E5個頂點(diǎn)，兩個頂點(diǎn)之間的值即為邊的權(quán)重艘绍，利用 Dijkstra算法查找從源點(diǎn)A到其它頂點(diǎn)的最短路徑赤拒。
  
  圖5-2 有權(quán)圖
  
  初始化距離表為：

頂點(diǎn)	Distance[v]	獲得Distance[v]的前一個頂點(diǎn)
A	0	——
B	-1	——
C	-1	——
D	-1	——
E	-1	——
F	-1	——

1)、完成初始化后诱鞠，從頂點(diǎn)A能夠到達(dá)B和C需了，因此在距離表中以相應(yīng)的邊權(quán)值來更新頂點(diǎn)B和C的可達(dá)性，如圖5-3所示般甲。

圖5-3 第一步

2)肋乍、從距離表中選擇一個最小距離，可知最小距離是頂點(diǎn)C敷存。這表明必須通過這兩個頂點(diǎn)（A和C）才能到達(dá)其它頂點(diǎn)墓造。而A和C都能到達(dá)頂點(diǎn)B锚烦，這種情況下要選擇代價(jià)小的路徑孕锄，因?yàn)镃到B的代價(jià)（1+2）更小，所以距離表中用3和頂點(diǎn)C來更新恬涧。通過C還可以到達(dá)頂點(diǎn)D，因此也相應(yīng)的更新距離表中頂點(diǎn)D的值售碳。如圖5-4所示圾亏。

圖5-4 第二步

3)陕见、當(dāng)前唯一未被訪問的結(jié)點(diǎn)為E，為了到達(dá) E韧骗，需要找出所有可以到達(dá)E的路徑并選擇其中代價(jià)最小的路徑，可以發(fā)現(xiàn)袍暴，當(dāng)使用經(jīng)過C到達(dá)的B頂點(diǎn)作為中間頂點(diǎn)時具有最小代價(jià)些侍。如圖5-5所示。

圖5-5 第三步

4)政模、最終產(chǎn)生的最小代價(jià)樹如圖5-6所示岗宣。

圖5-6 最小代價(jià)樹

• 代碼實(shí)現(xiàn)：

        public void Dijkstra(Graph G,int s) {
            Heap PQ = new Heap();
            int v;
            PQ.enQueue(s);
            for(int i = 0; i < G.vertexCount; i++) {
                Distance[i] = -1;
            }
            Distance[s] = 0;
            while (!PQ.isEmpty()) {
                v = PQ.deleteMin();
                //獲取與頂點(diǎn)v相鄰的頂點(diǎn)集合
                var list = GetAdjacentTo(v);
                foreach (int w in list) {
                    int d = Distance[v] + weight[v, w];
                    //判斷頂點(diǎn)w是否被訪問過
                    if (Distance[w] == -1) {
                        //更新頂點(diǎn)w到源點(diǎn)的值
                        Distance[w] = d;
                        //加入優(yōu)先隊(duì)列
                        PQ.enQueue(w);
                        //更新頂點(diǎn)w的最短路徑的上一頂點(diǎn)
                        Path[w] = v;
                    }
                    //判斷當(dāng)前路徑是否最短
                    if (Distance[w] > d) {
                        Distance[w] = d;
                        //更新頂點(diǎn)w的最短路徑的上一頂點(diǎn)
                        Path[w] = v;
                    }
                }
            }
        }

5.3、Bellman-Ford算法

• Dijkstra算法不能處理邊值為負(fù)的情況淋样。這是由于當(dāng)某個頂點(diǎn)u被標(biāo)記為已訪問時耗式，仍然存在這樣一種可能，即存在一條從某個未被訪問過的頂點(diǎn)v到u的負(fù)路徑趁猴。在這種情況下刊咳，從s出發(fā)經(jīng)過v再到u的路徑長度小于從s出發(fā)到u但不經(jīng)過v的路徑的長度。
• Dijstra算法與無權(quán)圖算法相結(jié)合可以解決這個問題儡司，用S初始化隊(duì)列娱挨，然后在每一步將頂點(diǎn)v出隊(duì)，找到v的所有相鄰頂點(diǎn)w使得：到v的距離+邊（v,w）的權(quán)值<到w的原有距離捕犬。對w的原有距離和路徑進(jìn)行更新跷坝，并且若w不在隊(duì)列中，則入隊(duì)或听√叫ⅲ可以為每個頂點(diǎn)設(shè)置一個標(biāo)記位來表示它是否在隊(duì)列中，重復(fù)該過程直至隊(duì)列為空誉裆。
• 代碼實(shí)現(xiàn)：

        public void BellmanFordAlgorihm(Graph G,int s) {
            LLQueue Q = new LLQueue();
            int v;
            Q.enQueue(s);
            //假定用 INT_MAX填充距離表
            Distance[s] = 0;
            while (!Q.isEmpty()) {
                v = Q.deQueue();
                //獲取與頂點(diǎn)v相鄰的頂點(diǎn)集合
                var list = GetAdjacentTo(v);
                foreach (int w in list) {
                    int d = Distance[v] + weight[v, w];
                    if (Distance[w] > d) {
                        Distance[w] = d;
                        Path[w] = v;
                        if (!Q.isExist(w)) {
                            Q.enQueue(w);
                        }
                    }
                }
            }
        }

6顿颅、最小生成樹

• 圖的最小生成樹是一個包含所有頂點(diǎn)的子圖并且是一棵樹。一個圖可能有多個生成樹足丢。有以下兩個著名算法用于解決最小生成樹問題：
  1）粱腻、Prim算法
  2）、Kruskal算法

6.1斩跌、Prim算法

• 與Dijkstra算法幾乎相同绍些，Prim算法也利用距離表來保存距離和路徑。唯一的區(qū)別是耀鸦，由于距離的定義不同柬批，所以更新操作略有不同啸澡。
• 代碼實(shí)現(xiàn)：

        public void Prims(Graph G,int s) {
            Heap PQ = new Heap();
            int v;
            PQ.enQueue(s);
            //假設(shè)距離表用 -1 填充
            Distance[s] = 0;
            while (!PQ.isEmpty()) {
                v = PQ.deleteMin();
                //獲取與頂點(diǎn)v相鄰的頂點(diǎn)集合
                var list = GetAdjacentTo(v);
                foreach (int w in list) {
                    int d = Distance[v] + weight[v, w];
                    if (Distance[w] == -1) {
                        //更新頂點(diǎn)w到源點(diǎn)的值
                        Distance[w] = d;
                        //加入優(yōu)先隊(duì)列
                        PQ.enQueue(w);
                        //更新頂點(diǎn)w的最短路徑的上一頂點(diǎn)
                        Path[w] = v;
                    }
                    //判斷當(dāng)前路徑是否最短
                    if (Distance[w] > d) {
                        Distance[w] = weight[v,w];
                        //更新頂點(diǎn)w的最短路徑的上一頂點(diǎn)
                        Path[w] = v;
                    }
                }
            }
        }

6.2、Kruskal算法

• 算法：從 V 個不同的樹開始氮帐，其中 V 為圖中的頂點(diǎn)嗅虏。當(dāng)構(gòu)造最小生成樹時，算法每次選擇一條權(quán)值最小且不會形成回路的邊將其加入到生成樹中上沐。因此皮服，初始化時有 |V| 棵單頂點(diǎn)樹在森林中，當(dāng)加入一條邊時参咙，兩棵樹就合成為一棵樹龄广。當(dāng)算法完成時，就只剩下一棵樹蕴侧，該樹即為最小生成樹择同。
• 舉例：如圖6-1所示，圖中各邊的數(shù)值表示相應(yīng)邊的權(quán)重戈盈。
  
  圖6-1 示例
  
  ①
  
  圖6-2 第一步
  
  ②
  
  圖6-3 第二步
  
  ③
  
  圖6-4 第三步
  
  ④
  
  圖6-5 第四步
  
  ⑤
  
  圖6-6 第五步
  
  ⑥
  
  圖6-7 第六步