失眠网 > 数据结构——无向图创建邻接表以及深度遍历广度遍历（C语言版）

数据结构——无向图创建邻接表以及深度遍历广度遍历（C语言版）

时间：2022-05-31 22:42:41

摘自：数据结构——无向图创建邻接表以及深度遍历、广度遍历（C语言版）
作者：正弦定理
发布时间：-12-22 20:55:12
网址：/chinesekobe/article/details/111409503

数据结构——无向图创建邻接表以及深度遍历、广度遍历

一、邻接表概念二、邻接表实现（1）准备前提——结构体定义（2）创建边链表（3）打印边链表（4）深度优先遍历（5）广度优先搜索（6）全部代码

一、邻接表概念

在无向图中，顶点存储在顶点表中，以一个顶点为标记，指向边链表，两者组合在一起，称为邻接表

对无向图的每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图则是以顶点vi为尾的弧）。这个单链表就称为顶点vi的边表（对于有向图则称为出边表）边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）邻接表中存在两种结点：顶点表结点和边表结点顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成边表（邻接表）结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成

如图：

二、邻接表实现

具体样例

基本每一步，都有注释！！可认真看并理解！！！

（1）准备前提——结构体定义

#define MAXSIZE 100//深度遍历标记数组 int DfsVist[MAXSIZE]; //广度遍历标记数组 int BfsVist[MAXSIZE];//边链表 typedef struct EdgeLink{int Local;//存放该顶点对应边链表中数据 struct EdgeLink *next;//边链表节点指针 }Edge,*ELINK;//顶点表 typedef struct VertexLink{int Vertex;//存放一条边链表对应的顶点 ELINK FirstNode;//指向该顶点对应边链表的头节点 }Vertex[MAXSIZE],*VLINK;//存放顶点和边，指向顶点表结构体数组 typedef struct MyGraph{int Vnum;//存放顶点数 int Enum;//存放边数 Vertex List;//边链表对应的顶点表中顶点结构体 }MyGraph;1234567891011121314151617181922232425262728293031323334

（2）创建边链表

//创建边链表void CreateLink(MyGraph *T){int i,j;int v1,v2;ELINK p;//边链表指针 ELINK q;printf("请输入顶点数和边数(空格隔开):\n");scanf("%d%d",&(T->Vnum),&(T->Enum));//初始化顶点表结构体数组 for(i=0;i<T->Vnum;i++){printf("请输入第%d个顶点的信息:\n",i+1);scanf("%d",&(T->List[i].Vertex));//存放顶点在顶点表中 T->List[i].FirstNode = NULL; //让每个顶点表第一个指向边链表的指针为NULL }//打印顶点坐标和顶点表中顶点数据 printf("---------------------------\n"); for(i=0;i<T->Vnum;i++){printf("顶点下标为:%d 顶点数据为: %d\n",i,T->List[i].Vertex); }printf("---------------------------\n");//插入边链表数据for(i=0;i<T->Enum;i++){//因为顶点表为顺序表，所以要按顶点顺序输入相连边 printf("请输入两个连接顶点下标(空格隔开):\n");scanf("%d%d",&v1,&v2);getchar(); q = (ELINK)malloc(sizeof(Edge));//创建边链表节点，分配内存 q->Local = v2;//记录与该顶点连接边的顶点坐标q->next = NULL;//让尾巴指向NULL if(!T->List[v1].FirstNode){//判断是否为这个顶点第一个指向的数据 T->List[v1].FirstNode = q;}else{//这个顶点已经指向了一条边，以这条边为头节点，尾插法 p = T->List[v1].FirstNode;//临时存放头节点 while(p->next)//让节点指针遍历到尾巴上 {p = p->next;}p->next = q;//让新插的节点连接到之前边节点的尾巴上 }q = (ELINK)malloc(sizeof(Edge));//创建边链表节点，分配内存 q->Local = v1;//记录与该顶点连接边的顶点坐标q->next = NULL;//让尾巴指向NULL if(!T->List[v2].FirstNode){//判断是否为这个顶点第一个指向的数据 T->List[v2].FirstNode = q;}else{//这个顶点已经指向了一条边，以这条边为头节点，尾插法 p = T->List[v2].FirstNode;//临时存放头节点 while(p->next)//让节点指针遍历到尾巴上 {p = p->next;}p->next = q;//让新插的节点连接到之前边节点的尾巴上 }} }123456789101112131415161718192223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283

（3）打印边链表

//打印邻接表 void PrintLink(MyGraph *S) {MyGraph *T = S;ELINK Q;//防止边链表指针指到NULL ，用临时指针代替遍历打印 int i;printf("打印邻接表结果如下:\n");for(i=0;i<T->Vnum;i++){Q = T->List[i].FirstNode;//接受每个顶点指向对应边链表的头节点指针 printf("%d--->",i);while(1){if(Q == NULL)//指针指到尾巴 NULL{putchar('\n');break;}printf("------->%3d",Q->Local);Q = Q->next;}}putchar('\n');}1234567891011121314151617181922232425262728

