數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)C++——圖（1&2&3&4）

2019-11-17 05:47:51

字體：大中小

供稿：網(wǎng)友

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)C++——圖【1】（基本儲(chǔ)存方法）


      首先告訴大家一個(gè)好消息，數(shù)據(jù)結(jié)構(gòu)到這里就要結(jié)束了！然后再來(lái)一個(gè)壞消息，這里是數(shù)據(jù)結(jié)構(gòu)中“最沒(méi)有意義”的部分和最難的部分。圖的應(yīng)用恐怕是所有結(jié)構(gòu)中最寬泛的了，但這也注定了在講“數(shù)據(jù)結(jié)構(gòu)的圖”的時(shí)候沒(méi)什么好講的——關(guān)于圖的最重要的是算法，而且相當(dāng)?shù)囊徊糠侄际呛軐?zhuān)業(yè)的，一般的人幾乎不會(huì)接觸到；相對(duì)而言，結(jié)構(gòu)就顯得分量很輕。你可以看到關(guān)于圖中元素的操作很少，遠(yuǎn)沒(méi)有單鏈表那里列出的一大堆“接口”。——一個(gè)結(jié)構(gòu)假如復(fù)雜，那么能確切定義的操作就很有限。

      不管怎么說(shuō)，還是先得把圖存起來(lái)。不要看書(shū)上列出了好多方法，根本只有一個(gè)——鄰接矩陣。假如矩陣是稀疏的，那就可以用十字鏈表來(lái)儲(chǔ)存矩陣（見(jiàn)前面的《稀疏矩陣（十字鏈表）》）。假如我們只關(guān)系行的關(guān)系，那么就是鄰接表（出邊表）；反之，只關(guān)心列的關(guān)系，就是逆鄰接表（入邊表）。

下面給出兩種儲(chǔ)存方法的實(shí)現(xiàn)。

#ifndef Graphmem_H

#define Graphmem_H

#include

#include

using namespace std;

template  class Network;

const int maxV = 20;//最大節(jié)點(diǎn)數(shù)

template

class AdjMatrix
{
      friend class Network >;
public:
       AdjMatrix() : vNum(0), eNum(0)
       {
              vertex = new name[maxV]; edge = new dist*[maxV];
              for (int i = 0; i < maxV; i++) edge[i] = new dist[maxV];
       }

       ~AdjMatrix()
       {
              for (int i = 0; i < maxV; i++) delete []edge[i];
              delete []edge; delete []vertex;
       }

       bool insertV(name v)
       {
              if (find(v)) return false;
              vertex[vNum] = v;
              for (int i = 0; i < maxV; i++) edge[vNum][i] = NoEdge;
              vNum++; return true;
       }

       bool insertE(name v1, name v2, dist cost)
       {
              int i, j;
              if (v1 == v2  !find(v1, i)  !find(v2, j)) return false;
              if (edge[i][j] != NoEdge) return false;
              edge[i][j] = cost; eNum++; return true;
       }

       name& getV(int n)  //沒(méi)有越界檢查

       int nextV(int m, int n)//返回m號(hào)頂點(diǎn)的第n號(hào)頂點(diǎn)后第一個(gè)鄰接頂點(diǎn)號(hào)，無(wú)返回-1
       {
              for (int i = n + 1; i < vNum; i++) if (edge[m][i] != NoEdge) return i;
              return -1;
       }

PRivate:
       int vNum, eNum;

      dist NoEdge, **edge; name *vertex;

       bool find(const name& v)
       {
              for (int i = 0; i < vNum; i++) if (v == vertex[i]) return true;
              return false;
       }

       bool find(const name& v, int& i)
       {
              for (i = 0; i < vNum; i++) if (v == vertex[i]) return true;
              return false;
       }
};

template

class LinkedList
{
      friend class Network >;

public:

       LinkedList() : vNum(0), eNum(0) {}

       ~LinkedList()
       {
              for (int i = 0; i < vNum; i++) delete vertices[i].e;
       }

       bool insertV(name v)
       {
              if (find(v)) return false;
              vertices.push_back(vertex(v, new list));
              vNum++; return true;
       }

       bool insertE(const name& v1, const name& v2, const dist& cost)
       {
              int i, j;
              if (v1 == v2  !find(v1, i)  !find(v2, j)) return false;
              for (list::iterator iter = vertices[i].e->begin();
              iter != vertices[i].e->end() && iter->vID < j; iter++);
              if (iter == vertices[i].e->end())
              {
                     vertices[i].e->push_back(edge(j, cost)); eNum++; return true;
              }

              if (iter->vID == j) return false;
              vertices[i].e->insert(iter, edge(j, cost)); eNum++; return true;
}

