图的操作算法详解

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

一.图

基础概念

  1. 有向图 - 图中每个边都有一个方向例如社交媒体网站上的关注关系图就是有向图。
  2. 无向图 - 图中每个边都没有方向例如朋友之间的相互认识关系图可以是无向图。
  3. 简单图 - 没有自环和重复边的无向图或有向图例如一张不允许两个人之间有多个好友关系的朋友关系图就是简单图。
  4. 多重图 - 允许存在重复边的无向图或有向图例如同一个用户在不同时间对同一篇文章进行多次评论的评论关系图就是多重图。
  5. 完全图 - 任意两个顶点之间都存在一条边的图例如五个节点的完全图就具有10条边。
  6. 子图 - 从原图中选取一部分节点和它们之间的边形成的图例如从一张社交网络上选取几个用户和他们之间的好友关系形成的子图。
  7. 连通图和联通分量 - 在无向图中如果任意两个节点之间都存在至少一条路径则该图为连通图。如果将连通图中所有连通的子图都提取出来得到的每个连通的子图称为联通分量。
  8. 强连通图 - 在有向图中如果任意两个节点之间都存在至少一条有向路径则该图为强连通图。
  9. 生成树 - 连通图中的一棵树它包含了原图中所有节点并且只有最少的边被保留例如一个城市的道路系统可以被看做是一张无向图其最小生成树表示了连接城市的最短路径。
  10. 度 - 节点拥有的边的数量对于无向图而言就是与该节点相邻的节点的数量对于有向图而言则分为入度和出度。
  11. 权和网 - 图中边具有的权重或者是节点之间的关联程度例如一个城市之间的距离可以被看做是一张加权无向图。
  12. 稠密图和稀疏图 - 用来描述图中边的数量相对于节点数量的性质如果边数接近节点数的平方那么图就是稠密图反之则为稀疏图。
  13. 路径和路径长度 - 从起始节点到结束节点所经过的边的序列称为路径路径上经过的边的数量称为路径长度。
  14. 距离 - 两个节点之间的最短路径长度。
  15. 回路 - 从起始节点到结束节点的路径且起始节点和结束节点是同一个节点。在无向图中也被称为环。

二.图的存储

1.邻接矩阵

邻接矩阵是一种用二维数组表示图的数据结构其中矩阵中的每个元素表示两个节点之间是否存在边。对于无向图而言邻接矩阵是对称的对于有向图而言则不一定对称。

在C语言中可以使用二维数组来实现邻接矩阵例如

#define MAX_NODES 100
int graph[MAX_NODES][MAX_NODES];

其中graph[i][j] 表示从节点 i 到节点 j 是否存在一条边。如果存在则该值为1否则为0。

2.邻接表

邻接表是由顶点和与之相连的边组成的链表在链表中存储了每个节点的邻居节点信息。对于稀疏图而言邻接表比邻接矩阵更加节省空间但查询某个节点的邻居节点需要遍历整个链表。

在C语言中可以使用结构体和指针来实现邻接表例如

#define MAX_NODES 100
struct AdjNode {
    int dest;
    struct AdjNode* next;
};
typedef struct AdjNode AdjNode;

struct Graph {
    AdjNode* adjLists[MAX_NODES];
};
typedef struct Graph Graph;

其中Graph 结构体包含了一个数组 adjLists每个元素都是一个指向 AdjNode 结构体的指针。在 AdjNode 结构体中dest 表示目标节点的编号next 则是指向下一个邻居节点的指针。

3.关联矩阵

关联矩阵是一种用二维数组表示图的数据结构其中矩阵中的每个元素表示一个顶点和一条边之间的关系。在关联矩阵中行代表顶点列代表边如果该顶点与该边相连则值为1否则为0。

在C语言中可以使用二维数组来实现关联矩阵例如

#define MAX_NODES 100
#define MAX_EDGES 200
int matrix[MAX_NODES][MAX_EDGES];

其中matrix[i][j] 表示顶点 i 是否与边 j 相连。如果相连则该值为1否则为0。

4.十字链表

十字链表是在邻接表的基础上进一步扩展的数据结构它可以表示有向图的结构同时避免了邻接表中查询源点和目标点的缺点。在十字链表中每个节点都有两个域分别指向以该节点为起点的出边和以该节点为终点的入边。

在C语言中可以使用结构体和指针来实现十字链表例如

#define MAX_NODES 100

struct Edge {
    int from;
    int to;
    struct Edge* nextOut;
    struct Edge* nextIn;
};
typedef struct Edge Edge;

struct Graph {
    Edge* edges[MAX_NODES];
};
typedef struct Graph Graph;