（4）深度优先遍历

//*****************深度优先遍历算法—邻接表 *****************//void DFS_Link(MyGraph *T,int n){int i,j;ELINK q;//指向边链表节点指针 if(n<0 || n>=T->Vnum){printf("输入有误\n");return;}DfsVist[n] = 1;//遍历一个顶点，做下标记 1 printf(" %d",T->List[n].Vertex);q = T->List[n].FirstNode;//q指向下标为i所对顶点对应的边链表的第一个边结点while(q!=NULL){if(DfsVist[q->Local]!=1){j = q->Local;DFS_Link(T,j);} q = q->next;}} //初始化深度遍历—邻接表 void Init_DFSLINK(MyGraph *Q){int i;for(i=0;i<Q->Vnum;i++){DfsVist[i] = 0;}for(i=0;i<Q->Vnum;i++){if(!DfsVist[i]){DFS_Link(Q,i);//此顶点没有被标记，开始递归遍历}}putchar('\n'); }1234567891011121314151617181922232425262728293031323334353637383940414243444546474849505152

（5）广度优先搜索

//广度遍历 void BFS(MyGraph *S,int t){ELINK P; //指向顶点所对应的边链表中 int i;int v;//用来接收边链表对应的顶点//创建一个数组队列 int Queue[MAXSIZE];int front = 0;//队头 int rear = 0;//队尾 printf("%d ",S->List[t].Vertex);//输出当前遍历边链表的顶点 BfsVist[t] = 1;//将该顶点作标记rear = (rear+1)%MAXSIZE;//入队一个让队尾指向后移一位Queue[rear] = t; //将该顶点入队 while(front != rear)//若front == rear，表明这个顶点在边链表上连接的顶点已经遍历完毕 {front = (front+1)%MAXSIZE;//出队 v = Queue[front];//得到此时遍历到顶点坐标 P = S->List[v].FirstNode;//遍历当前顶点指向边链表中连接的其他顶点//也就是换个顶点的边链表继续遍历查找剩余顶点 while(P!=NULL){if(BfsVist[P->Local] == 0){printf("%d ",P->Local+1);//输出连接边顶点 BfsVist[P->Local] = 1;//作标记,表示这个顶点已经搜索过 rear = (rear+1)%MAXSIZE;//将该下标入队 Queue[rear] = P->Local;//把遍历到新的边链表对应的顶点坐标入队 }P = P->next;//遍历这个顶点的边链表 }} } //BFS广度遍历初始化void Init_BFS(MyGraph *S){int i;for(i=0;i<S->Vnum;i++){BfsVist[i] = 0;//初始化标记符 }for(i=0;i<S->Vnum;i++){if(BfsVist[i]==0)BFS(S,i);}}1234567891011121314151617181922232425262728293031323334353637383940414243444546474849505152535455565758596061626364

（6）全部代码

