c++邻接表是什么

今天小编给大家分享一下c++邻接表是什么的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。

 图

图状结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图是比树更一般、更复杂的非线性结构，常被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。

第一节 基本概念

1.1 定义和术语

（1）定语：

图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的，其形式化定义为：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是有序的（有序对常常用尖括号“<>”表示），即顶点之间的连线是有方向的，则称该图为有向图。

3、顶点、边、弧、弧头、弧尾：在图中，数据元素vi称为顶点（Vertex）；（vj，vj）表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；如果是在有向图中，一般称这条连线为弧。边用顶点的无序偶对（vi，vj）来表示，称顶点vi和vj互为邻接点，边<vi,vj>依附于顶点vi与顶点vj；弧用顶点的有序偶对<vi,vj>来表示，有序偶对的第一个节点vi被称为始点(或弧尾），在图中就是不带箭头的一端；有序偶对的第二个节点vj被称为终点(或弧头），在图中就是带箭头的一端。

4、无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n（n-1）/2条边。

5、有向完全图：在有一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。

6、顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD(v)。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(V)；出度是指以顶点v为始点的弧的数目，记为OD(V)。有TD(V)=ID(v)+OD(v)。

7、边的权、网：与边有关的数据信息称为权(Weight)。在实际应用中，权值可以有某种含义。例如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间或其他代价等。边上带权的图称为网或网络（network）。

8、路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分别为图中的边。路径上边的数目称为路径长度。

9、简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点与最后一个顶点相同的 路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。

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条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。

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出发深度优化遍历图G。
10、BFSTtaverse(G,v)：在图G中，从顶点v出发广度优先遍历图G。

在一个图中，顶点是没有先后次序的，但当采用某一种确定的存储方式存储后，存储结构中顶点的存储次序成了顶点之间的相对次序，这里用顶点在图中的位置表示该顶点的存储顺序；同样的道理，对一个顶点的所有邻接点，采用该顶点的第i个邻接点表示与该顶点相邻接的某个顶点的存储顺序，在这种意义下，图还有以下的基本操作。

11、LocateVex（G，u）：在图G中找到顶点u，返回该顶点在图中位置。
12、FirstAdjVex（G，v）：在图G中，返回v的第一个邻接点。若顶点在G中没有邻接顶点，则返回“空”。
13、NextAdjVex(G，v，w)：在图G中， 返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回"空”。

第二节 存储结构

图是一种结构复杂的数据结构，表现在不仅各个顶点的度可以千差万别，而且顶点之间的逻辑关系也错综复杂。从图的定义可知，一个图的信息包括两部分，即图中顶点的信息及描述顶点之间的关系——边或弧的信息。因此，无论采用什么方法建立图的存储结构，都要完整、准确地反映这两方面的信息。

2.1 邻接矩阵

所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中的顶点信息，用矩阵表示图中各顶点之间的邻接关系。假设图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是网，则邻接矩阵可定义为：

A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的边 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的边。
其中，wij表示边(Vi,vj)或<vi,vj>上的权值；表示一个计算机允许的、大于所有边上权值的数。

（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上或下三角矩阵的元素即可。

（2）对于无向图，邻接矩阵的第i行或第i列非零元素或非&元素的个数正好是第i个顶点的度TD(vi)。

（3）对于有向图，邻接矩阵的第i行和第i列非零元素或非&元素的个数正好是第i个顶点的出度OD(vi)或入度ID(vi)。

（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

在实际应用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外，还有图的顶点数和边数。故可将其形式描述如下：

#define MaxVertexNum 100 
typedef char VertexType;
typedef int EdgeType;
typedef struct{
    VertexType vexs[MaxVertexNum];//顶点表
    EdgeType edges[MaxVertexNum] [MaxVertexNum];//相邻矩阵，即边表
    int n,e;//顶点数和边数
 }MGraph;

2.2 邻接表

邻接表（Adjacency List）是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图邻接表。

在邻接表表示中有两种结点结构：一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成。另一种是边表即邻接表结点，它由邻接点域（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个头结点和2e个表结点。显然，在边稀疏（e<<n(n-1)/2）的情况下，用邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息较多时更是如此。在无向图的邻接表中，顶点vi的度恰为第i个链表中的结点数；而在有向图中，第i个链表中的结点个数只是顶点v1的出度，求入度，必须遍历整个整个邻接表。在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。有时，为了便于确定顶点的入度或以顶点vi为头的弧，可以建立一个有向的逆邻接表，即对每个顶点vi建立一个链接以vi为头的弧的链表。

在建立邻接表或逆邻表时，若输入的顶点信息即为顶点的编号，则建立邻接表的复杂度为O(n+e)，否则，需要通过查找才能得到顶点在图中位置，则时间复杂度为O(ne)。

在邻接表上容易找到任意顶点的第一个邻接点和下一个邻结点，但要判定任意两个顶点(vi和vj)之间是否有边或弧相连，则需查找第i个或第j个链表，因此，不如邻接矩阵方便。

第3节 图的遍历

图的遍历是指从图中的任意顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍历操作的基础之上的。

3.1 深度优先搜索（Depth First Search，DFS）

类似于树的先根遍历，是树的先根遍历的推广。假设初始化状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依然从v的未被访问的邻接点出发深度优化遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。如下图：

a所示的无向图G4，进行图的深度优先搜索。假设从顶点v1出发进行搜索，在访问了顶点v1之后，选择邻接点v2。因为v2未曾访问，则从v2出发进行搜索，以此类推，接着从v4,v8,v5出发进行搜索。在访问了v5之后，由于其邻接点都已经被访问了，则搜索回到v8，同理，搜索继续回到到v4,v2,v1。此时，由于v1的另一个邻接点未被访问，则查找又从v1到v3，v6，v7。显然，这是一个递归的过程。为了遍历过程中便于区分顶点是否已被访问，需要附设访问标志数组visited[0:n-1]，其初值为FALSE,一旦某个顶点被访问，则其相应的分量置为TRUE。

void DFS(Graph G,int v){
    //从第v个顶点出发递归地深度优先遍历图G
    visited[v] =TRUE;
    //访问第v个点
    VisitFunc(v);
    for(w=FirstAdjVex(G,V) ;w ;w =NextAdjVex(G,v,w))
    //对v的尚未访问邻接顶点w递归调用DFS
    if(!visited[w]) 
        DFS(G,W);
}

深度优化搜索算法实现：

void DFSTraverseAL(ALGraph *G){
        /*深度优先遍历以邻接表存储的图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为出发点对邻接表存储的图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 广度优先搜索（Breadth First Search，BFS）

类似于树的按层次遍历的过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以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。和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且为了顺次访问路径长度为1，2，3···的顶点，需要附设队列以存储已被访问的路径长度为1，2，···的顶点。从图的某一点v出发，非递归地进行广度优先遍历的过程算法如下所示：

voidBFSTraverse(Grapg G,Status （*Visit）（int v)){
    //按广度优先非递归遍历图G，使用辅助队列Q和访问标志数组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);
        }
    }
}

下面算法给出了对以邻接矩阵为存储结构的图G进行广度优先搜索实现的C语言描述。广度优先搜索算法：

 /*广度优先遍历以邻接矩阵存储的图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为出发点，对图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*/

分析上述算法，每个顶点最多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者的不同之处仅在于对顶点访问的顺序不同。

第4节 图的应用

4.1 最小生成树

（1）基本概念：由于生成树的定义可知，无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树，对连通图的不同遍历，就可能得到不同的生成树。对于有n个顶点的无向连通图，无论其生成树的形态如何，所有生成树中都有且仅有n-1条边。

如果无向连通图是一个网，那么，它的所有生成树中必有一棵生成树的边的权值总和最小，称这样的一棵生成树为最小代价生成树（Minimum Cost Spanning Tree），简称最小生成树（MST）。一棵生成树的代价就是树中所有的边的代价之和。

最小生成树的概念可以应用到许多实际问题中。例如，以尽可能低的总价建造城市间的通信网络，把十个城市联系在一起。在这十个城市中，任意两个城市之间都可以建造通信线路，通信线路的造价依据城市间的距离不同而不同，可以构造一个通信线路造价网络，在网络中，每个顶点表示城市，顶点之间的边表示城市之间可构造通信线路，每条边的权值表示该条通信线路的造价，要想使总的造价最低，实际上就是寻找该网络的最小生成树。

构造最小生成树的方法很多，其中大多数算法都利用了MST性质。MST性质描述如下：
设G=(V,E)是一个连通网，其中V为网中所有顶点的集合，E为网中所有带权边的集合，再设集合U用于存放G的最小生成树的顶点。若边（u，v）是G中所有一端在U中而另一端在V-U中 具有最小权值的一条边，则存在一棵包含边（u，v）的最小生成树。关于MST性质的证明请参阅有关书籍，这里略去。

（2）Prim算法和Kruskal算法

假设G =（V，E）为一连通网，其中V为网中所有顶点的集合，E为网中所有带权边的集合。设置两个新的集合U和T，其中集合U用于存放G的最小生成树中的顶点，集合T存放G的最小生成树中的边。令集合U的初值为U={u1}（假设构造最小生成树时，从顶点u1出发），集合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、结束

Prim算法构造最小生成树的过程示意图如下：

为实现Prim算法，需设置两个辅助一维数组lowcost和closevertex，其中，lowcost用来保存集合V-U中各顶点与集合U中各顶点构成的边中具有最小权值的边的权值；数组closevertex用来保存依附于该边的在集合U中的顶点。假设初始化状态时，U={u1（出发的顶点）},这时有lowcost[0]=0,它表示顶点u1已加入集合中，数组lowcost的其他各分量的值是顶点u1到其余各顶点所构成的直接边的权值。然后不断选取最小的边（ui，uk）（u包含U,uk包含V-U），每选取一条边，就将lowcost（k）置为0，表示顶点uk已加入集合U中。由于顶点uk从集合V-U进入集合U后，这两个集合的内容发生了变化，就需依据具体情况更新数组lowcost和closevertex中部分分量的内容。

当无向网采用二维数组存储的邻接矩阵存储时，Prim算法如下：

void Prim(int gm[][MAXNODE],int n,int closevertex[]){
    //    从序号为0的顶点出发，建立的最小生成树存于数组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的顶点出发生成最小生成树
    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循环的执行次数为n-1，第二个for循环中又包含了一个while循环和一个for循环，执行次数为2（n-1）²，所以Prim算法的时间复杂度为O(n²）。

Kruskal算法基本思想如下：设G=(V, E)是连通网，集合T存放G的最小生成树中的边。初始时，最小生成树中已经包含G中的全部顶点，集合T的初值为T={}，这样每个顶点就自成一个连通分量。最小生成树的生成过程是，在图G的边集E中按权值自小至大依次选择边（u, v），若该边端点u、v分别属于当前两个不同的连通分量，则将该边（u, v）加入到T，由此这两个连通分量连接成一个连通分量，整个连通分量数量就减少了一个；若u、v是当前同一个连通分量的顶点，则舍去此边，继续寻找下一条两端不属于同一连通分量的权值最小的边，依此类推，直到所有的顶点都在同一个连通分量上为止。这时集合T中包含了最小生成树的所有边。算法描述如下：

T={};
while(T中的边数<n-1){//n为G中的顶点数
从E中选取当前最短边(u,v)
删除E中条边（u，v）
if((u,v)并入T之后不产生回路)
    将(u,v)并入T中
}

Kruskal 算法构造最小生成树的过程示意图：

以上就是“c++邻接表是什么”这篇文章的所有内容，感谢各位的阅读！相信大家阅读完这篇文章都有很大的收获，小编每天都会为大家更新不同的知识，如果还想学习更多的知识，请关注亿速云行业资讯频道。