其中Graph 结构体包含了一个数组 edges每个元素都是一个指向 Edge 结构体的指针。在 Edge 结构体中from 表示边的起点to 表示边的终点nextOut 则是指向下一条以该节点为起点的出边的指针nextIn 则是指向下一条以该节点为终点的入边的指针。

5.前向星

前向星也是在邻接表的基础上进行扩展它可以同时支持有向图和无向图同时也解决了在邻接表中查询某个节点的所有出边或入边的效率问题。在前向星中每个节点不再只存储一个指向第一个邻居节点的指针而是存储一组指向所有邻居节点的指针这些指针按照一定的顺序排列成一个链表。

在C语言中可以使用结构体和数组来实现前向星例如

#define MAX_NODES 100
#define MAX_EDGES 200

struct Edge {
    int to;
    int weight; // 可选
    int next; // 指向下一条出边或入边
};
typedef struct Edge Edge;

struct Graph {
    Edge edges[MAX_EDGES];
    int head[MAX_NODES]; // 存储每个节点的第一条边的编号
    int edgeCount;
};
typedef struct Graph Graph;

其中Graph 结构体包含了两个数组edges 数组存储所有边的信息head 数组存储每个节点的第一条边的编号edgeCount 表示边的数量。在 Edge 结构体中to 表示边的终点weight 表示边的权值可选next 表示与该边起点相同的下一条边的编号。

6.邻接多重表

邻接多重表是一种用于表示无向图的数据结构它将每条边都存储为两个顶点之间的一条边并且对于每个节点存储所有与该节点相连的边的信息。在邻接多重表中每个节点都有一个指向第一条与该节点相连的边的指针而每条边则包含了指向其起点和终点下一条边的指针。

在C语言中可以使用结构体和指针来实现邻接多重表例如

#define MAX_NODES 100
#define MAX_EDGES 200

struct Edge {
    int from;
    int to;
    int nextFrom; // 指向起点相同的下一条边
    int nextTo; // 指向终点相同的下一条边
};
typedef struct Edge Edge;

struct Graph {
    Edge edges[MAX_EDGES];
    int head[MAX_NODES]; // 存储每个节点的第一条边的编号
    int edgeCount;
};
typedef struct Graph Graph;

其中Graph 结构体包含了两个数组edges 数组存储所有边的信息head 数组存储每个节点的第一条边的编号edgeCount 表示边的数量。在 Edge 结构体中from 和 to 分别表示边的起点和终点nextFrom 和 nextTo 则分别指向与该边起点相同和终点相同的下一条边的编号。

三.图的基本操作

在考研范围内需要掌握以下图的基本操作

  1. 创建图根据实际需求创建一个空的图数据结构并初始化各个节点和边的相关信息。
  2. 添加节点向图中添加一个新的节点并更新与该节点相连的所有边的信息。
  3. 添加边向图中添加一条新的边并更新相应节点的邻居节点列表。
  4. 删除节点从图中删除一个节点并将其所有与之相连的边移除。
  5. 删除边从图中删除一条边并更新相应节点的邻居节点列表。
  6. 查找节点查找图中是否包含某个特定的节点并返回其相关信息。
  7. 查找边查找图中是否包含某条特定的边并返回其相关信息。
  8. 遍历图遍历图中的所有节点和边以便进行进一步的分析和处理。
  9. 拓扑排序对有向无环图进行拓扑排序以确定所有节点的执行顺序。
  10. 最短路径计算两个节点之间的最短路径以便找到最优解决方案。
  11. 最小生成树寻找无向图的最小生成树以获得最小成本的连接方式。

四.核心功能实现

1.创建图

// 创建邻接矩阵表示的无向图
void CreateGraph(Graph *G) {
	int i, j, k, weight;
	
	printf("请输入图的顶点数和边数(用空格隔开): ");
	scanf("%d %d", &G->vertex_num, &G->edge_num);
	
	printf("请输入%d个顶点的信息: ", G->vertex_num);
	for (i = 0; i < G->vertex_num; ++i)
		scanf("%s", &G->vertex[i]);
	
	for (i = 0; i < G->vertex_num; ++i)
		for (j = 0; j < G->vertex_num; ++j)
			G->edge[i][j] = 0;  // 初始化邻接矩阵
	
	printf("请输入%d条边的信息(起点 终点 权值):\n", G->edge_num);
	for (k = 0; k < G->edge_num; ++k) {
		scanf("%d %d %d", &i, &j, &weight);
		// 因为是无向图所以需要对称赋值
		G->edge[i][j] = weight;
		G->edge[j][i] = weight;  
		//如果这里是创建有向图那么就需要我们应该会改
	}
}