       name& getV(int n)  //沒(méi)有越界檢查
       int nextV(int m, int n)//返回m號(hào)頂點(diǎn)的第n號(hào)頂點(diǎn)后第一個(gè)鄰接頂點(diǎn)號(hào)，無(wú)返回-1
       {
              for (list::iterator iter = vertices[m].e->begin();
              iter != vertices[m].e->end(); iter++) if (iter->vID > n) return iter->vID;
              return -1;
       }

private:

       bool find(const name& v)
       {
              for (int i = 0; i < vNum; i++) if (v == vertices[i].v) return true;
              return false;
       }

       bool find(const name& v, int& i)
       {
              for (i = 0; i < vNum; i++) if (v == vertices[i].v) return true;
              return false;
       }
       strUCt edge
       {
              edge() {}
              edge(int vID, dist cost) : vID(vID), cost(cost) {}
              int vID;
              dist cost;
       };

       struct vertex
       {
             vertex() {}
              vertex(name v, list* e) : v(v), e(e) {}
              name v;
              list* e;
       };
       int vNum, eNum;
       vector vertices;
};

#endif

      這個(gè)實(shí)現(xiàn)是很簡(jiǎn)陋的，但應(yīng)該能滿足后面的講解了。現(xiàn)在這個(gè)還什么都不能做，不要急，在下篇將講述圖的DFS和BFS。

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）——圖【2】（DFS和BFS）    happycock（原作）

要害字     DFS BFS

      對(duì)于非線性的結(jié)構(gòu)，遍歷都會(huì)首先成為一個(gè)問(wèn)題。和二叉樹(shù)的遍歷一樣，圖也有深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）兩種。不同的是，圖中每個(gè)頂點(diǎn)沒(méi)有了祖先和子孫的關(guān)系，因此，前序、中序、后序不再有意義了。仿照二叉樹(shù)的遍歷，很輕易就能完成DFS和BFS，只是要注重圖中可能有回路，因此，必須對(duì)訪問(wèn)過(guò)的頂點(diǎn)做標(biāo)記。

最基本的有向帶權(quán)網(wǎng)
#ifndef Graph_H

#define Graph_H

#include

#include

using namespace std;

#include "Graphmem.h"

template

class Network
{
public:

       Network() {}

       Network(dist maxdist)

       ~Network() {}

       bool insertV(name v)

       bool insertE(name v1, name v2, dist cost)

       name& getV(int n)

       int nextV(int m, int n = -1)

       int vNum()

       int eNum()

protected:

       bool* visited;

       static void print(name v)

private:

       mem data;
};

#endif

      你可以看到，這是在以mem方式儲(chǔ)存的data上面加了一層外殼。在圖這里，邏輯上分有向、無(wú)向，帶權(quán)、不帶權(quán)；儲(chǔ)存結(jié)構(gòu)上有鄰接矩陣和鄰接表。也就是說(shuō)分開(kāi)來(lái)有8個(gè)類(lèi)。為了最大限度的復(fù)用代碼，繼續(xù)關(guān)系就非常復(fù)雜了。但是，多重繼續(xù)是件很討厭的事，什么覆蓋啊，還有什么虛擬繼續(xù)，我可不想花大量篇幅講語(yǔ)言特性。于是，我將儲(chǔ)存方式作為第三個(gè)模板參數(shù)，這樣一來(lái)就省得涉及虛擬繼續(xù)了，只是這樣一來(lái)這個(gè)Network的實(shí)例化就很麻煩了，不過(guò)這可以通過(guò)typedef或者外殼類(lèi)來(lái)解決，我就不寫(xiě)了。反正只是為了讓大家明白，真正要用的時(shí)候，最好是寫(xiě)專(zhuān)門(mén)的類(lèi)，比如無(wú)向無(wú)權(quán)鄰接矩陣圖，不要搞的繼續(xù)關(guān)系亂七八糟。

DFS和BFS的實(shí)現(xiàn)
public:

       void DFS(void(*visit)(name v) = print)
       {
              visited = new bool[vNum()];

              for (int i = 0; i < vNum(); i++) visited[i] = false;

              DFS(0, visit);

              delete []visited;
       }

protected:

       void DFS(int i, void(*visit)(name v) = print)
       {
              visit(getV(i)); visited[i] = true;

              for (int n = nextV(i); n != -1; n = nextV(i, n))

                     if (!visited[n]) DFS(n, visit);
       }

