邻接矩阵
简要说明代码定义基本方法 邻接表
简要说明代码定义基本方法 十字链表
简要说明代码定义基本方法 邻接多重表
简要说明代码定义基本方法
众所周知，图有4种实现方法
- 邻接矩阵邻接表十字链表（有向图）邻接多重表（无向图）
本文将演示以上四种方法的c语言实现，及基本方法
使用的教材：《数据结构（c语言版）》清华大学严蔚敏
以下代码是在学习时写的，如有错误欢迎批评指正。如果您有更好的代码实现方法，欢迎留言
所谓邻接矩阵，就是为图附加一个矩阵。
例如如下图
这是个有向图，并且有4个顶点4条弧
那么用邻接矩阵法来表示的话
顶点集：
[a, b, c, d]
矩阵：
[
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
0
]
begin{bmatrix} 0&1&1&0\ 0 &0&0&0\ 0&0&0&1\ 1&0&0&0end{bmatrix}
⎣⎢⎢⎡0001100010000010⎦⎥⎥⎤
对于无权图，当对应矩阵的顶点集索引值元素为1表示有弧（边），为0表示无弧（边）。当为有权图时，其值即为权值
由于邻接矩阵对于无向图和有向图都适用，因此增加kind以区分是何种图
D: directed 方向
G: graph 图
N: network 网
# define MAX_SIZE 20 // 定义图的最大尺寸
typedef char ElemType;
// 图的种类
typedef enum Kind {
DG, DN, UDG, UDN
} GraphKind;
// 矩阵
typedef struct Matrix {
int adj; // 权
ElemType *info; // 弧相关信息，这个不知道存啥，暂时没搞懂
} Matrix, AdjMatrix[MAX_SIZE][MAX_SIZE];
// 图
typedef struct Graph {
ElemType vexs[MAX_SIZE]; // 顶点集
AdjMatrix arcs; // 邻接矩阵
int vexnum, arcnum; // 当前顶点数和弧数
GraphKind kind; // 图的种类，有向图无向图有向网无向网
}Graph, *pGraph;
基本方法
写在前面：连用两次scanf函数，第二次会取到第一次的换行符。可以用fflush或者setbuf(linux下)清空输入缓冲区。也可以多加一个scanf吃掉n。由于多次测试setbuf没用，因此有很多吃n的scanf。这堆函数是对于有向图写的，无向图、带权的换汤不换药
# include邻接表 简要说明# include # include # define MAX_SIZE 20 # define true 1 # define false 0 typedef char ElemType; typedef int bool; typedef enum Kind { DG, DN, UDG, UDN } GraphKind; typedef struct Matrix { int adj; // 权 ElemType *info; // 弧相关信息 } Matrix, AdjMatrix[MAX_SIZE][MAX_SIZE]; typedef struct Graph { ElemType vexs[MAX_SIZE]; // 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 当前顶点数和弧数 GraphKind kind; }Graph, *pGraph; pGraph CreateGraph(GraphKind kind); void AddVex(pGraph graph, ElemType vex); void AddArc(pGraph graph, ElemType vexa, ElemType vexb); void AddMultiVex(pGraph graph); void AddMultiArc(pGraph graph); bool ExistArc(pGraph graph, ElemType vexa, ElemType vexb); // 看两个顶点之间是否存在弧 void PrintVex(pGraph graph); int main() { // 创建图 pGraph graph = CreateGraph(DG); printf("-------图测试-------n"); int choose; char a, b; while (true) { printf("选择:n1,添加顶点n2,添加多个顶点n3,添加弧n4,添加多个弧n5,打印顶点n6,查询弧n7,打印弧数n8,退出nn"); printf("----n"); scanf("%d", &choose); setbuf(stdin, NULL); switch (choose) { case 1: printf("输入顶点:"); scanf("%c", &a); setbuf(stdin, NULL); AddVex(graph, a); break; case 2: AddMultiVex(graph); break; case 3: printf("输入弧："); scanf("%c %c", &a, &b); setbuf(stdin, NULL); AddArc(graph, a, b); break; case 4: AddMultiArc(graph); break; case 5: PrintVex(graph); break; case 6: printf("输入弧:"); scanf("%c %c", &a, &b); if (ExistArc(graph, a, b)==true) printf("truen"); else printf("falsen"); break; case 7: printf("共有%d条弧n", graph->arcnum); break; default: break; } if (choose==8) break; printf("-----------------------------------"); } return 0; } pGraph CreateGraph(GraphKind kind) { pGraph new = (pGraph) malloc(sizeof(Graph)); memset(new, 0, sizeof(Graph)); new->kind = kind; return new; } void AddVex(pGraph graph, ElemType vex) { graph->vexs[graph->vexnum++] = vex; } void AddArc(pGraph graph, ElemType vexa, ElemType vexb) { // 先找到弧头和弧尾的index int index_a, index_b; for (int i=0; i vexnum; i++) { if (graph->vexs[i]==vexa) index_a = i; if (graph->vexs[i]==vexb) index_b = i; } // 添加关系，弧数+1 graph->arcs[index_a][index_b].adj = 1; graph->arcnum++; } void AddMultiVex(pGraph graph) { char a; printf("请输入顶点: "); scanf("%c", &a); setbuf(stdin, NULL); while (a!='#') { AddVex(graph, a); printf("请输入顶点: "); scanf("%c", &a); scanf("%c", &a); } } void AddMultiArc(pGraph graph) { char a, b, s; printf("请输入弧: "); scanf("%c %c", &a, &b); scanf("%c", &s); while (a!='#' && b!='#') { AddArc(graph, a, b); printf("请输入弧: "); scanf("%c %c", &a, &b); scanf("%c", &s); } } bool ExistArc(pGraph graph, ElemType vexa, ElemType vexb) { int index_a, index_b; for (int i=0; i vexnum; i++) { if (graph->vexs[i]==vexa) index_a = i; if (graph->vexs[i]==vexb) index_b = i; } if (graph->arcs[index_a][index_b].adj!=0) return true; else return false; } void PrintVex(pGraph graph) { for (int i=0; i vexnum; i++) { printf("%ct", graph->vexs[i]); } printf("n"); }
邻接表类似于树的孩子表示法
用一个数组存放顶点集，同时添加链表指明弧（边）的另一端以表示弧的存在
对于邻接表，当
V
1
V_1
V1有1的链表结点时，说明有
V
1
V_1
V1指向
V
2
V_2
V2的弧
逆邻接表和邻接表指向相反
# define MAX_SIZE 20
typedef char ElemType;
typedef enum {
DG, DN, UDG, UDN
} GraphKind;
typedef struct ArcNode {
int adj; // 弧头在顶点集中的索引
struct ArcNode *nextArc; // 指向的下一个弧头
ElemType *info; // 弧的相关信息
} ArcNode;
typedef struct {
ElemType data; // 数据域
ArcNode *firstArc; // 第一个弧头
} VNode, AdjList[MAX_SIZE];
typedef struct {
AdjList vertices; // 数据域
int vexnum, arcnum; // 顶点数，弧数
GraphKind kind; // 图类型
} Graph, *pGraph;
基本方法
# include十字链表 简要说明# include # include # define MAX_SIZE 20 # define true 1 # define false 0 typedef char ElemType; typedef int bool; typedef enum { DG, DN, UDG, UDN } GraphKind; typedef struct ArcNode { int adj; // 指向弧头 struct ArcNode *nextArc; // 指向的下一个弧头 ElemType *info; // 弧尾信息 } ArcNode; typedef struct { ElemType data; // 数据域 ArcNode *firstArc; // 第一个弧头 } VNode, AdjList[MAX_SIZE]; typedef struct { AdjList vertices; // 数据域 int vexnum, arcnum; // 顶点数，弧数 GraphKind kind; // 图类型 } Graph, *pGraph; pGraph CreateGraph(GraphKind kind); void AddVex(pGraph graph, ElemType vex); void AddArc(pGraph graph, ElemType vexa, ElemType vexb); void ShowInfo(pGraph graph); bool ExistArc(pGraph graph, ElemType vexa, ElemType vexb); int main() { pGraph graph = CreateGraph(DG); // 添加结点 AddVex(graph, 'a'); AddVex(graph, 'b'); AddVex(graph, 'c'); AddVex(graph, 'd'); // 添加弧 AddArc(graph, 'a', 'b'); AddArc(graph, 'a', 'c'); AddArc(graph, 'c', 'd'); AddArc(graph, 'c', 'a'); AddArc(graph, 'd', 'a'); AddArc(graph, 'd', 'b'); AddArc(graph, 'd', 'c'); // 输出信息 ShowInfo(graph); // 查看是否存在弧 printf("弧ab: %dn", ExistArc(graph, 'a', 'b')); printf("弧ad: %dn", ExistArc(graph, 'a', 'd')); return 0; } pGraph CreateGraph(GraphKind kind) { pGraph new = (pGraph) malloc(sizeof(Graph)); memset(new, 0, sizeof(Graph)); new->kind = kind; return new; } void AddVex(pGraph graph, ElemType vex) { graph->vertices[graph->vexnum++].data = vex; } void AddArc(pGraph graph, ElemType vexa, ElemType vexb) { // 找到元素索引 int index_a, index_b; for (int i=0; i vexnum; i++) { if (graph->vertices[i].data==vexa) index_a = i; if (graph->vertices[i].data==vexb) index_b = i; } // 创建弧结点 ArcNode *node = (ArcNode *) malloc(sizeof(ArcNode)); memset(node, 0, sizeof(ArcNode)); node->adj = index_b; // 添加弧结点 if (graph->vertices[index_a].firstArc==NULL) graph->vertices[index_a].firstArc = node; else { ArcNode *final = graph->vertices[index_a].firstArc; while (final->nextArc!=NULL) final = final->nextArc; final->nextArc = node; } graph->arcnum++; } void ShowInfo(pGraph graph) { printf("顶点数：%dn弧数:%dn", graph->vexnum, graph->arcnum); } bool ExistArc(pGraph graph, ElemType vexa, ElemType vexb) { // 找到index int index_a, index_b; for (int i=0; i vexnum; i++) { if (graph->vertices[i].data==vexa) index_a = i; if (graph->vertices[i].data==vexb) index_b = i; } // 查看结点 // 以下代码更简洁 ArcNode *p = graph->vertices[index_a].firstArc; while (p!=NULL && p->adj!=index_b) p = p->nextArc; return p!=NULL; }
刚刚在邻接表那块儿，我们提到过邻接表和逆邻接表。十字链表具有这两种优点，即可以表明某个结点指向谁了，也可以表示它被谁指了。十字，用横表示他指别人，竖表示被别人指。例如上图的链表结点（2，0）。横向是2指过来的，竖向是0指的。说明
V
3
V_3
V3指向别人，即
V
1
V_1
V1。而我们从
V
1
V_1
V1也方便找到有谁指向了它
十字链表是用来表示有向图的
# define MAX_SIZE 20
typedef char ElemType;
// 弧
typedef struct ArcNode {
int tailvex, headvex; // 两个维度的指向
struct ArcNode *tlink, *hlink; // 下一个链表接点
ElemType *info;
} ArcNode;
// 顶点
typedef struct VexNode {
ElemType data; // 数据域
ArcNode *firstIn, *firstOut; // 入弧和出弧
} VexNode;
// 图
typedef struct Graph {
VexNode data[MAX_SIZE];
int vexnum, arcnum;
} Graph, *pGraph;
基本方法
# include邻接多重表 简要说明# include # include # define MAX_SIZE 20 # define true 1 # define false 0 typedef char ElemType; typedef int bool; // 弧 typedef struct ArcNode { int tailvex, headvex; struct ArcNode *tlink, *hlink; ElemType *info; } ArcNode; // 顶点 typedef struct VexNode { ElemType data; // 数据域 ArcNode *firstIn, *firstOut; // 入弧和出弧 } VexNode; // 图 typedef struct Graph { VexNode data[MAX_SIZE]; int vexnum, arcnum; } Graph, *pGraph; pGraph CreateGraph(); void AddVex(pGraph graph, ElemType vex); void AddArc(pGraph graph, ElemType vexa, ElemType vexb); void ShowInfo(pGraph graph); bool ExistArc(pGraph graph, ElemType vexa, ElemType vexb); int main() { pGraph graph = CreateGraph(); // 添加顶点 AddVex(graph, 'a'); AddVex(graph, 'b'); AddVex(graph, 'c'); AddVex(graph, 'd'); // 添加弧 AddArc(graph, 'a', 'b'); AddArc(graph, 'a', 'c'); AddArc(graph, 'c', 'a'); AddArc(graph, 'c', 'd'); AddArc(graph, 'd', 'a'); AddArc(graph, 'd', 'b'); AddArc(graph, 'd', 'c'); // 输出 ShowInfo(graph); // 判断弧 printf("弧ab: %dn", ExistArc(graph, 'a', 'b')); printf("弧ba: %dn", ExistArc(graph, 'b', 'a')); printf("弧cb: %dn", ExistArc(graph, 'c', 'b')); printf("弧cd: %dn", ExistArc(graph, 'c', 'd')); return 0; } pGraph CreateGraph() { pGraph new = (pGraph) malloc(sizeof(Graph)); memset(new, 0, sizeof(Graph)); return new; } void AddVex(pGraph graph, ElemType vex) { graph->data[graph->vexnum++].data = vex; } void AddArc(pGraph graph, ElemType vexa, ElemType vexb) { // 找到ab索引 int index_a, index_b; for (int i=0; i vexnum; i++) { if (graph->data[i].data == vexa) index_a = i; if (graph->data[i].data == vexb) index_b = i; } // 创建a的出弧和b的入弧 ArcNode *new = (ArcNode *) malloc(sizeof(ArcNode)); memset(new, 0, sizeof(ArcNode)); new->tailvex = index_a; new->headvex = index_b; // 出弧 if (graph->data[index_a].firstOut==NULL) graph->data[index_a].firstOut = new; else { ArcNode *final = graph->data[index_a].firstOut; while (final->tlink!=NULL) final = final->tlink; final->tlink = new; } // 入弧 if (graph->data[index_b].firstIn==NULL) graph->data[index_b].firstIn = new; else { ArcNode *final = graph->data[index_b].firstIn; while (final->hlink!=NULL) final = final->hlink; final->hlink = new; } graph->arcnum++; } void ShowInfo(pGraph graph) { printf("顶点数：%dn弧数：%dn", graph->vexnum, graph->arcnum); } bool ExistArc(pGraph graph, ElemType vexa, ElemType vexb) { // 找到ab索引 int index_a, index_b; for (int i=0; i vexnum; i++) { if (graph->data[i].data == vexa) index_a = i; if (graph->data[i].data == vexb) index_b = i; } ArcNode *p = graph->data[index_a].firstOut; while (p!=NULL && p->headvex!=index_b) p = p->tlink; return p!=NULL; }
首先很重要的一点，邻接多重表是针对无向图的。
虽然他长得像十字链表，但是横向和竖向指向并不说明指和被指。无向图的边没有方向。因此在定义邻接多重表时不需要设置横向指针和竖向指针，只需要一个firstedge指向链表结点即可
# define MAX_SIZE 20
typedef char ElemType;
typedef enum {
unvisited, visited // 用来表示是否被访问过，以后会用到
} VisitIf;
typedef struct EBox {
VisitIf mark; // 标记是否访问过
int ivex, jvex; // 两个顶点的位置，不区分前后
struct EBox *ilink, *jlink; // 下一个弧结点
ElemType *info; // 边的信息
} EBox;
typedef struct VexBox {
ElemType data; // 顶点数据域
EBox *firstedge; // 边指针
} VexBox;
typedef struct {
VexBox adjmulti[MAX_SIZE]; // 图的数据域
int vexnum, edgenum;
} AMGraph, *pAMGraph;
基本方法
提示：你可以跳过下面这段话，但如果你要看以下的代码的话，你会回来的
在AddArc添加边和ExistEdge检查是否存在边两个函数内，可以看到添加边和查找边的代码多了很多。因为邻接多重表的链表结点是不区分先后次序的（ivex, jvex）。如果要查找ab边，可能ivex表示a的索引jvex表示b，也可能反过来。因此当游走指针从a找b时，跳到下一个结点，需要判断走ilink还是jlink。如果ivex是a，那么要走ilink。
在ExistEdge查找是否存在该边时，在while里面，else表示当ivex和jvex都不是a时，返回false。此时p指针从a出发，但是却到了一个陌生的地方。ivex和jvex都不是a。
ExistEdge在找的时候不用担心边成环时，陷入while的死循环的问题。
# include# include # include # define MAX_SIZE 20 # define true 1 # define false 0 typedef int bool; typedef char ElemType; typedef enum { unvisited, visited } VisitIf; typedef struct EBox { VisitIf mark; // 标记是否访问过 int ivex, jvex; // 两个顶点的位置 struct EBox *ilink, *jlink; // 下一个弧结点 ElemType *info; // 该边信息 } EBox; typedef struct VexBox { ElemType data; // 顶点数据域 EBox *firstedge; // 边指针 } VexBox; typedef struct { VexBox adjmulti[MAX_SIZE]; // 图的数据域 int vexnum, edgenum; } AMGraph, *pAMGraph; pAMGraph CreateGraph(); void AddVex(pAMGraph graph, ElemType vex); void AddArc(pAMGraph graph, ElemType vexa, ElemType vexb); bool ExistEdge(pAMGraph graph, ElemType vexa, ElemType vexb); int main() { // 创建图 pAMGraph graph = CreateGraph(); // 添加顶点 AddVex(graph, 'a'); AddVex(graph, 'b'); AddVex(graph, 'c'); AddVex(graph, 'd'); AddVex(graph, 'e'); // 添加边 AddArc(graph, 'a', 'b'); AddArc(graph, 'a', 'd'); AddArc(graph, 'b', 'c'); AddArc(graph, 'b', 'e'); AddArc(graph, 'c', 'd'); AddArc(graph, 'c', 'e'); // 检查是否存在边 printf("边 ab : %dn", ExistEdge(graph, 'a', 'b')); printf("边 ba : %dn", ExistEdge(graph, 'b', 'a')); printf("边 ac : %dn", ExistEdge(graph, 'a', 'c')); printf("边 ad : %dn", ExistEdge(graph, 'a', 'd')); printf("边 ae : %dn", ExistEdge(graph, 'a', 'e')); printf("边 bc : %dn", ExistEdge(graph, 'b', 'c')); printf("边 bd : %dn", ExistEdge(graph, 'b', 'd')); printf("边 be : %dn", ExistEdge(graph, 'b', 'e')); printf("边 cd : %dn", ExistEdge(graph, 'c', 'd')); printf("边 ce : %dn", ExistEdge(graph, 'c', 'e')); printf("边 de : %dn", ExistEdge(graph, 'd', 'e')); return 0; } pAMGraph CreateGraph() { pAMGraph new = (pAMGraph) malloc(sizeof(AMGraph)); memset(new, 0, sizeof(AMGraph)); return new; } void AddVex(pAMGraph graph, ElemType vex) { graph->adjmulti[graph->vexnum++].data = vex; } void AddArc(pAMGraph graph, ElemType vexa, ElemType vexb) { // 找到两个顶点的index int index_a, index_b; for (int i=0; i vexnum; i++) { if (graph->adjmulti[i].data == vexa) index_a = i; if (graph->adjmulti[i].data == vexb) index_b = i; } // 创建边 EBox *edge = (EBox *) malloc(sizeof(EBox)); memset(edge, 0, sizeof(EBox)); edge->ivex = index_a; edge->jvex = index_b; // 添加到两个顶点 if (graph->adjmulti[index_a].firstedge==NULL) graph->adjmulti[index_a].firstedge = edge; else { EBox *p = graph->adjmulti[index_a].firstedge; while ((p->ivex==index_a && p->ilink!=NULL) || (p->jvex==index_a && p->jlink!=NULL)) { if (p->ivex==index_a) p = p->ilink; else p = p->jlink; } if (p->ivex==index_a) p->ilink = edge; else p->jlink = edge; } if (graph->adjmulti[index_b].firstedge==NULL) graph->adjmulti[index_b].firstedge = edge; else { EBox *p = graph->adjmulti[index_b].firstedge; while ((p->ivex==index_b && p->ilink!=NULL) || (p->jvex==index_b && p->jlink!=NULL)) { if (p->ivex==index_b) p = p->ilink; else p = p->jlink; } if (p->ivex==index_b) p->ilink = edge; else p->jlink = edge; } graph->edgenum++; } bool ExistEdge(pAMGraph graph, ElemType vexa, ElemType vexb) { // 找到两个顶点的index int index_a, index_b; for (int i=0; i vexnum; i++) { if (graph->adjmulti[i].data == vexa) index_a = i; if (graph->adjmulti[i].data == vexb) index_b = i; } // 查找是否存在 EBox *p = graph->adjmulti[index_a].firstedge; // 当p==NULL说明遍历完 // 当 p 的 ivex 和 jvex 都不为 vexb 时，说明不是这个 while (p!=NULL && (p->ivex!=index_a || p->jvex!=index_a)) { // 由于 vexa 在 p 中存放的位置不确定，因此要找到 vexa 的下一个指针域 if (p->ivex==index_a) if (p->jvex==index_b) return true; else p = p->ilink; else if (p->jvex==index_a) if (p->ivex==index_b) return true; else p = p->jlink; else return false; } return false; }
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）