投稿
  1. 首页
  2. 随笔

数据结构无向图的 *** 作（C语言）

刷机大师下载 • 2022-12-16 • 随笔 • 阅读 64

数据结构无向图的 *** 作（C语言）,第1张

数据结构无向图的 *** 作（C语言）

目录

//1、含邻接矩阵的图结构

//2、创建邻接矩阵

//3、打印邻接矩阵

//4、邻接表的图结构

//5、创建邻接表

//6、打印邻接表

//7、深度优先搜索

//8、广度优先搜索

//9、带主函数完整测试源码

//1、含邻接矩阵的图结构

用邻接矩阵来表示图：

//定义邻接矩阵的图结构
typedef struct graph {
	elemtype data[N + 1];//存放顶点，不使用data[0]存放
	int side[N + 1][N + 1];//邻接矩阵，同上
}graph;
//2、创建邻接矩阵

邻接矩阵是用来表示边的，0表示没有边，1表示有边，值为1的数组下标分别为边的起始和结尾序号：

//创建邻接矩阵
void Create1(graph* g,int sum) {
	int i, j;
	//初始化矩阵;
	for (i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			g->side[i][j] = 0;//0表示没有边，1表示右边
		}
	}
	//输入边的信息
	printf("分别输入%d条边的始尾：n",sum);
	for (int k = 1; k <= sum; k++) {
		scanf("%d %d", &i, &j);
		g->side[i][j] = 1;//无向图的边是双向的
		g->side[j][i] = 1;
	}
}
//3、打印邻接矩阵 
//打印邻接矩阵
void Print1(graph g) {
	for (int i = 1; i <= N; i++) {//控制行
		for (int j = 1; j <= N; j++) {//控制列
			printf("%d ", g.side[i][j]);
		}
		printf("n");//换行
	}
}
//4、邻接表的图结构 
//定义邻接表结构
typedef struct linkgraph {
	elemtype data;//顶点值
	int index;//下标值
	struct linkgraph* next;//邻接点
}*linkgraph;
//5、创建邻接表

先把每个顶点给放在一个数组里，然后把各顶点的邻接点以链表形式连在其后：

//创建邻接表
void Create2(linkgraph arr[],graph* g) {//arr是邻接表的顶点数组，g是图
	//先存放每个顶点的值和序号
	for (int i = 1; i <= N; i++) {
		arr[i] = (linkgraph)malloc(sizeof(struct linkgraph));//不初始化就报错
		arr[i]->data = g->data[i];//先存顶点
		arr[i]->index = i;//给每个顶点排号
		arr[i]->next = NULL;//因为还不知道该顶点的邻接点是谁所以给空
	}
	//然后输入边
	int i, j, sum;
	linkgraph new;//新的邻接表结点，用来连接邻接点
	printf("输入边的条数：");
	scanf("%d", &sum);
	if (sum > E)
		printf("输入错误！");
	else {
		printf("分别输入%d条边的始尾序号：n", sum);
		for (int k = 1; k <= sum; k++) {
			scanf("%d %d", &i, &j);//输入边，也就是两个顶点的下标值
			new = (linkgraph)malloc(sizeof(struct linkgraph));
			new->index = j;//先给邻接点排号
			new->data=arr[j]->data;//再给新节点赋值让他去连上前一个顶点
			new->next = arr[i]->next;//这里是头插法，尾插法需要头节点
			arr[i]->next = new;//
			//无向图，所以两遍
			new = (linkgraph)malloc(sizeof(struct linkgraph));
			new->index = i;
			new->data = arr[i]->data;
			new->next = arr[j]->next;
			arr[j]->next = new;
		}
	}
}
//6、打印邻接表

打印出每个顶点和他的邻接点