public:

       void BFS(int i = 0, void(*visit)(name v) = print)//n沒(méi)有越界檢查
       {
              visited = new bool[vNum()]; queue a; int n;

              for (n = 0; n < vNum(); n++) visited[n] = false;

              visited[i] = true;

              while (i != -1)//這個(gè)判定可能是無(wú)用的
              {

                     visit(getV(i));

                     for (n = nextV(i); n != -1; n = nextV(i, n))

                            if (!visited[n])

                     if (a.empty()) break;

                     i = a.front(); a.pop();
              }
              delete []visited;
       }

      DFS和BFS函數(shù)很難寫(xiě)得像樹(shù)的遍歷方法那么通用，這在后面就會(huì)看到，雖然我們使用了DFS和BFS的思想，但是上面的函數(shù)卻不能直接使用。因?yàn)闃?shù)的信息主要在節(jié)點(diǎn)上，而圖的邊上還有信息。

測(cè)試程序
#include

using namespace std;

#include "Graph.h"

int main()
{
       Network > a;
       a.insertV('A'); a.insertV('B');

       a.insertV('C');       a.insertV('D');

       a.insertE('A', 'B', 1); a.insertE('A', 'C', 2);

      a.insertE('B', 'D', 3);

       cout << "DFS: "; a.DFS(); cout << endl;

       cout << "BFS: "; a.BFS(); cout << endl;

       return 0;
}

老實(shí)說(shuō)，這個(gè)類(lèi)用起來(lái)真的不是很方便。不過(guò)能說(shuō)明問(wèn)題就好。

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）——圖【3】（無(wú)向圖上）    happycock（原作）

要害字     數(shù)據(jù)結(jié)構(gòu) C++ 連通分量關(guān)節(jié)點(diǎn)

要是在紙上隨便畫(huà)畫(huà)，或者只是對(duì)圖做點(diǎn)示范性的說(shuō)明，大多數(shù)人都會(huì)選擇無(wú)向圖。然而在計(jì)算機(jī)中，無(wú)向圖卻是按照有向圖的方法來(lái)儲(chǔ)存的——存兩條有向邊。實(shí)際上，當(dāng)我們說(shuō)到無(wú)向的時(shí)候，只是忽略方向——在紙上畫(huà)一條線，難不成那線“嗖”的就出現(xiàn)了，不是從一頭到另一頭畫(huà)出來(lái)的？

無(wú)向圖有幾個(gè)特有的概念，連通分量、關(guān)節(jié)點(diǎn)、最小生成樹(shù)。下面將分別介紹，在此之前，先完成無(wú)向圖類(lèi)的基本操作。

無(wú)向圖類(lèi)
template
class Graph : public Network
{
public:
       Graph() {}

       Graph(dist maxdist) : Network (maxdist) {}

bool insertE(name v1, name v2, dist cost)
       {
              if (Network::insertE(v1, v2, cost))
                     return Network::insertE(v2, v1, cost);
              return false;
       }
};

僅僅是添加邊的時(shí)候，再添加一條反向邊，很簡(jiǎn)單。

連通分量

這是無(wú)向圖特有的，有向圖可要復(fù)雜多了（強(qiáng)、單、弱連通），原因就是無(wú)向圖的邊怎么走都行，有向圖的邊似乎掉下無(wú)底深淵就再也爬不上來(lái)了。有了DFS，求連通分量的算法就變得非常簡(jiǎn)單了——對(duì)每個(gè)沒(méi)有訪問(wèn)的頂點(diǎn)調(diào)用DFS就可以了。

       void components()

       {

              visited = new bool[vNum()]; int i, j = 0;

              for (i = 0; i < vNum(); i++) visited[i] = false;

              cout << "Components:" << endl;

              for (i = 0; i < vNum(); i++)

              {

                     if (!visited[i])

              }

              delete []visited;

       }

黑體的部分就是核心。

關(guān)節(jié)點(diǎn)
下定義是人們熟悉事物的一個(gè)方法，因?yàn)楦拍钍沟萌藗兡軌騾^(qū)分事物——關(guān)于這個(gè)還有個(gè)絕對(duì)的運(yùn)動(dòng)和相對(duì)的靜止的哲學(xué)觀點(diǎn)（河水總在流，但是長(zhǎng)江還叫長(zhǎng)江，記得那個(gè)聞名的“不可能踏進(jìn)同一條河里”嗎？）因此，能否有個(gè)準(zhǔn)確的概念往往是一門(mén)學(xué)科發(fā)展程度的標(biāo)志，而能否下一個(gè)準(zhǔn)確的定義反映了一個(gè)人的思維能力。說(shuō)這么多廢話，原因只有一個(gè)，我沒(méi)搞清楚什么叫“關(guān)節(jié)點(diǎn)”——參考書(shū)有限，不能仔細(xì)的考究了，如有誤解，還望指正。