2.插入顶点

// 在图G中插入顶点x
void InsertVertex(Graph *G, char x){
	if(G->vertex_num == MAX_VERTEX_NUM){  // 图已满
		printf("Error: 超出最大结点范围\n");
		return;
	}
	G->vertex[G->vertex_num] = x;
	G->vertex_num++;
	//更新边信息
	for(int i=0;i<G->vertex_num-1;++i){
		G->edge[i][G->vertex_num-1] = 0; //初始化新顶点的出边
		G->edge[G->vertex_num-1][i] = 0; //初始化新顶点的入边
	}
}

3.删除顶点

// 将数组中从 start 开始的元素向前移动一位
void moveArray(char arr[], int start, int end) {
	for (int i = start; i < end; ++i) {
		arr[i] = arr[i+1];
	}
}

// 在图G中删除顶点x
void DeleteVertex(Graph *G,char x){
	int n = -1;      //待删除结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果节点不存在
		printf("Error: 结点不存在\n");
		return;
	}
	// 删除该节点对应的行和列
	for(int i=n;i<G->vertex_num-1;++i){
		moveArray(G->vertex, i, G->vertex_num - 1); // 将后面的节点前移
		for(int j=0;j<G->vertex_num;++j){
			G->edge[i][j] = G->edge[i+1][j]; // 前移一位
			G->edge[j][i] = G->edge[j][i+1];
		}
	}
	G->vertex_num--;
	// 更新最后一行和最后一列
	for(int i=0;i<G->vertex_num;++i){
		G->edge[G->vertex_num][i] = 0; // 删除最后一列
		G->edge[i][G->vertex_num] = 0; // 删除最后一行
	}
}

4.求第一个邻接点

//求图G中顶点x的第一个邻接点
char FirstNeighbor(Graph *G,char x){
	int n = -1;      //待查询结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果查询节点不存在
		printf("Error: 结点不存在\n");
	}
	int count=0;
	int nx;        //第一个邻接点在数组里的下标
	//现在知道了他在第n个所以我们查询边矩阵第n行中第一个1在哪就知道第一个邻接点是谁
	for(int j=0;j<G->vertex_num;j++){
		if(G->edge[n][j]==1) count++;
		if(count==1){
			nx=j;
			break;
		}
	}
	return G->vertex[nx];
}

5.求其余邻接点

//返回图G中顶点x除顶点y的下一个邻接点
char NextNeighbor(Graph *G,char x,char y){
	int n = -1;      //待查询结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果查询节点不存在
		printf("Error: 结点不存在\n");
	}
	int count=0;
	int nx;   //存放返回邻接点数组下标
	for(int j=0;j<G->vertex_num;j++){
		if(G->edge[n][j]==1){
			if(G->vertex[j]!=y){
				j=nx;
			}
		}	
	}
	return G->vertex[nx];
}

6.判断边

//判断图G中x和y之间是否有边
int Adjacent(Graph *G,char x,char y){
	int n1,n2;   //分别存储x和y的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n1=i;
			break;
		}
	}
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n2=i;
			break;
		}
	}
	if(G->edge[n1][n2]==0 && G->edge[n2][n1]==0)
		return -1;
	else
		return 1;
}

以上部分均选取第三部分比较难 的算法进行实现

五.C语言完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTEX_NUM 20  // 最大顶点数

typedef struct {
	char vertex[MAX_VERTEX_NUM];  // 存放顶点信息
	int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  // 存放边信息
	int vertex_num;  // 顶点数
	int edge_num;  // 边数
} Graph;

// 创建邻接矩阵表示的无向图
void CreateGraph(Graph *G) {
	int i, j, k, weight;
	
	printf("请输入图的顶点数和边数(用空格隔开): ");
	scanf("%d %d", &G->vertex_num, &G->edge_num);
	
	printf("请输入%d个顶点的信息: ", G->vertex_num);
	for (i = 0; i < G->vertex_num; ++i)
		scanf("%s", &G->vertex[i]);
	
	for (i = 0; i < G->vertex_num; ++i)
		for (j = 0; j < G->vertex_num; ++j)
			G->edge[i][j] = 0;  // 初始化邻接矩阵
	
	printf("请输入%d条边的信息(起点 终点 权值):\n", G->edge_num);
	for (k = 0; k < G->edge_num; ++k) {
		scanf("%d %d %d", &i, &j, &weight);
		// 因为是无向图所以需要对称赋值
		G->edge[i][j] = weight;
		G->edge[j][i] = weight;  
		//如果这里是创建有向图那么就需要我们应该会改
	}
}

