上期讲完邻接矩阵后，我们可以对其分析一下优缺点。
优点：
- 便于判断两个顶点之间是否有边
- 便于计算各个顶点的度【对于有向图无论出度入度都很方便】
- 适用于稠密图【即边数很多的图】
缺点：
- 不便于增加和删除顶点
- 不便于统计边数【需要从头扫描邻接矩阵全部元素】
- 空间复杂度高
针对他的缺点，我们提出另一套方案，采用邻接表来表示图
定义：邻接表，是一种链式存储结构，包含表头结点表和边表
- 表头结点表：由所有表头结点以顺序存储结构存储，包含数据域和链域
- 数据域：用来存放顶点内容【可能是数字、字符】
- 链域：用来指向对应顶点的邻接点
- 边表：包含邻接点域、权值域和链域【权值域可以没有】
- 邻接点域：存放邻接点在数组中的对应位置【即索引，而非数值】
- 权值域：存放顶点与该邻接点的权值
- 链域：用来指向顶点对应的下一个邻接点
(该图没有添加权值，如果有，在边表中邻接点域和链域中点添加即可)
以无向图举例：
开头为各个表头结点，存放顶点vertex和链域firstEdge；而链域firstEdge用来指向顶点的邻接点，没有则为NULL；而后面的边表存放邻接点位置【即在数组中的位置，就是开头的数字】和链域
有向图的邻接表存储定义：
#define mvnum 100
typedef struct EdgeNode{//边表
int adjvex;//数据域
struct EdgeNode *next;//链域
}EdgeNode;
typedef struct VexNode{//表头结点表
int vertex;//表头数据域
EdgeNode *firstEdge;//链域
}VexNode,AdjList[mvnum];
typedef struct Graph{//图
AdjList adjList;//表头结点数组
int vexnum,edgenum;//顶点个数，边数
}Graph;
接下来，我们声明几个我们常用的基本功能函数
void CreateGraph(Graph &G);//图的创建
void Traverse(Graph &G);//图的遍历
代码实现：
#include
using namespace std;
#define mvnum 100
typedef struct EdgeNode{//边表
int adjvex;//数据域
struct EdgeNode *next;//链域
}EdgeNode;
typedef struct VexNode{//表头结点表
int vertex;//表头数据域
EdgeNode *firstEdge;//链域
}VexNode,AdjList[mvnum];
typedef struct Graph{//图
AdjList adjList;//表头结点数组
int vexnum,edgenum;//顶点个数，边数
}Graph;
void CreateGraph(Graph &G);//有向图的创建
void Traverse(Graph &G);//图的遍历
void CreateGraph(Graph &G){
cin>>G.vexnum>>G.edgenum;
for(int i=0;i>G.adjList[i].vertex;//输入各表头顶点
G.adjList[i].firstEdge=NULL;//初始化，将表头结点的链域置空
}
for(int i=0;i>v1>>v2;//v1代表表头，v2代表邻接点
EdgeNode *e=new EdgeNode;
e->adjvex=v2;//这里类似头插法的思想
e->next=G.adjList[i].firstEdge;
G.adjList[i].firstEdge=e;
}
}
void Traverse(Graph &G){
for(int i=0;iadjvex;
p=p->next;
}
cout<
Original: https://blog.csdn.net/m0_54566774/article/details/121629864
Author: 胖橙汁
Title: 图论——邻接表之有向网
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/555987/
转载文章受原作者版权保护。转载请注明原作者出处！