嚴(yán)版是這么說(shuō)的：假如刪除某個(gè)頂點(diǎn)，將圖的一個(gè)連通分量分割成兩個(gè)或兩個(gè)以上的連通分量，稱(chēng)該頂點(diǎn)為關(guān)節(jié)點(diǎn)。——雖然沒(méi)有提到圖必須是無(wú)向的，但是提到了連通分量已經(jīng)默認(rèn)是無(wú)向圖了。

殷版是這么說(shuō)的：在一個(gè)無(wú)向連通圖中，……（余下同嚴(yán)版）。

問(wèn)題出來(lái)了，非連通圖是否可以討論含有關(guān)節(jié)點(diǎn)？我們是否可以說(shuō)某個(gè)連通分量中含有關(guān)節(jié)點(diǎn)？遺憾的是，嚴(yán)版留下這個(gè)問(wèn)題之后，在后面給出的算法是按照連通圖給的，這樣當(dāng)圖非連通時(shí)結(jié)果就是錯(cuò)的。殷版更是滑頭，只輸出重連通分量，不輸出關(guān)節(jié)點(diǎn)，自己雖然假定圖是連通的，同樣沒(méi)有連通判定。

翻翻離散數(shù)學(xué)吧，結(jié)果沒(méi)找到什么“關(guān)節(jié)點(diǎn)”，只有“割點(diǎn)”，是這樣的：一個(gè)無(wú)向連通圖，假如刪除某個(gè)頂點(diǎn)后，變?yōu)榉沁B通圖，該頂點(diǎn)稱(chēng)為割點(diǎn)。權(quán)當(dāng)“割點(diǎn)”就是“關(guān)節(jié)點(diǎn)”，那么算法至少也要先判定是否連通吧？可是書(shū)上都直接當(dāng)連通的了……

關(guān)于算法不再細(xì)說(shuō)，書(shū)上都有。下面的示例，能輸出每個(gè)連通分量的“關(guān)節(jié)點(diǎn)”（是不是可以這樣叫，我也不清楚）。dfn儲(chǔ)存的是每個(gè)頂點(diǎn)的訪問(wèn)序號(hào)，low是深度優(yōu)先生成樹(shù)上每個(gè)非葉子頂點(diǎn)的子女通過(guò)回邊所能到達(dá)的頂點(diǎn)最小的訪問(wèn)序號(hào)。把指向雙親的邊也當(dāng)成回邊并不影響判定，因此不必特意區(qū)分，殷版顯式區(qū)分了，屬于畫(huà)蛇添足。這樣一來(lái)，if (low[n] >= dfn[i]) cout << getV(i);這個(gè)輸出關(guān)節(jié)點(diǎn)的判定中的>=就顯得很尷尬了，因?yàn)橹荒艿扔诓豢赡艽笥凇＿€要注重的是，生成樹(shù)的根（DFS的起始點(diǎn)）是單獨(dú)判定的。

       void articul()

       {

              dfn = new int[vNum()]; low = new int[vNum()]; int i, j = 0, n;

              for(i = 0; i < vNum(); i++) dfn[i] = low[i] = 0;//初始化

              for (i = 0; i < vNum(); i++)

              {

                     if (!dfn[i])

                     {

                            cout << '(' << ++j << ')'; dfn[i] = low[i] = count = 1;

                            if ((n = nextV(i)) != -1) articul(n); bool out = false;//訪問(wèn)樹(shù)根

                            while ((n = nextV(i, n)) != -1)

                            {

                                   if (dfn[n]) continue;

                                  if (!out) //樹(shù)根有不只一個(gè)子女

                                   articul(n);//訪問(wèn)其他子女

                            }

                            cout << endl;

                     }

              }

              delete []dfn; delete []low;

       }

