数据结构——图的基本操作
文章目录
- 1.图
- 2.图的结构体定义
- 3.图的初始化
- 4.添加顶点、删除顶点
- 4.1添加顶点
- 4.2删除顶点
- 5.添加边、删除边
- 5.1添加边
- 5.2删除边
- 6.打印图
- 7.main函数
在生命旅途中，我们就像是一个个节点，被无数看不见的边相连。每一次的相识与相离，都在这张巨大的网络图中留下独特的印记。
1.图
图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。我们可以将图 G 抽象地表示为一组顶点 V 和一组边 E 的集合。
接下来，我将使用C语言基于邻接矩阵来构建这张图
2.图的结构体定义
邻接矩阵是一种用于表示图中顶点之间关系的二维数组。在您提供的结构体定义中，GraphAdjMat 包含了三个成员：vertices、adjMat 和 size。以下是如何使用这个结构体来表示图的简要说明：
-
顶点数组
vertices：- 这是一个一维数组，用于存储图中的顶点信息。每个元素对应一个顶点，可以存储顶点的标识符或其他相关信息。
-
邻接矩阵
adjMat：- 这是一个二维数组，用于表示图中顶点之间的连接关系。
adjMat[i][j]表示顶点i和顶点j之间的边的信息。通常，如果顶点i和顶点j之间有边，则adjMat[i][j]会被设置为1（或边的权重，如果是加权图的话），如果没有边，则设置为0。
- 这是一个二维数组，用于表示图中顶点之间的连接关系。
-
顶点数量
size：- 这是一个整数，表示图中当前的顶点数量。这个值用于在操作图时，知道邻接矩阵中哪些行和列是有效的。
/*
* @brief 使用邻接矩阵来实现图
* @Max_Size 图中最大顶点数量
* @param vertices 顶点数组
* @param adjMat 邻接矩阵
* @param size 图中顶点的数量
*/
# define Max_Size 255
typedef struct
{
int vertices[Max_Size];
int adjMat[Max_Size][Max_Size];
int size;
}GraphAdjMat;
3.图的初始化
函数 CreateGraph 的功能是创建并初始化一个图结构，使用邻接矩阵来表示这个图。具体来说，这个函数执行以下操作：
- 动态分配内存：为
GraphAdjMat结构体分配一块内存空间。 - 检查内存分配：如果内存分配失败，则返回
NULL。 - 初始化邻接矩阵：将邻接矩阵中的所有元素设置为0，表示图中没有边。
- 设置顶点数量：将图中的顶点数量
size设置为0，表示图是空的。 - 返回图结构：返回一个指向新创建并初始化的图结构的指针。
简而言之，CreateGraph 函数用于创建一个空的图，并准备好用于后续添加顶点和边的操作。
/*
* @brief 图的初始化
* @param 无
* @return 初始化后的图
*/GraphAdjMat *CreateGraph()
{
//为图创建存储空间
GraphAdjMat *graph = (GraphAdjMat *)malloc(sizeof(GraphAdjMat));
//如果内存分配失败，返回空值
if (graph == NULL)
{
return NULL;
}
//将邻接矩阵初始化为0
for (int i = 0; i < Max_Size; i++)
{
for (int j = 0; j < Max_Size; j++)
{
graph->adjMat[i][j] = 0;
}
}
//将图顶点数置0
graph->size = 0;
return graph;
}
4.添加顶点、删除顶点
4.1添加顶点
函数 addVertice 的功能是向图结构中添加一个新的顶点。以下是这个函数的简要说明：
-
参数检查：函数首先检查图中是否还有空间添加新的顶点。如果
graph->size已经等于Max_Size，即图中顶点数已达到最大值，函数将打印一条消息并返回，不执行添加操作。 -
添加顶点：如果图中还有空间，函数将新顶点的值
val添加到graph->vertices数组的当前size索引处，这个索引对应于图中的下一个空位置。 -
更新邻接矩阵：对于新添加的顶点，函数需要更新邻接矩阵。它遍历所有已存在的顶点，并设置新顶点与这些顶点之间的连接状态为0（表示没有边）。这是通过设置
graph->adjMat[n][i]和graph->adjMat[i][n]来实现的，其中n是新顶点的索引。 -
增加顶点计数：最后，函数通过增加
graph->size的值来更新图中顶点的数量。
简而言之，addVertice 函数用于在图的 vertices 数组中添加一个新的顶点，并在邻接矩阵中为这个新顶点初始化与其他顶点之间的边的状态。
/*
* @brief 添加顶点
* @param graph 要添加顶点的图
* @param val 要添加的元素
* @return 无
*/void addVertice(GraphAdjMat *graph,int val)
{
//如果图满，退出程序
if (graph->size == Max_Size)
{
printf("图已满！\n");
return;
}
//添加第n个结点
int n = graph->size;
graph->vertices[n] = val;
//将第n个结点的行和列均置0
for (int i = 0; i < n; i++)
{
graph->adjMat[n][i] = graph->adjMat[i][n] = 0;
}
graph->size++;
}
4.2删除顶点
函数 deleteVertice 的功能是从图结构中删除指定索引位置的顶点。以下是这个函数的简要说明：
-
参数检查：函数首先检查传入的索引
index是否有效。如果索引小于0或大于等于图中顶点的数量graph->size，则表示索引越界，函数将打印一条错误消息并返回，不执行删除操作。 -
删除顶点：如果索引有效，函数将从
vertices数组中删除索引为index的顶点。这是通过将index位置及其后面的所有顶点向前移动一个位置来实现的。 -
删除邻接矩阵中的行：对于邻接矩阵中索引为
index的行，函数将该行及其后面的所有行向前移动一个位置，以删除对应的行。 -
删除邻接矩阵中的列：对于邻接矩阵中索引为
index的列，函数将该列及其后面的所有列向前移动一个位置，以删除对应的列。 -
更新顶点计数：最后，函数通过减少
graph->size的值来更新图中顶点的数量。
简而言之，deleteVertice 函数用于从图中删除指定索引的顶点，并相应地更新 vertices 数组和邻接矩阵，以保持图的一致性。
/*
* @brief 删除顶点
* @param graph 图
* @param index 删除顶点的索引
* @return 无
*/void deleteVertice(GraphAdjMat *graph,int index)
{
//处理索引越界的情况
if (index <0 || index >= graph->size)
{
printf("索引越界！\n");
return;
}
//将顶点删除
for (int i = index; i < graph->size - 1;i++)
{
graph->vertices[i] = graph->vertices[i + 1];
}
//删除行
for (int i = index; i < graph->size -1;i++)
{
for (int j = 0; j < graph->size; j++)
{
graph->adjMat[i][j] = graph->adjMat[i + 1][j];
}
}
//删除列
for (int i = 0; i < graph->size; i++)
{
for (int j = index; j < graph->size - 1;j++)
{
graph->adjMat[i][j] = graph->adjMat[i][j + 1];
}
}
//顶点个数减1
graph->size--;
}
5.添加边、删除边
5.1添加边
函数 addEdge 的功能是向图中添加一条边，连接两个指定索引的顶点。以下是这个函数的简要说明：
-
参数检查：函数首先检查传入的两个索引
index1和index2是否有效。如果任一索引小于0或大于等于图中顶点的数量graph->size，则表示索引非法，函数将打印一条错误消息并返回，不执行添加边的操作。 -
添加边：如果两个索引都有效，函数将在邻接矩阵中设置
index1和index2之间的连接状态。具体来说，它将graph->adjMat[index1][index2]和graph->adjMat[index2][index1]都设置为1。这表示在顶点index1和顶点index2之间添加了一条双向连接的边。
简而言之，addEdge 函数用于在图中添加一条无向边，连接两个指定索引的顶点，并在邻接矩阵中相应地更新这两个顶点之间的连接状态。
/*
* @brief 添加边
* @param graph * @param index1 index2 要添加的两个边在vertics中的索引
* @return 无
*/void addEdge(GraphAdjMat *graph,int index1,int index2)
{
if (index1 < 0 || index1 >= graph->size || index2 < 0 || index2 >= graph->size)
{
printf("索引非法\n");
return;
}
//添加边
graph->adjMat[index1][index2] = 1;
graph->adjMat[index2][index1] = 1;
}
5.2删除边
函数 deleteEdge 的功能是从图中删除连接两个指定索引顶点之间的边。以下是这个函数的简要说明：
-
参数检查：函数首先检查传入的两个索引
index1和index2是否有效。如果任一索引小于0或大于等于图中顶点的数量graph->size，则表示索引非法，函数将打印一条错误消息并返回，不执行删除边的操作。 -
删除边：如果两个索引都有效，函数将在邻接矩阵中将
index1和index2之间的连接状态设置为0。具体来说，它将graph->adjMat[index1][index2]和graph->adjMat[index2][index1]都设置为0。这表示在顶点index1和顶点index2之间删除了一条双向连接的边。
简而言之，deleteEdge 函数用于在图中删除一条无向边，该边连接两个指定索引的顶点，并在邻接矩阵中相应地更新这两个顶点之间的连接状态。
/*
* @brief 删除边
* @param graph 图
* @param index1,index2 要删除的两个顶点之间的边在vertices中的索引
*/void deleteEdge(GraphAdjMat *graph, int index1, int index2)
{
if (index1 < 0 || index1 >= graph->size || index2 < 0 || index2 >= graph->size)
{
printf("索引非法\n");
return;
}
//添加边
graph->adjMat[index1][index2] = 0;
graph->adjMat[index2][index1] = 0;
}
6.打印图
/*
* @brief 打印邻接矩阵
* @param graph 图
* @return 无
*/void printGraph(GraphAdjMat *graph)
{
//输出顶点
for (int i = 0; i < graph->size; i++)
{
printf("%d ",graph->vertices[i]);
}
printf("\n");
//打印边
for (int i = 0; i < graph->size; i++)
{
for (int j = 0; j < graph->size; j++)
{
printf("%d ",graph->adjMat[i][j]);
}
printf("\n");
}
}
7.main函数
int main(void)
{
GraphAdjMat *graph = CreateGraph();
//添加顶点
int arr[] = {1,2,3,4,5,6,7,8,9};
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
addVertice(graph,arr[i]);
}
//添加边
/*
* 1 2 3 * 4 5 6 * 7 8 9 */ addEdge(graph,0,1);
addEdge(graph,1,2);
addEdge(graph,0,3);
addEdge(graph,1,4);
addEdge(graph,2,5);
addEdge(graph,3,4);
addEdge(graph,4,5);
addEdge(graph,3,6);
addEdge(graph,4,7);
addEdge(graph,5,8);
addEdge(graph,6,7);
addEdge(graph,7,8);
//打印图
printGraph(graph);
return 0;
}
输出：
D:\develop\Ccode\Data_Structure_Learn\Map\cmake-build-debug\Map.exe
1 2 3 4 5 6 7 8 9
0 1 0 1 0 0 0 0 0
1 0 1 0 1 0 0 0 0
0 1 0 0 0 1 0 0 0
1 0 0 0 1 0 1 0 0
0 1 0 1 0 1 0 1 0
0 0 1 0 1 0 0 0 1
0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 1 0 1
0 0 0 0 0 1 0 1 0
Process finished with exit code 0