#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100//深度遍历标记数组 int DfsVist[MAXSIZE]; //广度遍历标记数组 int BfsVist[MAXSIZE];//边链表 typedef struct EdgeLink{int Local;//存放该顶点对应边链表中数据 struct EdgeLink *next;//边链表节点指针 }Edge,*ELINK;//顶点表 typedef struct VertexLink{int Vertex;//存放一条边链表对应的顶点 ELINK FirstNode;//指向该顶点对应边链表的头节点 }Vertex[MAXSIZE],*VLINK;//存放顶点和边，指向顶点表结构体数组 typedef struct MyGraph{int Vnum;//存放顶点数 int Enum;//存放边数 Vertex List;//边链表对应的顶点表中顶点结构体 }MyGraph;//创建边链表void CreateLink(MyGraph *T){int i,j;int v1,v2;ELINK p;//边链表指针 ELINK q;printf("请输入顶点数和边数(空格隔开):\n");scanf("%d%d",&(T->Vnum),&(T->Enum));//初始化顶点表结构体数组 for(i=0;i<T->Vnum;i++){printf("请输入第%d个顶点的信息:\n",i+1);scanf("%d",&(T->List[i].Vertex));//存放顶点在顶点表中 T->List[i].FirstNode = NULL; //让每个顶点表第一个指向边链表的指针为NULL }//打印顶点坐标和顶点表中顶点数据 printf("---------------------------\n"); for(i=0;i<T->Vnum;i++){printf("顶点下标为:%d 顶点数据为: %d\n",i,T->List[i].Vertex); }printf("---------------------------\n");//插入边链表数据for(i=0;i<T->Enum;i++){//因为顶点表为顺序表，所以要按顶点顺序输入相连边 printf("请输入两个连接顶点下标(空格隔开):\n");scanf("%d%d",&v1,&v2);getchar(); q = (ELINK)malloc(sizeof(Edge));//创建边链表节点，分配内存 q->Local = v2;//记录与该顶点连接边的顶点坐标q->next = NULL;//让尾巴指向NULL if(!T->List[v1].FirstNode){//判断是否为这个顶点第一个指向的数据 T->List[v1].FirstNode = q;}else{//这个顶点已经指向了一条边，以这条边为头节点，尾插法 p = T->List[v1].FirstNode;//临时存放头节点 while(p->next)//让节点指针遍历到尾巴上 {p = p->next;}p->next = q;//让新插的节点连接到之前边节点的尾巴上 }q = (ELINK)malloc(sizeof(Edge));//创建边链表节点，分配内存 q->Local = v1;//记录与该顶点连接边的顶点坐标q->next = NULL;//让尾巴指向NULL if(!T->List[v2].FirstNode){//判断是否为这个顶点第一个指向的数据 T->List[v2].FirstNode = q;}else{//这个顶点已经指向了一条边，以这条边为头节点，尾插法 p = T->List[v2].FirstNode;//临时存放头节点 while(p->next)//让节点指针遍历到尾巴上 {p = p->next;}p->next = q;//让新插的节点连接到之前边节点的尾巴上 }} }//打印邻接表 void PrintLink(MyGraph *S) {MyGraph *T = S;ELINK Q;//防止边链表指针指到NULL ，用临时指针代替遍历打印 int i;printf("打印邻接表结果如下:\n");for(i=0;i<T->Vnum;i++){Q = T->List[i].FirstNode;//接受每个顶点指向对应边链表的头节点指针 printf("%d--->",i);while(1){if(Q == NULL){putchar('\n');break;}printf("------->%3d",Q->Local);Q = Q->next;//！！BUG }}putchar('\n');}//*****************深度优先遍历算法—邻接表 *****************//void DFS_Link(MyGraph *T,int n){int i,j;ELINK q;//指向边链表节点指针 if(n<0 || n>=T->Vnum){printf("输入有误\n");return;}DfsVist[n] = 1;//遍历一个顶点，做下标记 1 printf(" %d",T->List[n].Vertex);q = T->List[n].FirstNode;//q指向下标为i所对顶点对应的边链表的第一个边结点while(q!=NULL){if(DfsVist[q->Local]!=1){j = q->Local;DFS_Link(T,j);} q = q->next;}} //初始化深度遍历—邻接表 void Init_DFSLINK(MyGraph *Q){int i;for(i=0;i<Q->Vnum;i++){DfsVist[i] = 0;}for(i=0;i<Q->Vnum;i++){if(!DfsVist[i]){DFS_Link(Q,i);//此顶点没有被标记，开始递归遍历}}putchar('\n'); }//广度遍历 void BFS(MyGraph *S,int t){ELINK P; //指向顶点所对应的边链表中 int i;int v;//用来接收边链表对应的顶点//为了不和广度搜素—邻接矩阵冲突//创建一个数组队列 int Queue[MAXSIZE];int front = 0;//队头 int rear = 0;//队尾 printf("%d ",S->List[t].Vertex);//输出当前遍历边链表的顶点 BfsVist[t] = 1;//将该顶点作标记rear = (rear+1)%MAXSIZE;//入队一个让队尾指向后移一位Queue[rear] = t; //将该顶点入队 while(front != rear)//若front == rear，表明这个顶点在边链表上连接的顶点已经遍历完毕 {front = (front+1)%MAXSIZE;//出队 v = Queue[front];//得到此时遍历到顶点坐标 P = S->List[v].FirstNode;//遍历当前顶点指向边链表中连接的其他顶点//也就是换个顶点的边链表继续遍历查找剩余顶点 while(P!=NULL){if(BfsVist[P->Local] == 0){printf("%d ",P->Local+1);//输出连接边顶点 BfsVist[P->Local] = 1;//作标记,表示这个顶点已经搜索过 rear = (rear+1)%MAXSIZE;//将该下标入队 Queue[rear] = P->Local;//把遍历到新的边链表对应的顶点坐标入队 }P = P->next;//遍历这个顶点的边链表 }} } //BFS广度遍历初始化void Init_BFS(MyGraph *S){int i;for(i=0;i<S->Vnum;i++){BfsVist[i] = 0;//初始化标记符 }for(i=0;i<S->Vnum;i++){if(BfsVist[i]==0)BFS(S,i);}} int main(){MyGraph *S;S = (MyGraph *)malloc(sizeof(MyGraph));//创建边链表 CreateLink(S);//打印边链表 PrintLink(S);//深度遍历Init_DFSLINK(S); //广度遍历 Init_BFS(S);return 0;}12345678910111213141516171819222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119111221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992000220320420520620720820921021121221321421521621721821921222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287

运行结果：

如果觉得《数据结构——无向图创建邻接表以及深度遍历广度遍历（C语言版）》对你有帮助，请点赞、收藏，并留下你的观点哦！

本内容不代表本网观点和政治立场，如有侵犯你的权益请联系我们处理。

网友评论

网友评论仅供其表达个人看法，并不表明网站立场。