C++的無向圖是什么

本篇內(nèi)容介紹了“C++的無向圖是什么”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

無向圖

要是在紙上隨便畫畫，或者只是對圖做點示范性的說明，大多數(shù)人都會選擇無向圖。然而在計算機(jī)中，無向圖卻是按照有向圖的方法來儲存的——存兩條有向邊。實際上，當(dāng)我們說到無向的時候，只是忽略方向——在紙上畫一條線，難不成那線“嗖”的就出現(xiàn)了，不是從一頭到另一頭畫出來的? 無向圖有幾個特有的概念，連通分量、關(guān)節(jié)點、最小生成樹。下面將分別介紹，在此之前，先完成無向圖類的基本操作。

無向圖類

template <class name, class dist, class mem>  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;  }  };

僅僅是添加邊的時候，再添加一條反向邊，很簡單。

連通分量

這是無向圖特有的，有向圖可要復(fù)雜多了(強(qiáng)、單、弱連通)，原因就是無向圖的邊怎么走都行，有向圖的邊好像掉下無底深淵就再也爬不上來了。有了DFS，求連通分量的算法就變得非常簡單了——對每個沒有訪問的頂點調(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]) { cout << '(' << ++j << ')'; DFS(i); cout << endl; }  }  delete []visited;  }

關(guān)節(jié)點

下定義是人們認(rèn)識事物的一個方法，因為概念使得人們能夠區(qū)分事物——關(guān)于這個還有個絕對的運(yùn)動和相對的靜止的哲學(xué)觀點(河水總在流，但是長江還叫長江，記得那個著名的“不可能踏進(jìn)同一條河里”嗎?)因此，能否有個準(zhǔn)確的概念往往是一門學(xué)科發(fā)展程度的標(biāo)志，而能否下一個準(zhǔn)確的定義反映了一個人的思維能力。說這么多廢話，原因只有一個，我沒搞清楚什么叫“關(guān)節(jié)點”——參考書有限，不能仔細(xì)的考究了，如有誤解，還望指正。

嚴(yán)版是這么說的：如果刪除某個頂點，將圖的一個連通分量分割成兩個或兩個以上的連通分量，稱該頂點為關(guān)節(jié)點?！m然沒有提到圖必須是無向的，但是提到了連通分量已經(jīng)默認(rèn)是無向圖了。

殷版是這么說的：在一個無向連通圖中，……(余下同嚴(yán)版)。

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

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

關(guān)于算法不再細(xì)說，書上都有。下面的示例，能輸出每個連通分量的“關(guān)節(jié)點”(是不是可以這樣叫，我也不清楚)。dfn儲存的是每個頂點的訪問序號，low是深度優(yōu)先生成樹上每個非葉子頂點的子女通過回邊所能到達(dá)的頂點最小的訪問序號。把指向雙親的邊也當(dāng)成回邊并不影響判斷，因此不必特意區(qū)分，殷版顯式區(qū)分了，屬于畫蛇添足。這樣一來，if (low[n] >= dfn[i]) cout << getV(i);這個輸出關(guān)節(jié)點的判斷中的>=就顯得很尷尬了，因為只能等于不可能大于。還要注意的是，生成樹的根(DFS的起始點)是單獨判斷的。

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;//訪問樹根  while ((n = nextV(i, n)) != -1)  {  if (dfn[n]) continue;  if (!out) { cout << getV(i); out = true; }//樹根有不只一個子女  articul(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;

“C++的無向圖是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！