图的基本概念参阅：/qq_41453285/article/details/104151973图的描述：无权图最常用的描述方法都是基于邻接的方式：邻接矩阵、邻接链表、邻接数组有权图也使用无权图的描述方法，只需要将无权图稍做修改就可以了（详细见下面介绍）本文是概念讲述，编码实现参阅下一篇文章：/qq_41453285/article/details/104465857

一、无权图描述之邻接矩阵

邻接矩阵的定义

一个n顶点图G=(V,E)的邻接矩阵是一个n*n的矩阵（假设是A），其中每个元素都是0或1.假设V={1,2,3,...,n}如果G是一个无向图，则元素的定义如下：如果G是有向图，那么其中的元素定义如下：根据上面的两个公式，可以得到下面的结论：无向图的邻接矩阵有下面的特征：无向图的邻接矩阵是对称的顶点i的度=矩阵第i行（列）中1的个数完全图的邻接矩阵中，对角元素为0，其余全为1有向图的邻接矩阵有下面的特征：无向图的邻接矩阵可能是不对称的顶点i的出度=第i行元素之和，顶点的入度=第i列元素之和。因此顶点的度=第i行元素之和+第i列元素之和完全图的邻接矩阵中，对角元素为0，其余全为1

下面是一些无向图与有向图以及它们的邻接矩阵定义：

将邻接矩阵映射到数组

方法一：利用A(i,j)=1，当且仅当a[i][j]是true，1<=i<=n，1<=j<=n，因此n*n的邻接矩阵需要映射到一个(n+1)*(n+1)的布尔型数组中，此时需要字节方法二：利用A(i,j)=1，当且仅当a[i-1]a[j-1]是true，1<=i<=n，1<=j<=n，因此n*n的邻接矩阵需要映射到一个n*n的布尔型数组中，此时需要字节，比方法一减少了2n+1字节方法三：根据定义我们知道，所有对侥幸元素都是0而不需要存储，因此可以对角线元素去掉，进一步减少n字节的存储空间，压缩之后可以得到一个上（或下）三角矩阵缺陷：压缩之后虽然减少了存储空间，但是代价不小，因为定点的外部索引和在图中的内部描述不匹配。这样一来，不仅代码容易出错，而且访问边的时间也会增加。因此我们不建议这种做法例如把上面的三个邻接矩阵去掉对角线元素之后，如下图所示（阴影部分是原邻接矩阵的下三角部分）方法四：无向图邻接矩阵是对称的，因此只需要存储上三角（或下三角）的元素，所以可以使用邻接矩阵来实现，此时所需空间仅为()/2字节，这对大型图来说是很有意义的邻接矩阵参阅：/qq_41453285/article/details/103258171

复杂度分析

使用邻接矩阵时，要确定邻接至或邻接于一个给定节点的集合需要用时Θ(n)。然而，增加或删除一条边仅需用时Θ(1)

邻接矩阵编码实现

下面我们创建无向网，主要思想为：①输入总顶点数和总边数②依次输入点的信息存入顶点表中③初始化邻接矩阵，使每个权值初始化为极大值④构造邻接矩阵代码如下所示：

#include <iostream>using namespace std;#define MVNum100 // 顶点个数typedef int VerTexType; // 假设顶点的数据类型为inttypedef int ArcType;// 假设边的权值类型为整型typedef struct{VerTexType vexs[MVNum];// 顶点表ArcType arcs[MVNum][MVNum]; // 邻接矩阵int vecnum, arcnum; // 图的当前顶点数和边数} AMGraph;int LocateVex(AMGraph G, VerTexType u);// 创建无向网Gint createUDN(AMGraph &G){// 输入总顶点数、总边数std::cout << "请输入总顶点数与总边数: ";std::cin >> G.vecnum >> G.arcnum;int i, j, k;// 依次输入点的信息std::cout << "请输入点的信息: ";for(i = 0; i < G.vecnum; ++i)std::cin >> G.vexs[i];// 初始化邻接矩阵for(i = 0; i < G.vecnum; ++i){for(j = 0; j < G.vecnum; ++j)G.arcs[i][j] = 0; // 边的权值均置为0(也可以置为极大值)}std::cout << "请输入" << G.arcnum << "条边的信息: " << std::endl;for(k = 0; k < G.arcnum; ++k){int v1, v2, w;// 输入一条边所依附的顶点及边的权值std::cin >> v1 >> v2 >> w;// 确定v1和v2在G中的位置i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = w; // 边<v1, v2>的权值置为wG.arcs[j][i] = G.arcs[i][j]; // 置<v1, v2>的对称边<v2, v1>的权值为w}return 1;}// 在图G中查找顶点u，存在则返回顶点表中的下标，否则返回-1int LocateVex(AMGraph G, VerTexType u){int i;for(i = 0; i < G.vecnum; ++i)if(u == G.vexs[i])return i;return -1;}void printUDN(AMGraph &G){for(int i = 0; i < G.vecnum; ++i){for(int j = 0; j < G.vecnum; ++j){std::cout << G.arcs[i][j] << " ";}std::cout << std::endl;}}int main(){AMGraph G;// 创建无向网createUDN(G);// 打印无向网信息std::cout << "无向网的邻接矩阵为: " << std::endl;printUDN(G);return 0;}