// 在图G中插入顶点x
void InsertVertex(Graph *G, char x){
	if(G->vertex_num == MAX_VERTEX_NUM){  // 图已满
		printf("Error: 超出最大结点范围\n");
		return;
	}
	G->vertex[G->vertex_num] = x;
	G->vertex_num++;
	//更新边信息
	for(int i=0;i<G->vertex_num-1;++i){
		G->edge[i][G->vertex_num-1] = 0; //初始化新顶点的出边
		G->edge[G->vertex_num-1][i] = 0; //初始化新顶点的入边
	}
}

// 将数组中从 start 开始的元素向前移动一位
void moveArray(char arr[], int start, int end) {
	for (int i = start; i < end; ++i) {
		arr[i] = arr[i+1];
	}
}

// 在图G中删除顶点x
void DeleteVertex(Graph *G,char x){
	int n = -1;      //待删除结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果节点不存在
		printf("Error: 结点不存在\n");
		return;
	}
	// 删除该节点对应的行和列
	for(int i=n;i<G->vertex_num-1;++i){
		moveArray(G->vertex, i, G->vertex_num - 1); // 将后面的节点前移
		for(int j=0;j<G->vertex_num;++j){
			G->edge[i][j] = G->edge[i+1][j]; // 前移一位
			G->edge[j][i] = G->edge[j][i+1];
		}
	}
	G->vertex_num--;
	// 更新最后一行和最后一列
	for(int i=0;i<G->vertex_num;++i){
		G->edge[G->vertex_num][i] = 0; // 删除最后一列
		G->edge[i][G->vertex_num] = 0; // 删除最后一行
	}
}

//求图G中顶点x的第一个邻接点
char FirstNeighbor(Graph *G,char x){
	int n = -1;      //待查询结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果查询节点不存在
		printf("Error: 结点不存在\n");
	}
	int count=0;
	int nx;        //第一个邻接点在数组里的下标
	//现在知道了他在第n个所以我们查询边矩阵第n行中第一个1在哪就知道第一个邻接点是谁
	for(int j=0;j<G->vertex_num;j++){
		if(G->edge[n][j]==1) count++;
		if(count==1){
			nx=j;
			break;
		}
	}
	return G->vertex[nx];
}

//返回图G中顶点x除顶点y的下一个邻接点
char NextNeighbor(Graph *G,char x,char y){
	int n = -1;      //待查询结点在数组里的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n=i;
			break;
		}
	}
	if(n == -1){  // 如果查询节点不存在
		printf("Error: 结点不存在\n");
	}
	int count=0;
	int nx;   //存放返回邻接点数组下标
	for(int j=0;j<G->vertex_num;j++){
		if(G->edge[n][j]==1){
			if(G->vertex[j]!=y){
				j=nx;
			}
		}	
	}
	return G->vertex[nx];
}

//判断图G中x和y之间是否有边
int Adjacent(Graph *G,char x,char y){
	int n1,n2;   //分别存储x和y的下标
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n1=i;
			break;
		}
	}
	for(int i=0;i<G->vertex_num;i++){
		if(G->vertex[i]==x) {
			n2=i;
			break;
		}
	}
	if(G->edge[n1][n2]==0 && G->edge[n2][n1]==0)
		return -1;
	else
		return 1;
}

int main() {
	Graph G;
	CreateGraph(&G);
	return 0;
}

六.运行结果

9HRC.jpg

刚好最近复习数据结构与算法顺便参加了英杰的新星计划这是本周第一篇投稿。

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：1. CSS的三大特性

下一篇：命令模式(十七)

“图的操作算法详解” 的相关文章

小白入门pwn笔记--elf文件概述1年前 (2023-02-02)
web项目部署上线（无虚拟主机，待学习）1年前 (2023-02-02)
微机原理与系统设计笔记1 | 绪论与数制表示1年前 (2023-02-02)
崔宝秋国际开源经验在小米开花 | 开源英雄1年前 (2023-02-02)
《RPC实战与核心原理》学习笔记Day71年前 (2023-02-02)
基于stm32的智能小车(远程控制、避障、循迹)_智能小车1年前 (2023-02-02)
第41讲：MySQL内置的QL性能分析工具1年前 (2023-02-02)
docker部署netcore项目1年前 (2023-02-02)
1.5万字长文：从 C# 入门 Kafka1年前 (2023-02-02)
OpenMP 线程同步 Construct 实现原理以及源码分析（下）1年前 (2023-02-02)

阿里云国际版