数据结构——图的基本操作

在生命旅途中，我们就像是一个个节点，被无数看不见的边相连。每一次的相识与相离，都在这张巨大的网络图中留下独特的印记。

1.图

图（graph）是一种非线性数据结构，由顶点（vertex）和边（edge）组成。我们可以将图 G 抽象地表示为一组顶点 V 和一组边 E 的集合。

接下来，我将使用C语言基于邻接矩阵来构建这张图

2.图的结构体定义

邻接矩阵是一种用于表示图中顶点之间关系的二维数组。在您提供的结构体定义中，GraphAdjMat 包含了三个成员：vertices、adjMat 和 size。以下是如何使用这个结构体来表示图的简要说明：

1. 顶点数组 vertices：

   • 这是一个一维数组，用于存储图中的顶点信息。每个元素对应一个顶点，可以存储顶点的标识符或其他相关信息。

2. 邻接矩阵 adjMat：

   • 这是一个二维数组，用于表示图中顶点之间的连接关系。adjMat[i][j] 表示顶点 i 和顶点 j 之间的边的信息。通常，如果顶点 i 和顶点 j 之间有边，则 adjMat[i][j] 会被设置为1（或边的权重，如果是加权图的话），如果没有边，则设置为0。

3. 顶点数量 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 的功能是创建并初始化一个图结构，使用邻接矩阵来表示这个图。具体来说，这个函数执行以下操作：

1. 动态分配内存：为 GraphAdjMat 结构体分配一块内存空间。
2. 检查内存分配：如果内存分配失败，则返回 NULL。
3. 初始化邻接矩阵：将邻接矩阵中的所有元素设置为0，表示图中没有边。
4. 设置顶点数量：将图中的顶点数量 size 设置为0，表示图是空的。
5. 返回图结构：返回一个指向新创建并初始化的图结构的指针。

简而言之，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 的功能是向图结构中添加一个新的顶点。以下是这个函数的简要说明：

1. 参数检查：函数首先检查图中是否还有空间添加新的顶点。如果 graph->size 已经等于 Max_Size，即图中顶点数已达到最大值，函数将打印一条消息并返回，不执行添加操作。

2. 添加顶点：如果图中还有空间，函数将新顶点的值 val 添加到 graph->vertices 数组的当前 size 索引处，这个索引对应于图中的下一个空位置。

3. 更新邻接矩阵：对于新添加的顶点，函数需要更新邻接矩阵。它遍历所有已存在的顶点，并设置新顶点与这些顶点之间的连接状态为0（表示没有边）。这是通过设置 graph->adjMat[n][i] 和 graph->adjMat[i][n] 来实现的，其中 n 是新顶点的索引。

4. 增加顶点计数：最后，函数通过增加 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 的功能是从图结构中删除指定索引位置的顶点。以下是这个函数的简要说明：

1. 参数检查：函数首先检查传入的索引 index 是否有效。如果索引小于0或大于等于图中顶点的数量 graph->size，则表示索引越界，函数将打印一条错误消息并返回，不执行删除操作。

2. 删除顶点：如果索引有效，函数将从 vertices 数组中删除索引为 index 的顶点。这是通过将 index 位置及其后面的所有顶点向前移动一个位置来实现的。

3. 删除邻接矩阵中的行：对于邻接矩阵中索引为 index 的行，函数将该行及其后面的所有行向前移动一个位置，以删除对应的行。

4. 删除邻接矩阵中的列：对于邻接矩阵中索引为 index 的列，函数将该列及其后面的所有列向前移动一个位置，以删除对应的列。

5. 更新顶点计数：最后，函数通过减少 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 的功能是向图中添加一条边，连接两个指定索引的顶点。以下是这个函数的简要说明：

1. 参数检查：函数首先检查传入的两个索引 index1 和 index2 是否有效。如果任一索引小于0或大于等于图中顶点的数量 graph->size，则表示索引非法，函数将打印一条错误消息并返回，不执行添加边的操作。

2. 添加边：如果两个索引都有效，函数将在邻接矩阵中设置 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 的功能是从图中删除连接两个指定索引顶点之间的边。以下是这个函数的简要说明：

1. 参数检查：函数首先检查传入的两个索引 index1 和 index2 是否有效。如果任一索引小于0或大于等于图中顶点的数量 graph->size，则表示索引非法，函数将打印一条错误消息并返回，不执行删除边的操作。

2. 删除边：如果两个索引都有效，函数将在邻接矩阵中将 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 0Process finished with exit code 0