假设我们输入的无向网是上面的图片，下面程序的运行效果与图片中的一致附加：如果要构造无向图，则只把上面的代码修改2个地方即可： 初始化邻接矩阵时，w均为0构造邻接矩阵时，w为1附加：如果要构造有向网，则只把上面的代码修改1个地方即可：邻接矩阵是非对称矩阵，仅为G.arcs[i][j]赋值，无需为G.arcs[j][i]赋值附加：如果要构造有向图，只需要把"无向图+有向网"的注意事项都修改即可

邻接矩阵优缺点

优点：直观、简单、好理解方便检查任意一对顶点间是否存在边方便找任一顶点的所有"邻接点"（有边直接相连的顶点）方便就算任一顶点的"度"（从该点发出的边数为"出度"，指向该点的边数为"入度"） 无向图：对应行（或列）非0元素的个数有向图：对应行非0元素的个数是"出度"；对应列非0元素的个数是"入度"缺点：不便于增加和删除顶点浪费空间——存稀疏图（点很多但是边很少）有大量无效元素，对于稠密图（特别是完全图）还是很合适的

二、无权图描述之邻接链表

一个顶点i的邻接表是一个线性表，它包含所有邻接于顶点i的顶点。在一个图的邻接表描述中，图的每一个顶点都有一个邻接表。当邻接表用链表表示时，就是邻接链表

邻接链表的描述

我们假设使用数组aList来描述所有的邻接表aList[i].firstNode指向顶点i的邻接表的第一个顶点如果x指向链表aList[i]的一个顶点，那么(i,x->element)是图的一条边，其中element的数据类型是整型int下图是一些无向图与有向图以及它们对应的邻接链表的描述：

特点

假设现在我们有这样一个有向图下面是它的邻接表形式：顶点Vi的出度为第i个单链表中的节点个数顶点Vi的入度为整个单链表中邻接点域值是i-1的结点个数下面是它的逆邻接表形式：顶点Vi的入度为第i个单链表中的节点个数顶点Vi的出度为整个单链表中邻接点域值是i-1的结点个数

复杂度分析

一个指针和一个整数各需要4字节的存储空间，因此用邻接链表描述一个n顶点的图需要8(n+1)字节存储n+1个firstNode指针和aList链表的listSize域，需要4*2*m字节存储m个链表节点，每个链表节点的两个域next和element各需要4字节，其中对于无向图m=2e，对于无向图m=3（其中e是边数）当e远远小于时，邻接链表比邻接矩阵需要更少的空间。例如，一个e=n的有向图，用邻接链表描述需要16n+8字节，用压缩的邻接链表矩阵描述需要字节。因此，当e=n>=17时，邻接链表描述所需空间更少在邻接链描述中，确定邻接于顶点i的顶点需要用时Θ(邻接于顶点i的顶点数)。插入或删除一条边(i,j)的用时，对无向图是，对无向图是

演示案例

已知某网的邻接表如下所示，请画出该网络网络如下所示

邻接链表编码实现

顶点的结构如下所示：

#define MVNum100 // 顶点个数typedef int VerTexType; // 假设顶点的数据类型为inttypedef int ArcType;// 假设边的权值类型为整型typedef struct VNode {VerTexType data; // 顶点信息ArcNode *firstarc; // 指向第一条依附该顶点的边的指针} VNode, AdjList[MVNum];

弧（边）的结点结构如下：