//打印邻接表
void Print2(linkgraph arr[]) {
	printf("顶点--->邻接点n");
	for (int i = 1; i <= N; i++) {//控制顶点
		linkgraph p = arr[i];//这里主要是方便后面的书写
		printf("%c：t", p->data);
		while (p->next) {//这里循环退出时就代表他没有邻接点了
			p = p->next;//找到他 的邻接点
			printf("%c ", p->data);
		}
		printf("n");
	}
}
//7、深度优先搜索

深度优先就是一条路走到黑，用递归一直访问没有被访问过的顶点，直到把所有顶点都访问了：

//深度优先搜索
int visited[N + 1];//辅助数组，代表顶点的访问状态，访问过了为1，没访问为0
//先初始化这个辅助数组
void InitVisited() {
	for (int i = 1; i <= N; i++) {
		visited[i] = 0;
	}
}
void DFS(graph* g,int i) {
	printf("%c ", g->data[i]);
	visited[i] = 1;//标记被访问过了
	for (int j = 1; j <= N; j++) {
		if (g->side[i][j] && !visited[j])//判断两顶点是否存在边并且另一顶点是否被访问过了
			DFS(g, j);
	}
}
//8、广度优先搜索

广度优先类似于树的层序遍历：

//广度优先搜索
void BFS(graph* g, int i) {
	printf("%c ", g->data[i]);
	int Queue[N + 1];//辅助队列
	int front, rear;//队首队尾指针
	front = rear = 0;
	visited[i] = 1;//标记被访问过了
	Queue[++rear] = i;//入队，把顶点的下标值入队
	while (front < rear) {
		i = Queue[++front];//出队，找到当前顶点的下标值
		for (int j = 1; j <= N; j++) {
			if (g->side[i][j] && !visited[j]) {//判断两顶点是否存在边并且另一顶点是否被访问过了
				printf("%c ", g->data[j]);
				visited[j] = 1;//标记被访问过了
				Queue[++rear] = j;//入队，把顶点的下标值入队
			}
		}
	}
}
//9、带主函数完整测试源码 
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#define N 4//图的最大顶点数
#define E N*(N-1)/2//无向图的最大边数
#define elemtype char //顶点元素类型
#define max 32727
//无向图
//定义邻接矩阵的图结构
typedef struct graph {
	elemtype data[N + 1];//存放顶点，不使用data[0]存放
	int side[N + 1][N + 1];//邻接矩阵，同上
}graph;
//初始化顶点信息
void Init(graph* g) {
	//先存好顶点信息
	for (int i = 1; i <= N; i++) {
		scanf("%c", &g->data[i]);
		getchar();
	}
}
//创建邻接矩阵
void Create1(graph* g,int sum) {
	int i, j;
	//初始化矩阵;
	for (i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			g->side[i][j] = 0;//0表示没有边，1表示右边
		}
	}
	//输入边的信息
	printf("分别输入%d条边的始尾：n",sum);
	for (int k = 1; k <= sum; k++) {
		scanf("%d %d", &i, &j);
		g->side[i][j] = 1;//无向图的边是双向的
		g->side[j][i] = 1;
	}
}
//打印邻接矩阵
void Print1(graph g) {
	for (int i = 1; i <= N; i++) {//控制行
		for (int j = 1; j <= N; j++) {//控制列
			printf("%d ", g.side[i][j]);
		}
		printf("n");//换行
	}
}

