目录
1. 邻接矩阵表示法1.1 图的邻接矩阵1.2 创建有向网的邻接矩阵2. 邻接表表示法2.1 图的邻接表存储结构2.2 创建有向图的邻接表3. 十字链表表示法3.1 图的十字链表存储结构3.2 创建有向图的十字链表4. 邻接多重表4.1 邻接多重表的存储结构4.2 创建无向图的邻接多重表1. 邻接矩阵表示法
1.1 图的邻接矩阵
图的邻接矩阵表示法（Adjacency Matrix）也称作数组表示法。它采用两个数组来表示图：一个是用于存储顶点信息的一维数组，另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关系数组被称为邻接矩阵。
有向图的邻接矩阵可以指示弧的方向；无向图的邻接矩阵没有方向，所以是对称矩阵；
稀疏图不适于用邻接矩阵来存储，会造成空间浪费。
1.2 创建有向网的邻接矩阵
# include<stdio.h># define MAX_VERTEX_NUM 20//最多顶点个数# define INFINITY 32768//表示极大值，即∞/*图的邻接矩阵表示法*/typedef int AdjType;typedef char VertexData;typedef struct ArcNode {AdjType adj;//无权图用1或0表示是否相邻，带权图则为权值类型}ArcNode;typedef struct {VertexData vertex[MAX_VERTEX_NUM];//顶点向量ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵int vexnum, arcnum;//图的顶点数和弧数}AdjMatrix;/*采用邻接矩阵表示法创建有向网*//*求顶点位置*/int LocateVertex(AdjMatrix* G, VertexData v) {int k;for (k = 0; k < G->vexnum; k++) {if (G->vertex[k] == v)break;}return k;}/*创建有向网*/int CreateDN(AdjMatrix* G) {int i, j, k, weight;VertexData v1, v2;printf("输入图的顶点数和弧数：");//输入图的顶点数和弧数scanf("%d%d", &G->vexnum, &G->arcnum);for (i = 0; i < G->vexnum; i++) {//初始化邻接矩阵for (j = 0; j < G->vexnum; j++)G->arcs[i][j].adj = INFINITY;}printf("输入图的顶点：");for (i = 0; i < G->vexnum; i++)//输入图的顶点scanf(" %c", &G->vertex[i]);for (k = 0; k < G->arcnum; k++) {printf("输入第%d条弧的两个顶点及权值：", k + 1);scanf(" %c %c %d", &v1, &v2, &weight);//输入一条弧的两个顶点及权值i = LocateVertex(G, v1);j = LocateVertex(G, v2);G->arcs[i][j].adj = weight;//建立弧}}/*邻接矩阵的输出*/void AdjMatrixDisplay(AdjMatrix* G) {printf("图的邻接矩阵输出：\n");int i, j;for (i = 0; i < G->vexnum; i++) {printf("\t%c", G->vertex[i]);}printf("\n");for (i = 0; i < G->vexnum; i++) {//输出邻接矩阵printf("%c\t", G->vertex[i]);for (j = 0; j < G->vexnum; j++) {if (G->arcs[i][j].adj == INFINITY)printf("∞\t");elseprintf("%d\t", G->arcs[i][j].adj);}printf("\n");}}int main() {AdjMatrix G;CreateDN(&G);AdjMatrixDisplay(&G);return 0;}
运行结果
2. 邻接表表示法
2.1 图的邻接表存储结构
邻接表（Adjacency List）表示法是图的一种链式存储结构，它只存储图中存在的边信息。在邻接表中，对图中的每一个顶点建立一个带头结点的边链表，每个边链表的头结点又构成一个表头结点表。这样，一个n个顶点的图的邻接表表示由表头结点与边表两部分构成。
①表头结点表：由所有表头结点以顺序结构（向量）的形式存储，以便可以随机访问任一顶点的边链表。表头结点由两部分组成，其中数据域vexdata用于存储顶点的名或其它相关信息；链域firstarc用于指向链表中第一个顶点。
②边表：由表示图中顶点间邻接关系的n个边链表组成。边链表的弧结点结构由三部分组成，邻接点域adjvex用于存放与顶点vi相邻接的顶点在图中的位置；链域nextarc用于指向与顶点vi相关联的下一条边或弧的结点；数据域info用于存放与边或弧相关的信息（如赋权图中每条边或弧的权值）。
# define MAX_VERTEX_NUM 20//最多顶点个数/*图的邻接表表示法*/typedef char VertexData;//弧结点结构typedef struct ArcNode {int adjvex;//该弧指向顶点的位置struct ArcNode* nextarc;//指向下一条弧的指针int info;//与弧相关的信息}ArcNode;//表头结点结构typedef struct VertexNode {VertexData data;//顶点数据ArcNode* firstarc;//指向该顶点的第一条弧的指针}VertexNode;//邻接表结构typedef struct {VertexNode vertex[MAX_VERTEX_NUM];int vexnum, arcnum;//图的顶点数和弧数}AdjList;
2.2 创建有向图的邻接表
/*采用邻接表表示法创建有向图*//*求顶点位置*/int LocateVertex(AdjList* G, VertexData v) {int k;for (k = 0; k < G->vexnum; k++) {if (G->vertex[k].data == v)break;}return k;}/*创建有向图*/int CreateAdjList(AdjList* G) {int i, j, k;VertexData v1, v2;ArcNode* p;printf("输入图的顶点数和弧数：");//输入图的顶点数和弧数scanf("%d%d", &G->vexnum, &G->arcnum);printf("输入图的顶点：");for (i = 0; i < G->vexnum; i++) {//输入图的顶点，初始化顶点结点scanf(" %c", &(G->vertex[i].data));G->vertex[i].firstarc = NULL;}for (k = 0; k < G->arcnum; k++) {printf("输入第%d条弧的两个顶点：", k + 1);scanf(" %c %c", &v1, &v2);//输入一条弧的两个顶点i = LocateVertex(G, v1);j = LocateVertex(G, v2);p = (ArcNode*)malloc(sizeof(ArcNode));//申请新弧结点p->adjvex = j;p->nextarc = G->vertex[i].firstarc;G->vertex[i].firstarc = p;}}
3. 十字链表表示法
3.1 图的十字链表存储结构
十字链表（Orthogonal List）是有向图的另一种链式存储结构。有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，称为顶点结点。
data：用于存储与顶点有关的信息，如顶点的名字等。
firstin：用于指向以该顶点作为弧头的第一个弧顶点。
firstout：用于指向以该顶点作为弧尾的第一个弧顶点。
tailvex：表示弧尾顶点在图中的位置。
headvex：表示弧头顶点在图中的位置。
hlink：指向与此弧的弧头相同的下一条弧。
tlink：指向与此弧的弧尾相同的下一条弧。
info：指向该弧的相关信息，如权值等。
# define MAX_VERTEX_NUM 20//最多顶点个数/*十字链表表示法*/typedef char VertexData;//弧结点结构typedef struct ArcNode {int tailvex, headvex;struct ArcNode* hlink, * tlink;}ArcNode;//顶点结构typedef struct VertexNode {VertexData data;//顶点信息ArcNode* firstin, * firstout;}VertexNode;//十字链表结构typedef struct {VertexNode vertex[MAX_VERTEX_NUM];int vexnum, arcnum;//图的顶点数和弧数}OrthList;
3.2 创建有向图的十字链表
/*创建有向图的十字链表*//*求顶点位置*/int LocateVertex(OrthList* G, VertexData v) {int k;for (k = 0; k < G->vexnum; k++) {if (G->vertex[k].data == v)break;}return k;}/*创建有向图的十字链表*/void CreateOrthList(OrthList* G) {int i, j, k;VertexData vt, vh;ArcNode* p;printf("输入图的顶点数和弧数：");scanf("%d%d", &G->vexnum, &G->arcnum);//输入图的顶点数和弧数printf("输入图的顶点：");for (i = 0; i < G->vexnum; i++) {//输入图的顶点，初始化顶点结点scanf(" %c", &(G->vertex[i].data));G->vertex[i].firstin = NULL;G->vertex[i].firstout = NULL;}for (k = 0; k < G->arcnum; k++) {printf("输入第%d条弧的弧尾和弧头：", k + 1);scanf(" %c %c", &vt, &vh);i = LocateVertex(G, vt);j = LocateVertex(G, vh);p = (ArcNode*)malloc(sizeof(ArcNode));//申请新弧结点p->tailvex = i;p->headvex = j;p->tlink = G->vertex[i].firstout;G->vertex[i].firstout = p;p->hlink = G->vertex[j].firstin;G->vertex[j].firstin = p;}}
4. 邻接多重表
4.1 邻接多重表的存储结构
邻接多重表（Adjacency Multi-list）是无向图的存储结构，它能够提供更为方便的边处理信息。
data：用于存储与顶点有关的信息，如顶点的名字。
firstedge：用于指向第一条依附于该顶点的边。
mark：标志域，用以标记该条边是否被搜索过。
ivex/jvex：为该边依附的两个顶点在图中的位置。
ilink：用于指向下一条依附于顶点ivex的边。
jlink：用于指向下一条依附于顶点jvex的边。
# define MAX_VERTEX_NUM 20//最多顶点个数/*邻接多重表表示法*/typedef char VertexData;//边结点结构typedef struct EdgeNode {int mark, ivex, jvex;struct EdgeNode* ilink, * jlink;}EdgeNode;//顶点结点结构typedef struct {VertexData data;EdgeNode* firstedge;}VertexNode;//邻接多重表结构typedef struct {VertexNode vertex[MAX_VERTEX_NUM];int vexnum, arcnum;//图的顶点数和弧数}AdjMultiList;
4.2 创建无向图的邻接多重表
/*创建无向图的邻接多重表*//*求顶点位置*/int LocateVertex(AdjMultiList* G, VertexData v) {int k;for (k = 0; k < G->vexnum; k++) {if (G->vertex[k].data == v)break;}return k;}/*创建无向图的邻接多重表*/void CreateAdjMultiList(AdjMultiList* G) {int i, j, k;VertexData v1, v2;EdgeNode* p;printf("输入图的顶点数和弧数：");scanf("%d%d", &G->vexnum, &G->arcnum);//输入图的顶点数和弧数printf("输入图的顶点：");for (i = 0; i < G->vexnum; i++) {//输入图的顶点，初始化顶点结点scanf(" %c", &(G->vertex[i].data));G->vertex[i].firstedge = NULL;}for (k = 0; k < G->arcnum; k++) {printf("输入第%d条弧的两个顶点：", k + 1);scanf(" %c %c", &v1, &v2);//输入一条弧的两个顶点i = LocateVertex(G, v1);j = LocateVertex(G, v2);p = (EdgeNode*)malloc(sizeof(EdgeNode));p->ivex = i;p->jvex = j;p->mark = 0;p->ilink = G->vertex[i].firstedge;p->jlink = G->vertex[j].firstedge;G->vertex[i].firstedge = p;G->vertex[j].firstedge = p;}}
参考：耿国华《数据结构——用C语言描述（第二版）》
更多数据结构内容关注我的《数据结构》专栏：/weixin_51450101/category_11514538.html?spm=1001..3001.5482
如果觉得《【数据结构】图的存储结构（邻接矩阵 邻接表 十字链表 邻接多重表）及实现（C语言）》对你有帮助，请点赞、收藏，并留下你的观点哦！