private:

       void articul(int i)

       {

              dfn[i] = low[i] = ++count;

              for (int n = nextV(i); n != -1; n = nextV(i, n))

              {

                     if (!dfn[n])

                     {

                            articul(n);

                            if (low[n] < low[i]) low[i] = low[n];

                            if (low[n] >= dfn[i]) cout << getV(i);//這里只可能＝

                     }

                     else if (dfn[n] < low[i]) low[i] = dfn[n];//回邊判定

              }

       }

       int *dfn, *low, count;

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)（C++）——圖【4】（無(wú)向圖下）    happycock（原作）
要害字     數(shù)據(jù)結(jié)構(gòu) 最小生成樹(shù)

最小生成樹(shù)
說(shuō)人是最難伺候的，真是一點(diǎn)不假。上面剛剛為了“提高可靠性”添加了幾條多余的邊，這會(huì)兒又來(lái)想辦法怎么能以最小的代價(jià)把所有的頂點(diǎn)都連起來(lái)。可能正是人的這種精神才使得人類(lèi)能夠進(jìn)步吧——看著現(xiàn)在3GHz的CPU真是眼紅啊，我還在受500MHz的煎熬，然后再想想8086……

正如圖的基本元素是頂點(diǎn)和邊，從這兩個(gè)方向出發(fā)，就能得到兩個(gè)算法——Kruskal算法（從邊出發(fā)）、Prim算法（從頂點(diǎn)出發(fā)）。據(jù)說(shuō)還有別的方法，恕我參考資料有限，不能詳查。

最小生成樹(shù)的儲(chǔ)存
顯然用常用的樹(shù)的儲(chǔ)存方法來(lái)儲(chǔ)存沒(méi)有必要，雖然名曰“樹(shù)”，實(shí)際上，這里誰(shuí)是誰(shuí)的“祖先”、“子孫”并不重要。因此，用如下的MSTedge結(jié)構(gòu)數(shù)組來(lái)儲(chǔ)存就可以了。

template

class MSTedge

{

public:

       MSTedge() {}

       MSTedge(int v1, int v2, dist cost) : v1(v1), v2(v2), cost(cost) {}

       int v1, v2;

       dist cost;

       bool operator > (const MSTedge& v2)

       bool Operator < (const MSTedge& v2)

       bool operator == (const MSTedge& v2)

};

Kruskal算法
最小生成樹(shù)直白的講就是，挑選N－1條不產(chǎn)生回路最短的邊。Kruskal算法算是最直接的表達(dá)了這個(gè)思想——在剩余邊中挑選一條最短的邊，看是否產(chǎn)生回路，是放棄，不是選定然后重復(fù)這個(gè)步驟。說(shuō)起來(lái)倒是很簡(jiǎn)單，做起來(lái)就不那么輕易了——判定是否產(chǎn)生回路需要并查集，在剩余邊中找一條最短的邊需要最小堆（并不需要對(duì)所有邊排序，所以堆是最佳選擇）。

Kruskal算法的復(fù)雜度是O(eloge)，當(dāng)e接近N^2時(shí)，可以看到這個(gè)算法不如O(N^2)的Prim算法，因此，他適合于稀疏圖。而作為稀疏圖，通常用鄰接表來(lái)儲(chǔ)存比較好。另外，對(duì)于鄰接矩陣儲(chǔ)存的圖，Kruskal算法比Prim算法占不到什么便宜（初始還要掃描N^2條“邊”）。因此，最好把Kruskal算法放在Link類(lèi)里面。

template  int Link::MinSpanTree(MSTedge* a)

{

       MinHeap > E; int i, j, k, l = 0;

       MFSets V(vNum); list::iterator iter;

       for (i = 0; i < vNum; i++)

              for (iter = vertices[i].e->begin(); iter != vertices[i].e->end(); iter++)

                     E.insert(MSTedge(i, iter->vID, iter->cost));//建立邊的堆

       for (i = 0; i < eNum && l < vNum; i++)//Kruskal Start

       {

              j = V.find(E.top().v1); k = V.find(E.top().v2);

              if (j != k)

              E.pop();

       }

       return l;

}

下面是堆和并查集的實(shí)現(xiàn)

#ifndef Heap_H

#define Heap_H

#include

using namespace std;

#define minchild(i) (heap[i*2+1]
template

class MinHeap

{

public:

       void insert(const T& x)

       const T& top()

       void pop()

private:

       void FilterUp(int i)

       {

              for (int j = (i - 1) / 2; j >= 0 && heap[j] > heap[i]; i = j, j = (i - 1) / 2)

                     swap(heap[i], heap[j]);

       }

       void FilterDown(int i)

       {

              for (int j = minchild(i); j < heap.size() && heap[j] < heap[i]; i = j, j = minchild(i))

                     swap(heap[i], heap[j]);

       }