typedef struct ArcNode {int adjvex; // 该边指向的顶点的位置struct ArcNode* nextarc; // 指向下一条边的指针//OtherInfo info; // 和边相关的信息(例如权等)} ArcNode;

图的定义如下：

typedef struct {AdjList vertices;int vexnum, arcnum; // 图的当前顶点数和弧数} ALGraph;

下面的总的编码实现，算法的思想为：①输入总顶点数和总边数②建立顶点表依次输入点的信息存入顶点表中使么个表头结点的指针域初始化为NULL③创建邻接表依次输入每条边依附的两个顶点确定两个顶点的序号i和j，建立边结点将此边节点分别插入到Vi和Vj对应的两个链表的头部

#include <iostream>using namespace std;#define MVNum100 // 顶点个数typedef int VerTexType; // 假设顶点的数据类型为inttypedef int ArcType;// 假设边的权值类型为整型struct ArcNode;// 顶点的结构typedef struct VNode {VerTexType data; // 顶点信息ArcNode *firstarc; // 指向第一条依附该顶点的边的指针} VNode, AdjList[MVNum];// 弧（边）的结点结构typedef struct ArcNode {int adjvex; // 该边指向的顶点的位置struct ArcNode* nextarc; // 指向下一条边的指针//OtherInfo info;// 和边相关的信息(例如权等)} ArcNode;// 图的定义typedef struct {AdjList vertices;int vexnum, arcnum; // 图的当前顶点数和弧数} ALGraph;int LocateVex(ALGraph G, VerTexType u);// 创建无向网的邻接表实现int CreateUDG(ALGraph &G){// 输入总顶点数，总边数std::cout << "输入总顶点数和总边数: ";std::cin >> G.vexnum >> G.arcnum;int i, j;// 输入各点, 构造表头结点表std::cout << "输入" << G.vexnum << "个顶点的值:";for(int i = 0; i < G.vexnum; ++i){// 输入顶点值std::cin >> G.vertices[i].data;// 初始化表头结点的指针域G.vertices[i].firstarc = NULL;}// 输入各边，构造邻接表std::cout << "输入" << G.arcnum << "条边的顶点信息:" << std::endl;for(int k = 0; k < G.arcnum; ++k){// 输入一条边依附的两个顶点int v1, v2;std::cin >> v1 >> v2;i = LocateVex(G, v1);j = LocateVex(G, v2);// 生成一个新的边结点p1ArcNode *p1 = new ArcNode; p1->adjvex = j; // 邻接点序号为jp1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1; // 将新结点p1插入顶点Vi的边表头部// 生成一个新的边结点p2ArcNode *p2 = new ArcNode; p2->adjvex = i; // 邻接点序号为ip2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2; // 将新结点p2插入顶点Vj的边表头部}return 1;}// 在图G中查找顶点u，存在则返回顶点表中的下标，否则返回-1int LocateVex(ALGraph G, VerTexType u){int i;for(i = 0; i < G.vexnum; ++i)if(u == G.vertices[i].data){return i;}return -1;}void printGraph(ALGraph &G){for(int i = 0; i < G.vexnum; ++i){std::cout << G.vertices[i].data;ArcNode* temp = G.vertices[i].firstarc;while(temp != NULL){std::cout << "->" << temp->adjvex;temp = temp->nextarc;}std::cout << std::endl;}}int main(){ALGraph G;// 创建无向网的邻接表实现CreateUDG(G);// 打印无向网printGraph(G);return 0;}

假设本次输入的数据是下面的图片，那么程序的运行效果与预期一致（abcde更换为了01234）

邻接矩阵与邻接链表的关系

联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非0元素的个数区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列嚎与顶点编号一致），但邻接表不唯一（链表次序与顶点编号无关）②邻接矩阵的空间复杂度为O()，而邻接表的空间复杂度为O(n+e)用途：邻接矩阵多用于稠密图，邻接表多用于稀疏图

三、无权图描述之邻接数组

一个顶点i的邻接表是一个线性表，它包含所有邻接于顶点i的顶点。在一个图的邻接表描述中，图的每一个顶点都有一个邻接表。当邻接表用数组表示时，就是邻接数组

邻接数组的描述

方法一：用下图所示的邻接数组来表示，其中每一个索引处都是一个数组方法二：使用二维数组来表示，假设是aList[][]，其中aList[i]容量等于顶点i的邻接表长度

复杂度分析

邻接数组比邻接链表少用4m字节，因为不需要next指针域（这样的指针域有m个）而大部分的图操作，无论是邻接链表还是用邻接数组，其渐近时间复杂性是相同的。但是根据以往的实验，我们认为，对大部分的图操作，邻接数组的用时要少于邻接链表

注意：对邻接矩阵和邻接表所做的空间需求分析是渐近分析，而实际的实现所需空间可能要多一些，因为实际的代码可能要存储诸如顶点和边的个数，这些量在我们的分析中没有考虑

四、有权图的描述

将无权图的描述进行扩充就可以得到加权图的描述

邻接矩阵描述

用成本邻接矩阵C描述加权图，如果C(i,j)的权，那么它的使用方法和邻接矩阵的使用方法一样在这种描述中，因为矩阵中的值代表的是权值，因此不能单单使用0来描述不存在的边，在实际编程中可以给不存在的边指定一个很大的值（这个很大的值可以用变量noEdge来命名）下图是三个加权图以及邻接矩阵的描述：

邻接链表描述

因为有了权值，所以链表的元素有两个域vertex和weight，分别表示节点的编号与节点的权值下图是对于一个无向加权图的描述

邻接数组描述

原理与邻接链表相似，只是元素使用数对(vertex,weight)表示。不再讲述

五、附加：十字链表与邻接多重表

在上面我们可以使用邻接表表示有向图和无向图，但是都有缺点： 当用邻接表表示有向图时：求节点的度困难。改进方法是使用十字链表当用邻接表表示无向图时：每条边都要存储2遍。改进方法是使用邻接多重表关系如下：

十字链表

十字链表是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表有向图中的每一条弧对应十字链表中的一个弧节点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点节点如下图所示：

邻接多重表

回顾邻接表的特点：容易求得顶点和边的信息，但缺点是某些操作不方便（例如删除一条边需找表示此边的两个节点，如下图所示）如下图所示：

C++(数据结构与算法):55---无权图与有权图的描述（邻接矩阵 邻接链表 邻接数组 十字链表 邻接多重表）