//定义邻接表结构
typedef struct linkgraph {
	elemtype data;//顶点值
	int index;//下标值
	struct linkgraph* next;//邻接点
}*linkgraph;
//创建邻接表
void Create2(linkgraph arr[],graph* g) {//arr是邻接表的顶点数组，g是图
	//先存放每个顶点的值和序号
	for (int i = 1; i <= N; i++) {
		arr[i] = (linkgraph)malloc(sizeof(struct linkgraph));//不初始化就报错
		arr[i]->data = g->data[i];//先存顶点
		arr[i]->index = i;//给每个顶点排号
		arr[i]->next = NULL;//因为还不知道该顶点的邻接点是谁所以给空
	}
	//然后输入边
	int i, j, sum;
	linkgraph new;//新的邻接表结点，用来连接邻接点
	printf("输入边的条数：");
	scanf("%d", &sum);
	if (sum > E)
		printf("输入错误！");
	else {
		printf("分别输入%d条边的始尾序号：n", sum);
		for (int k = 1; k <= sum; k++) {
			scanf("%d %d", &i, &j);//输入边，也就是两个顶点的下标值
			new = (linkgraph)malloc(sizeof(struct linkgraph));
			new->index = j;//先给邻接点排号
			new->data=arr[j]->data;//再给新节点赋值让他去连上前一个顶点
			new->next = arr[i]->next;//这里是头插法，尾插法需要头节点
			arr[i]->next = new;//
			//无向图，所以两遍
			new = (linkgraph)malloc(sizeof(struct linkgraph));
			new->index = i;
			new->data = arr[i]->data;
			new->next = arr[j]->next;
			arr[j]->next = new;
		}
	}
}
//打印邻接表
void Print2(linkgraph arr[]) {
	printf("顶点--->邻接点n");
	for (int i = 1; i <= N; i++) {//控制顶点
		linkgraph p = arr[i];//这里主要是方便后面的书写
		printf("%c：t", p->data);
		while (p->next) {//这里循环退出时就代表他没有邻接点了
			p = p->next;//找到他 的邻接点
			printf("%c ", p->data);
		}
		printf("n");
	}
}
void menu() {
	printf("================n");
	printf("1、邻接矩阵n");
	printf("2、邻 接 表n");
	printf("================n");
}
//深度优先搜索
int visited[N + 1];//辅助数组，代表顶点的访问状态，访问过了为1，没访问为0
//先初始化这个辅助数组
void InitVisited() {
	for (int i = 1; i <= N; i++) {
		visited[i] = 0;
	}
}
void DFS(graph* g,int i) {
	printf("%c ", g->data[i]);
	visited[i] = 1;//标记被访问过了
	for (int j = 1; j <= N; j++) {
		if (g->side[i][j] && !visited[j])//判断两顶点是否存在边并且另一顶点是否被访问过了
			DFS(g, j);
	}
}
//广度优先搜索
void BFS(graph* g, int i) {
	printf("%c ", g->data[i]);
	int Queue[N + 1];//辅助队列
	int front, rear;//队首队尾指针
	front = rear = 0;
	visited[i] = 1;//标记被访问过了
	Queue[++rear] = i;//入队，把顶点的下标值入队
	while (front < rear) {
		i = Queue[++front];//出队，找到当前顶点的下标值
		for (int j = 1; j <= N; j++) {
			if (g->side[i][j] && !visited[j]) {//判断两顶点是否存在边并且另一顶点是否被访问过了
				printf("%c ", g->data[j]);
				visited[j] = 1;//标记被访问过了
				Queue[++rear] = j;//入队，把顶点的下标值入队
			}
		}
	}
}
int main(){
	int chose = 0;
	int start = 0;
	int sum = 0;//边的数目
	graph g;//创建一个无向图
	linkgraph arr[N + 1];//存放表头的数组,也就是存放每个结点的数组
	printf("输入%d个顶点信息：", N);
	Init(&g);//初始化顶点
	while (1) {
		menu();
		scanf("%d", &chose);
		switch (chose) {
		case 1:
			printf("输入边的条数：");
			scanf("%d", &sum);
			Create1(&g,sum);//创建矩阵
			Print1(g);//打印邻接矩阵
			InitVisited();
			printf("输入起点序号：");
			scanf("%d", &start);
			printf("深度优先搜索遍历：n");
			DFS(&g, start);
			printf("n");
			printf("广度优先搜索遍历：n");
			InitVisited();
			BFS(&g, start);
			printf("n");
			break;
		case 2:
			Create2(arr,&g);//创建邻接表
			Print2(arr);
			break;
		default:return 0;
		}
	}
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5636080.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
刷机大师下载 刷机大师下载 一级用户组
0 0
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表（0条）

保存