       vector heap;

};

#endif

#ifndef MFSets_H

#define MFSets_H

class MFSets

{

public:

       MFSets(int maxsize) : size(maxsize)

       {

              parent = new int[size + 1];

              for (int i = 0; i <= size; i++) parent[i] = -1;

       }

       ~MFSets()

       void merge(int root1, int root2)//root1!=root2

       {

              parent[root2] = root1;

       }

       int find(int n)

       {

              if (parent[n] < 0) return n;

              return find(parent[n]);

       }

private:

       int size;

       int* parent;

};

#endif

Prim算法
假如從頂點(diǎn)入手，就能得到另一種方法。從只含有一個(gè)頂點(diǎn)的集合開(kāi)始，尋找集合外面的頂點(diǎn)到這個(gè)集合里的頂點(diǎn)最近的一條邊，然后將這個(gè)頂點(diǎn)加入集合，修改因?yàn)檫@個(gè)頂點(diǎn)的加入而使得集合外面的頂點(diǎn)到集合里的頂點(diǎn)的最短距離產(chǎn)生變化的分量。因?yàn)樾枰獙?duì)每個(gè)頂點(diǎn)掃描，鄰接矩陣儲(chǔ)存的圖是最合適Prim算法的。

template  int AdjMatrix::MinSpanTree(MSTedge* a)

{

       dist* lowC = new dist[vNum]; int* nearV = new int[vNum];

       int i, j, k;

       for (i = 0; i < vNum; i++)  nearV[0] = -1;

       for (k = 0; k < vNum-1; k++)//Prim Start

       {

              for (i = 1, j = 0; i < vNum; i++)

                     if (nearV[i] != -1 && lowC[i] < lowC[j]) j = i;//find low cost

              a[k] = MSTedge(nearV[j], j, lowC[j]); nearV[j] = -1; //insert MST

              if (a[k].cost == NoEdge) return k - 1;//no edge then return

              for (i = 1; i < vNum; i++)//modify low cost

                     if (nearV[i] != -1 && edge[i][j] < lowC[i])

       }

       return k;

}

【附注】這里需要說(shuō)明一下，對(duì)于edge[I][I]這樣的是應(yīng)該是0呢還是NoEdge呢？顯然0合理，但是不好用。并且，從有權(quán)圖無(wú)權(quán)圖統(tǒng)一的角度來(lái)說(shuō)，是NoEdge更好。因此，在我的有權(quán)圖的鄰接矩陣中，主對(duì)角線上的元素是NoEdge，而不是書(shū)上的0。

測(cè)試程序
儲(chǔ)存和操作分離，沒(méi)想到得到了一個(gè)有趣的結(jié)果——對(duì)于最后的無(wú)向圖而言，最小生成樹(shù)的算法對(duì)外表現(xiàn)不知道是采用了那個(gè)算法。

template

bool Graph::MinSpanTree()

{

       MSTedge* a = new MSTedge[vNum() - 1];

       int n = data.MinSpanTree(a); dist sum = dist();

       if (n < vNum() - 1) return false;//不夠N－1條邊，不是生成樹(shù)

      for (int i = 0; i < n; i++)

       {

              cout << '(' << getV(a[i].v1) << ',' << getV(a[i].v2) << ')' << a[i].cost << ' ';

              sum += a[i].cost;

       }

       cout << endl << "MinCost: " << sum << endl;

       delete []a;

       return true;

}

最后的測(cè)試圖的數(shù)據(jù)取自殷版（C++）——不知是這組數(shù)據(jù)好是怎么的，殷版居然原封不動(dòng)的照抄了《數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用-C++語(yǔ)言描述》（中文譯名）

#include

using namespace std;

#include "Graph.h"

int main()

{

      Graph > a(100);//改為L(zhǎng)ink儲(chǔ)存為Kruskal算法

       a.insertV('A'); a.insertV('B');

       a.insertV('C');       a.insertV('D');

       a.insertV('E'); a.insertV('F');

       a.insertV('G');

       a.insertE('A', 'B', 28); a.insertE('A', 'F', 10);

      a.insertE('B', 'C', 16); a.insertE('C', 'D', 12);

       a.insertE('D', 'E', 22); a.insertE('B', 'G', 14);

      a.insertE('E', 'F', 25); a.insertE('D', 'G', 18);

      a.insertE('E', 'G', 24);

       a.MinSpanTree();

       return 0;

}

上一篇：雙向鏈表的排序

下一篇：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)C++——圖(4&5&總結(jié)&后記)