c++鄰接表是什么

今天小編給大家分享一下c++鄰接表是什么的相關知識點，內(nèi)容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

 圖

圖狀結(jié)構是一種比樹形結(jié)構更復雜的非線性結(jié)構。在樹形結(jié)構中，結(jié)點間具有分支層次關系，每一層上的結(jié)點只能和上一層的至多一個結(jié)點相關，但可能和下一層的多個結(jié)點相關。而在圖狀結(jié)構中，任意兩個結(jié)點之間都可能相關，即結(jié)點之間的鄰接關系可以是任意的。因此，圖是比樹更一般、更復雜的非線性結(jié)構，常被用于描述各種復雜的數(shù)據(jù)對象，在自然科學、社會科學和人文科學等許多領域有著非常廣泛的應用。

第一節(jié) 基本概念

1.1 定義和術語

（1）定語：

圖（Graph）是由非空的頂點集合和一個描述頂點之間的關系——邊（或者?。┑募辖M成的，其形式化定義為：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合，集合E中P(vi,vj)表示頂點vi和頂點vj之間有一條直接連線，即偶對(v1,vj）表示一條邊。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。

（2）術語:

1、無向圖：在一個圖中，如果任意兩個頂點構成的偶對(vi,vj）包含E是無序的，即頂點之間的連線是沒有方向的，則稱該圖為無向圖。

2、有向圖：在一個圖中，如果任意兩個頂點構成的偶對<vj,vj>包含E是有序的（有序?qū)Τ３Ｓ眉饫ㄌ枴?lt;>”表示），即頂點之間的連線是有方向的，則稱該圖為有向圖。

3、頂點、邊、弧、弧頭、弧尾：在圖中，數(shù)據(jù)元素vi稱為頂點（Vertex）；（vj，vj）表示在頂點vi和頂點vj之間有一條直接連線。如果是在無向圖中，則稱這條連線為邊；如果是在有向圖中，一般稱這條連線為弧。邊用頂點的無序偶對（vi，vj）來表示，稱頂點vi和vj互為鄰接點，邊<vi,vj>依附于頂點vi與頂點vj；弧用頂點的有序偶對<vi,vj>來表示，有序偶對的第一個節(jié)點vi被稱為始點(或弧尾），在圖中就是不帶箭頭的一端；有序偶對的第二個節(jié)點vj被稱為終點(或弧頭），在圖中就是帶箭頭的一端。

4、無向完全圖：在一個無向圖中，如果任意兩頂點都有一條直接邊相連接，則稱該圖為無向完全圖?？梢宰C明，在一個含有n個頂點的無向完全圖中，有n（n-1）/2條邊。

5、有向完全圖：在有一個有向圖中，如果任意兩頂點之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個含有n個頂點的有向完全圖中，有n(n-1)條邊。

6、頂點的度、入度、出度：頂點的度（Degree）是指依附于某頂點v的邊數(shù)，通常記為TD(v)。頂點v的入度是指以頂點v為終點的弧的數(shù)目，記為ID(V)；出度是指以頂點v為始點的弧的數(shù)目，記為OD(V)。有TD(V)=ID(v)+OD(v)。

7、邊的權、網(wǎng)：與邊有關的數(shù)據(jù)信息稱為權(Weight)。在實際應用中，權值可以有某種含義。例如，在一個反映城市交通線路的圖中，邊上的權值可以表示該條線路的長度或等級；對于一個電子線路圖，邊上的權值可以表示兩個端點之間的電阻、電流或電壓值；對于反映工程進度的圖而言，邊上的權值可以表示從前一個工程到后一個工程所需要的時間或其他代價等。邊上帶權的圖稱為網(wǎng)或網(wǎng)絡（network）。

8、路徑、路徑長度：頂點vp到頂點vq之間的路徑（path）是指頂點序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長度。

9、簡單路徑、回路、簡單回路：序列中頂點不重復出現(xiàn)的路徑稱為簡單路徑。路徑中第一個頂點與最后一個頂點相同的 路徑稱為回路或環(huán)（Cycle）。除第一個頂點與最后一個頂點之外，其他頂點不重復出現(xiàn)的回路稱為簡單回路，或者簡單環(huán)。

10、子圖：對于圖G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，則稱圖 G'是G的的一個子圖。

11、連通、連通圖、連通分量：在無向圖中，如果從一個頂點vi到另一個頂點vj(i=!j)存在路徑，則稱頂點vi和vj是連通的。如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖。無向圖的極大連通子圖稱為連通分量，極大連通子圖是指在保證連通與子圖的條件下，包含原圖中所有的頂點與邊。 如下圖：

12、強連通圖、強連通分量：對于有向圖來說，若圖中任意一對頂點vi和vj（i=!j）均存在從一個頂點vi到另一個頂點vj和從vj到vi的路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量，極大強連通子圖的含義同上。

13、生成樹：所謂連通圖G的生成樹，是G的包含其全部n個頂點的一個極小連通子圖，所謂極小連通子圖是指在包含所有頂點且保證連通的前提下盡可能少地包含原圖中的邊。生成樹必定包含且僅包含連通圖G的n-1條邊。在生成樹中添加任意一條屬于原圖中的邊必定會產(chǎn)生回路，因為新添加的邊使其所依附的兩個頂點之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。

14、生成森林：在非連通圖中，由每個連通分量都可得到一個極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個非連通圖的生成森林。

1.2 基本操作

1、GreatGraph(G) ： 輸入圖G的頂點和邊，建立圖G的存儲。
2、DestroyGraph(G) ：釋放圖G占用的存儲空間。
3、GetVex(G，v)：在圖G中找到頂點v，并返回頂點v的相關信息。
4、PutVex(G,V,value)：在圖G中找到頂點v，并將value值賦予給頂點v。
5、InsertVex(G,v）：在圖G中增添新頂點v。
6、DeleteVex(G,v)：在圖G中，刪除頂點v及所有和頂點v相關的邊或弧。
7、InsertArc(G,v,w)：在圖G中增添一條從頂點v到頂點w的邊或弧。
8、DeleteArc(G,v,w)：在圖G中刪除一條從頂點v到頂點w的邊或弧。
9、DFSTraverse(G,v)：在圖G中，從頂點v出發(fā)深度優(yōu)化遍歷圖G。
10、BFSTtaverse(G,v)：在圖G中，從頂點v出發(fā)廣度優(yōu)先遍歷圖G。

在一個圖中，頂點是沒有先后次序的，但當采用某一種確定的存儲方式存儲后，存儲結(jié)構中頂點的存儲次序成了頂點之間的相對次序，這里用頂點在圖中的位置表示該頂點的存儲順序；同樣的道理，對一個頂點的所有鄰接點，采用該頂點的第i個鄰接點表示與該頂點相鄰接的某個頂點的存儲順序，在這種意義下，圖還有以下的基本操作。

11、LocateVex（G，u）：在圖G中找到頂點u，返回該頂點在圖中位置。
12、FirstAdjVex（G，v）：在圖G中，返回v的第一個鄰接點。若頂點在G中沒有鄰接頂點，則返回“空”。
13、NextAdjVex(G，v，w)：在圖G中， 返回v的（相對于w的）下一個鄰接頂點。若w是v的最后一個鄰接點，則返回"空”。

第二節(jié) 存儲結(jié)構

圖是一種結(jié)構復雜的數(shù)據(jù)結(jié)構，表現(xiàn)在不僅各個頂點的度可以千差萬別，而且頂點之間的邏輯關系也錯綜復雜。從圖的定義可知，一個圖的信息包括兩部分，即圖中頂點的信息及描述頂點之間的關系——邊或弧的信息。因此，無論采用什么方法建立圖的存儲結(jié)構，都要完整、準確地反映這兩方面的信息。

2.1 鄰接矩陣

所謂鄰接矩陣（Adjacency Matrix）的存儲結(jié)構，就是用一維數(shù)組存儲圖中的頂點信息，用矩陣表示圖中各頂點之間的鄰接關系。假設圖G=(V,E)有n個確定的頂點，即V ={v0,v1，···，vn-1}，則表示G中各頂點相鄰關系的矩陣為一個n×n的矩陣，矩陣的元素為：

A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的邊 ；2，若(vi,vj）或<vi,vj>不是E(G)中的邊。

若G是網(wǎng)，則鄰接矩陣可定義為：

A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的邊 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的邊。
其中，wij表示邊(Vi,vj)或<vi,vj>上的權值；表示一個計算機允許的、大于所有邊上權值的數(shù)。

（1）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上或下三角矩陣的元素即可。

（2）對于無向圖，鄰接矩陣的第i行或第i列非零元素或非&元素的個數(shù)正好是第i個頂點的度TD(vi)。

（3）對于有向圖，鄰接矩陣的第i行和第i列非零元素或非&元素的個數(shù)正好是第i個頂點的出度OD(vi)或入度ID(vi)。

（4）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。

在實際應用鄰接矩陣存儲圖時，除了用一個二維數(shù)組存儲用于表示頂點間相鄰關系的鄰接矩陣外，還需用一個一維數(shù)組來存儲頂點信息，另外，還有圖的頂點數(shù)和邊數(shù)。故可將其形式描述如下：

#define MaxVertexNum 100 
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType vexs[MaxVertexNum];//頂點表
    EdgeType edges[MaxVertexNum] [MaxVertexNum];//相鄰矩陣，即邊表
    int n,e;//頂點數(shù)和邊數(shù)
 }MGraph;

2.2 鄰接表

鄰接表（Adjacency List）是圖的一種順序存儲與鏈式存儲結(jié)合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖G中的每個頂點vi，將所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表，再將所有頂點的鄰接表表頭放到數(shù)組中，就構成了圖鄰接表。

在鄰接表表示中有兩種結(jié)點結(jié)構：一種是頂點表的結(jié)點結(jié)構，它由頂點域（vertex）和指向第一條鄰接邊的指針域（firstedge）構成。另一種是邊表即鄰接表結(jié)點，它由鄰接點域（adjvex）和指向下一條鄰接邊的指針域（next）構成。對于圖的邊表需再增設一個存儲邊上的信息（如權值等）的域（info）。形式如下：

#define MaxVerNu
typedef struct node{
    int adjvex;
    struct node*next;
}EdgeNode;
 
typedef struct vnode{
    VertexType vertex;
    EdgeNode *firstedge;
}VertexNode;
 
typedef VertexNode AdjList[MaxVertexNum];
 
typedef struct{
    AdjList adjlist;
    int n ,e;
}ALGraph;

若無向圖中有n個頂點、e條邊，則它的鄰接表需n個頭結(jié)點和2e個表結(jié)點。顯然，在邊稀疏（e<<n(n-1)/2）的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間，當和邊相關的信息較多時更是如此。在無向圖的鄰接表中，頂點vi的度恰為第i個鏈表中的結(jié)點數(shù)；而在有向圖中，第i個鏈表中的結(jié)點個數(shù)只是頂點v1的出度，求入度，必須遍歷整個整個鄰接表。在所有鏈表中其鄰接點域的值為i的結(jié)點的個數(shù)是頂點vi的入度。有時，為了便于確定頂點的入度或以頂點vi為頭的弧，可以建立一個有向的逆鄰接表，即對每個頂點vi建立一個鏈接以vi為頭的弧的鏈表。

在建立鄰接表或逆鄰表時，若輸入的頂點信息即為頂點的編號，則建立鄰接表的復雜度為O(n+e)，否則，需要通過查找才能得到頂點在圖中位置，則時間復雜度為O(ne)。

在鄰接表上容易找到任意頂點的第一個鄰接點和下一個鄰結(jié)點，但要判定任意兩個頂點(vi和vj)之間是否有邊或弧相連，則需查找第i個或第j個鏈表，因此，不如鄰接矩陣方便。

第3節(jié) 圖的遍歷

圖的遍歷是指從圖中的任意頂點出發(fā)，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其他操作都是建立在遍歷操作的基礎之上的。

3.1 深度優(yōu)先搜索（Depth First Search，DFS）

類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設初始化狀態(tài)是圖中所有頂點未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點v出發(fā)，訪問此頂點，然后依然從v的未被訪問的鄰接點出發(fā)深度優(yōu)化遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。如下圖：

a所示的無向圖G4，進行圖的深度優(yōu)先搜索。假設從頂點v1出發(fā)進行搜索，在訪問了頂點v1之后，選擇鄰接點v2。因為v2未曾訪問，則從v2出發(fā)進行搜索，以此類推，接著從v4,v8,v5出發(fā)進行搜索。在訪問了v5之后，由于其鄰接點都已經(jīng)被訪問了，則搜索回到v8，同理，搜索繼續(xù)回到到v4,v2,v1。此時，由于v1的另一個鄰接點未被訪問，則查找又從v1到v3，v6，v7。顯然，這是一個遞歸的過程。為了遍歷過程中便于區(qū)分頂點是否已被訪問，需要附設訪問標志數(shù)組visited[0:n-1]，其初值為FALSE,一旦某個頂點被訪問，則其相應的分量置為TRUE。

void DFS(Graph G,int v){
    //從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G
    visited[v] =TRUE;
    //訪問第v個點
    VisitFunc(v);
    for(w=FirstAdjVex(G,V) ;w ;w =NextAdjVex(G,v,w))
    //對v的尚未訪問鄰接頂點w遞歸調(diào)用DFS
    if(!visited[w]) 
        DFS(G,W);
}

深度優(yōu)化搜索算法實現(xiàn)：

void DFSTraverseAL(ALGraph *G){
        /*深度優(yōu)先遍歷以鄰接表存儲的圖G*/
        int i;
        for (i=0; i<G ->n; i++)
             visited[i]=FALSE;              /*標志向量初始化*/
        for (i=0; i<G ->n; i++)
             if (!visited[i]) DFSAL(G, i);  /*vi 未訪問過，從vi開始DFS搜索*/
}                                    
 
   /*DFSTraveseAL*/
void DFSAL(ALGraph *G , int i) {
     /*以Vi為出發(fā)點對鄰接表存儲的圖G進行DFS搜索*/
      EdgeNode *p;
      printf ("visit vertex:V%c\n", G ->adjlist[i].vertex); /*訪問頂點vi*/
      visited[i]=TRUE;                      /*標記vi已訪問*/
      p=G ->adjlist[i].firstedge;
      //取vi邊表的頭指針    
      while(p){
        if(!visited[p->adjvex])
            DFSAL(G,p->adjvex);
        p = p->next;
      }
}

3.2 廣度優(yōu)先搜索（Breadth First Search，BFS）

類似于樹的按層次遍歷的過程。假設從圖中某頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述過程，直至所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起始點，由近至遠，依次訪問和v有路徑相通且路徑長度為1，2，···的頂點。

如上圖中的c，首先訪問v1和v1的鄰接點v2和v3，然后依次訪問v2的鄰接點v4和v5及v3的鄰接點v6和v7，最后訪問v4的鄰接點v8。得到訪問序列為：v1 →v2→v3→v4→v5→v6→v7→v8。和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個訪問標志數(shù)組。并且為了順次訪問路徑長度為1，2，3···的頂點，需要附設隊列以存儲已被訪問的路徑長度為1，2，···的頂點。從圖的某一點v出發(fā)，非遞歸地進行廣度優(yōu)先遍歷的過程算法如下所示：

voidBFSTraverse(Grapg G,Status （*Visit）（int v)){
    //按廣度優(yōu)先非遞歸遍歷圖G，使用輔助隊列Q和訪問標志數(shù)組visied
    for(v =0 ;v =G.vexnum ;++v)
        visited[v] =FALSE;
 
  //置空隊列Q
    Init_Queue(Q);
  
//v尚未被訪問
    if(!visited[v]){
        In_Queue(Q,v);//v入隊列
        while(!QueueEmpty(Q)){
            Out_Queue(Q,u);
            visited[u] =TURE;
            visit(u);
            for(w =FirstAdjVex(G,u) ; w ;w =NextAdjVex(G,u,w))
            if(!visited[w] 
                In_Queue(Q,W);
        }
    }
}

下面算法給出了對以鄰接矩陣為存儲結(jié)構的圖G進行廣度優(yōu)先搜索實現(xiàn)的C語言描述。廣度優(yōu)先搜索算法：

 /*廣度優(yōu)先遍歷以鄰接矩陣存儲的圖G*/
void BFSTraverseAL(MGraph *G)              
{   int i;
    for (i=0; i<G ->n; i++)
          visited[i]=FALSE;                 /*標志向量初始化*/
          for (i=0; i<G ->n; i++)
            if (!visited[i]) BFSM(G, i);    /* vi 未訪問過，從vi開始BFS查找*/
}    
 
/*BFSTraverseAL*/
void BFSM(Mgraph *G , int k)                /*以vk為出發(fā)點，對圖G進行BFS查找*/
    { int i, j;
        C_Queue Q;
        Init_Queue(&Q);
        printf("visit vertex:V%c\n",G ->vexs[k]); /*訪問原點vk*/
        visited[k]=TRUE;
    In_Queue(&Q, k);                        /*原點vk入隊列*/
    while (!QueueEmpty(&Q))
        { i=Out_Queue(&Q);                  /*vi 出隊列*/
          for (j=0; j<G ->n; j++)           /*依次查找vi的鄰接點vj*/
            if (G ->edges[i][j]= =1 && !visited[j]) /*若vj未訪問*/
              { printf("visit vertex:V%c\n", G ->vexs[j]); /*訪問vj */
                visited[j]=TRUE;
                In_Queue(&Q, j);            /*訪問過的vj入隊列*/
               }
        }
  } /*BFSM*/

分析上述算法，每個頂點最多進一次隊列。遍歷圖的過程實質(zhì)是通過邊或弧找鄰接點的過程，因此廣度優(yōu)先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷相同，兩者的不同之處僅在于對頂點訪問的順序不同。

第4節(jié) 圖的應用

4.1 最小生成樹

（1）基本概念：由于生成樹的定義可知，無向連通圖的生成樹不是唯一的。連通圖的一次遍歷所經(jīng)過的邊的集合及圖中所有頂點的集合就構成了該圖的一棵生成樹，對連通圖的不同遍歷，就可能得到不同的生成樹。對于有n個頂點的無向連通圖，無論其生成樹的形態(tài)如何，所有生成樹中都有且僅有n-1條邊。

如果無向連通圖是一個網(wǎng)，那么，它的所有生成樹中必有一棵生成樹的邊的權值總和最小，稱這樣的一棵生成樹為最小代價生成樹（Minimum Cost Spanning Tree），簡稱最小生成樹（MST）。一棵生成樹的代價就是樹中所有的邊的代價之和。

最小生成樹的概念可以應用到許多實際問題中。例如，以盡可能低的總價建造城市間的通信網(wǎng)絡，把十個城市聯(lián)系在一起。在這十個城市中，任意兩個城市之間都可以建造通信線路，通信線路的造價依據(jù)城市間的距離不同而不同，可以構造一個通信線路造價網(wǎng)絡，在網(wǎng)絡中，每個頂點表示城市，頂點之間的邊表示城市之間可構造通信線路，每條邊的權值表示該條通信線路的造價，要想使總的造價最低，實際上就是尋找該網(wǎng)絡的最小生成樹。

構造最小生成樹的方法很多，其中大多數(shù)算法都利用了MST性質(zhì)。MST性質(zhì)描述如下：
設G=(V,E)是一個連通網(wǎng)，其中V為網(wǎng)中所有頂點的集合，E為網(wǎng)中所有帶權邊的集合，再設集合U用于存放G的最小生成樹的頂點。若邊（u，v）是G中所有一端在U中而另一端在V-U中 具有最小權值的一條邊，則存在一棵包含邊（u，v）的最小生成樹。關于MST性質(zhì)的證明請參閱有關書籍，這里略去。

（2）Prim算法和Kruskal算法

假設G =（V，E）為一連通網(wǎng)，其中V為網(wǎng)中所有頂點的集合，E為網(wǎng)中所有帶權邊的集合。設置兩個新的集合U和T，其中集合U用于存放G的最小生成樹中的頂點，集合T存放G的最小生成樹中的邊。令集合U的初值為U={u1}（假設構造最小生成樹時，從頂點u1出發(fā)），集合T的初值為T={}。Prim算法的思想是，從所有u包含U，u包含V-U的邊中，選取具有最小權值的邊（u，v），將頂點v加入集合U中，將邊（u，v）加入集合T中，如此不斷重復，直到U=V時，最小生成樹構造完畢，這時集合T中包含了最小生成樹的所有邊。

Prim算法可用下述過程描述，其中用wuv表示頂點u與頂點v邊上的權值。

1、U ={U1},T={};
 
2、while(U=!V)do
 
(u,v) =min{wun;u包含U，v包含V-U}
 
T =T+{(u,v)}
 
U=U+{V}
 
3、結(jié)束

Prim算法構造最小生成樹的過程示意圖如下：

為實現(xiàn)Prim算法，需設置兩個輔助一維數(shù)組lowcost和closevertex，其中，lowcost用來保存集合V-U中各頂點與集合U中各頂點構成的邊中具有最小權值的邊的權值；數(shù)組closevertex用來保存依附于該邊的在集合U中的頂點。假設初始化狀態(tài)時，U={u1（出發(fā)的頂點）},這時有l(wèi)owcost[0]=0,它表示頂點u1已加入集合中，數(shù)組lowcost的其他各分量的值是頂點u1到其余各頂點所構成的直接邊的權值。然后不斷選取最小的邊（ui，uk）（u包含U,uk包含V-U），每選取一條邊，就將lowcost（k）置為0，表示頂點uk已加入集合U中。由于頂點uk從集合V-U進入集合U后，這兩個集合的內(nèi)容發(fā)生了變化，就需依據(jù)具體情況更新數(shù)組lowcost和closevertex中部分分量的內(nèi)容。

當無向網(wǎng)采用二維數(shù)組存儲的鄰接矩陣存儲時，Prim算法如下：

void Prim(int gm[][MAXNODE],int n,int closevertex[]){
    //    從序號為0的頂點出發(fā)，建立的最小生成樹存于數(shù)組closevertex中
    int lowcost[100],mincost;
    int i,j,k;
    for(i=1;i<n;i++){
        lowcost[i] =gm[0][i];
        closevertex[i] =0;
    }
    lowcost[0] = 0;//從序號0的頂點出發(fā)生成最小生成樹
    closevvertex[0] = 0;
    for(i =1 ;i<n; i++){
        mincost =MAXCOST;
        j =1;        
        k =1;
        while(j<n){
            if(lowcost[j]<mincost&&lowcost[j]!=0){
                mincost =lowcost[j];
                k = j;
            }
            j ++;
        }
        lowcost[k] = 0 ;
        for(j =1 ;j<n;j++){
            if(gm[k][j] <lowcost[j]){
                lowcost[j] =gm[k][j];
                closevertex[j] = k;
            }
        }
    }
}

在上述算法中，第一個for循環(huán)的執(zhí)行次數(shù)為n-1，第二個for循環(huán)中又包含了一個while循環(huán)和一個for循環(huán)，執(zhí)行次數(shù)為2（n-1）2，所以Prim算法的時間復雜度為O(n2）。

Kruskal算法基本思想如下：設G=(V, E)是連通網(wǎng)，集合T存放G的最小生成樹中的邊。初始時，最小生成樹中已經(jīng)包含G中的全部頂點，集合T的初值為T={}，這樣每個頂點就自成一個連通分量。最小生成樹的生成過程是，在圖G的邊集E中按權值自小至大依次選擇邊（u, v），若該邊端點u、v分別屬于當前兩個不同的連通分量，則將該邊（u, v）加入到T，由此這兩個連通分量連接成一個連通分量，整個連通分量數(shù)量就減少了一個；若u、v是當前同一個連通分量的頂點，則舍去此邊，繼續(xù)尋找下一條兩端不屬于同一連通分量的權值最小的邊，依此類推，直到所有的頂點都在同一個連通分量上為止。這時集合T中包含了最小生成樹的所有邊。算法描述如下：

T={};
while(T中的邊數(shù)<n-1){//n為G中的頂點數(shù)
從E中選取當前最短邊(u,v)
刪除E中條邊（u，v）
if((u,v)并入T之后不產(chǎn)生回路)
    將(u,v)并入T中
}

Kruskal 算法構造最小生成樹的過程示意圖：

以上就是“c++鄰接表是什么”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業(yè)資訊頻道。