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

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

一、邻接表概念

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

  1. 对无向图的每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图则是以顶点vi为尾的弧）。这个单链表就称为顶点vi的边表（对于有向图则称为出边表）
  2. 边表的头指针和顶点的数据信息采用顺序存储（称为顶点表）
  3. 邻接表中存在两种结点：顶点表结点和边表结点
  4. 顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成
  5. 边表（邻接表）结点由邻接点域（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;

（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;	//	让新插的节点连接到之前边节点的尾巴上 
		}	
	} 
}

（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');
}

（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'); 
}

（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);
	}	
}

（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;	
}

运行结果：
在这里插入图片描述


http://www.niftyadmin.cn/n/5377999.html

相关文章

Imgui(3) | 基于 imgui-SFML 的 mnist 数据集查看器

Imgui(3) | 基于 imgui-SFML 的 mnist 数据集查看器

Imgui(3) | 基于 imgui-SFML 的 mnist 数据集查看器 文章目录 Imgui(3) | 基于 imgui-SFML 的 mnist 数据集查看器0. 介绍1. 处理 mnist 数据集2. 显示单张图像和label2.1 显示单张图像2.2 点选列表后更新显示的图像2.3 显示 label2.4 使用完整的列表 总结 0. 介绍 把mnist数据…
阅读更多...
Docker安装和使用Redis

Docker安装和使用Redis

Docker安装和使用Redis 一、拉取 Redis 镜像二、根据镜像运行容器三、配置 Redis 密码1、进入 redis 容器内部2、使用 redis 命令行设置密码 一、拉取 Redis 镜像 docker pull redis二、根据镜像运行容器 docker run \ --name redis \-p 6379:6379 \-d \redis \redis-server …
阅读更多...
unity的重中之重：组件

unity的重中之重：组件

检查器&#xff08;Hierarchy&#xff09;面板中的所有东西都是组件。日后多数工作都是和组件打交道&#xff0c;包括调参、自定义脚本组件。 文章目录 12 游戏的灵魂&#xff0c;脚本组件13 玩转脚本组件14 尽职的一生&#xff0c;了解组件的生命周期15 不能插队&#xff01;…
阅读更多...
计算机设计大赛 深度学习YOLOv5车辆颜色识别检测 - python opencv

计算机设计大赛 深度学习YOLOv5车辆颜色识别检测 - python opencv

文章目录 1 前言2 实现效果3 CNN卷积神经网络4 Yolov56 数据集处理及模型训练5 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习YOLOv5车辆颜色识别检测 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0…
阅读更多...
安卓自定义画板

安卓自定义画板

包含功能&#xff1a; 包含 获取当前画板的截图、设置画笔样式、获取画笔样式、设置画笔宽度、获取画笔宽度、设置画笔颜色、获取画笔颜色、加载图片、获取图片位图对象、设置图片位图对象&#xff0c;并在画布上绘制图片、撤销上一步操作、重做上一步撤销的操作、清空所有绘图…
阅读更多...
@ 代码随想录算法训练营第7周（C语言）|Day42（动态规划）

@ 代码随想录算法训练营第7周（C语言）|Day42（动态规划）

代码随想录算法训练营第7周&#xff08;C语言&#xff09;|Day42&#xff08;动态规划&#xff09; Day42、动态规划&#xff08;包含题目 416. 分割等和子集 &#xff09; 416. 分割等和子集 题目描述 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集&…
阅读更多...
vue3-应用规模化-路由和状态

vue3-应用规模化-路由和状态

客户端 vs. 服务端路由 服务端路由指的是服务器根据用户访问的 URL 路径返回不同的响应结果。当我们在一个传统的服务端渲染的 web 应用中点击一个链接时&#xff0c;浏览器会从服务端获得全新的 HTML&#xff0c;然后重新加载整个页面。 然而&#xff0c;在单页面应用中&…
阅读更多...
ESP32学习（4）——电脑远程控制LED灯

ESP32学习（4）——电脑远程控制LED灯

1.思路梳理 首先需要让ESP32连接上WIFI 然后创建udp socket 接着接收udp数据 最后解析数据&#xff0c;控制LED 2.代码实现 import network from socket import * from machine import Pin p2Pin(2,Pin.OUT)def do_connect(): #连接wifi wlan network.WLAN(network.STA_IF)…
阅读更多...
最新文章

Copyright @ 2022~2023