数据结构~17.图结构的操作

朱雀 2022-12-29 02:09 159阅读 0赞

# 数据结构~17.图结构的操作 #

## [本文是上一篇文章的后续,详情点击该链接~][Link 1] ##

上一章主要是理论,那么这一章直接进入实战

##### 创建结构体 #####

#define MaxNum 20 //图的最大顶点数
    #define MaxValue 65535 //最大值
    typedef struct { 
    	char Vertex[MaxNum];				//保存顶点信息
    	int GType;							//图的类型 0 无向图 1 有向图
    	int VertexNum;						//顶点的数量
    	int EdgeNum;						//边的数量
    	int EdgeWeight[MaxNum][MaxNum];		//保存边的权
    	int isTrav[MaxNum];					//遍历标志
    }GraphMatrix;							//定义邻接矩阵图结构

##### 初始化 #####

在创建图之前,先进行一个初始化操作。这样可以避免很多不必要的麻烦。就比如二维数组如果一开始没有给予初始值,就会在显示图的时候出现乱码。

预先给定顶点和边的数量,可以给后面的代码省去很多的事情。这种编码思想就比较类似于面向对象中的封装。尽管,C语言不是面向对象语言...

/* 初始化图结构 (顶点数量和边的长度) 并且给二维数组赋初始值以免出现错误 */
    GraphMatrix *initGraph(int verNum,int edgeNum) { 
    	int i,j;
    	//动态分配
    	GraphMatrix* GM = (GraphMatrix*)malloc(sizeof(GraphMatrix));
    	//判断 如果不合法就给最大值
    	if (verNum > MaxNum) { 
    		verNum = 20;
    	}
    	GM->VertexNum = verNum;
    	GM->EdgeNum = edgeNum;
    	//给二维数组赋初始值
    	for (i = 0; i < MaxNum; i++) { 
    		for (j = 0; j < MaxNum; j++) { 
    			GM->EdgeWeight[i][j] = 0;
    		}
    	}
    	return GM;
    }

##### 创建图 #####

这里为了方便,我就直接把边的起点和终点还有权重放在三个数组里面相对应。然而事实上还可以将这个封装做的更好。但是这里仅仅只是为了描述图这种数据结构,所以就先这样写。

/* 创建邻接矩阵图 vertex 图结构中顶点的集合 EdgeStart 边的起点集合 EdgeEnd 边的终点集合 weight 权的集合 总之也是相对应 */
    void CreateGraph(GraphMatrix* GM, char* vertex, char* EdgeStart,char *EdgeEnd,int* weight) { 
    	// i 和 j 到后面用来找到起始点和终点 k 就用来循环
    	int i, j, k;
    	int weiInd = 0;						//权坐标
    	char start, end;				//边的起点和终点
    	//保存顶点信息 
    	for (i = 0; i < GM->VertexNum; i++) { 
    		GM->Vertex[i] = vertex[i];
    	}
    	//输入边的信息 
    	for (k = 0; k < GM->EdgeNum; k++) { 
    		//赋值给起点和终点
    		start = EdgeStart[k];
    		end = EdgeEnd[k];
    		//在已有的顶点中找到起始点 i 就是那个坐标
    		for (i = 0; start != GM->Vertex[i]; i++);
    		//在已有的顶点中找到终点 j 就是那个坐标
    		for (j = 0; end != GM->Vertex[j]; j++);
    		//判断图的类型
    		if (GM->GType == 1) { 
    			//对应位置保存权值 表示有一条边
    			GM->EdgeWeight[i][j] = weight[weiInd++];
    		}
    		//如果是无向图 就在对角位置保存权值
    		else { 
    			GM->EdgeWeight[j][i] = weight[weiInd++];
    		}
    	}
    }

##### 创建的调用过程 #####

//顶点
    	char vertex[] = { 'A','B','C','D','E','F'};
    	//边的起始
    	char start[] = {  'A','A','D','D','D','C','C','F'};
    	//边的终点
    	char end[] = {  'B','F','B','A','F','D','E','E'};
    	//权
    	int weight[] = { 1,2,3,4,5,6,7,8};
    	//初始化
    	GraphMatrix *GM = initGraph(6,8);
    	//创建图
    	CreateGraph(GM,vertex,start,end,weight);

##### 显示图(输出邻接矩阵) #####

这个需求还算简单,直接把二维数组输出出来就行。由于前面做了初始化,所以这里就不会再出现乱码。

void OutGraph(GraphMatrix *GM) { 
    	//先输出顶点信息
    	int i, j;
    	printf("图的顶点信息如下:\n");
    	for (i = 0; i < GM->VertexNum; i++) { 
    		printf("\t%c",GM->Vertex[i]);
    	}printf("\n");
    	//输出矩阵
    	for (i = 0; i < GM->VertexNum; i++) { 
    		printf("%c", GM->Vertex[i]);
    		for (j = 0; j < GM->VertexNum; j++) { 
    			//如果说权值是最大值
    			if (GM->EdgeWeight[i][j] == MaxValue) { 
    				//显示无穷大
    				printf("\tmax");
    			}
    			//否则直接输出边的权值
    			else { 
    				printf("\t%d",GM->EdgeWeight[i][j]);
    			}
    		}
    		printf("\n");
    	}
    }

## 图的遍历 ##

遍历图,其实就是逐个访问图中所有访问的顶点。由于图的结构复杂,存在多对多的特点。所以如果我们顺着一个路径访问某顶点的时候,可能还会顺着另一个路径返回该顶点。

如果说同一个顶点总是被多次访问。那肯定是会浪费大量的时间,所以这样遍历的效率就会特别低。

为了避免这种情况发生,所以刚刚定义结构体的时候就设置了一个数组 isTrav\[n\]。这个数组的每个元素初始值是0。当某个顶点被遍历访问之后,那么设置的数据元素值就为1。在访问某个顶点 i 的时候就会先判断数组isTrav\[i\]的值，如果这个值是1那就表示访问过，则继续路径的下一个顶点。如果是0就访问,然后再访问下一个顶点。

### 深度优先遍历 ###

void DeepTraOne(GraphMatrix *GH, int n) { 
    	int j;
    	//标记该节点已经处理过
    	GH->isTrav[n] = 1;
    	//输出结点数据
    	printf("%c ", GH->Vertex[n]);
    	//添加处理结点的操作
    	for (j = 0; j < GH->VertexNum; j++) { 
    		//进行递归遍历
    		if (GH->EdgeWeight[n][j] != MaxValue && ! GH->isTrav[n]) { 
    			DeepTraOne(GH,j);
    		}
    	}
    }
    void DeepTraGraph(GraphMatrix *GH) { 
    	int i;
    	//清除各顶点遍历标志
    	for (i = 0; i < GH->VertexNum; i++) { 
    		GH->isTrav[i] = 0;
    	}
    	//开始遍历
    	for (i = 0; i < GH->VertexNum; i++) { 
    		//若该结点未遍历
    		if (!GH->isTrav[i]) { 
    			//调用函数遍历
    			DeepTraOne(GH,i);
    		}
    	}
    }

## 完整代码 ##

#include<stdio.h>
    #include<stdlib.h>
    #define MaxNum 20 //图的最大顶点数
    #define MaxValue 65535 //最大值
    typedef struct { 
    	char Vertex[MaxNum];				//保存顶点信息
    	int GType;							//图的类型 0 无向图 1 有向图
    	int VertexNum;						//顶点的数量
    	int EdgeNum;						//边的数量
    	int EdgeWeight[MaxNum][MaxNum];		//保存边的权
    	int isTrav[MaxNum];					//遍历标志
    }GraphMatrix;							//定义邻接矩阵图结构
    /* 初始化图结构 (顶点数量和边的长度) 并且给二维数组赋初始值以免出现错误 */
    GraphMatrix *initGraph(int verNum,int edgeNum) { 
    	int i,j;
    	//动态分配
    	GraphMatrix* GM = (GraphMatrix*)malloc(sizeof(GraphMatrix));
    	//判断 如果不合法就给最大值
    	if (verNum > MaxNum) { 
    		verNum = 20;
    	}
    	GM->VertexNum = verNum;
    	GM->EdgeNum = edgeNum;
    	//给二维数组赋初始值
    	for (i = 0; i < MaxNum; i++) { 
    		for (j = 0; j < MaxNum; j++) { 
    			GM->EdgeWeight[i][j] = 0;
    		}
    	}
    	return GM;
    }
    /* 创建邻接矩阵图 vertex 图结构中顶点的集合 EdgeStart 边的起点集合 EdgeEnd 边的终点集合 weight 权的集合 总之也是相对应 */
    void CreateGraph(GraphMatrix* GM, char* vertex, char* EdgeStart,char *EdgeEnd,int* weight) { 
    	// i 和 j 到后面用来找到起始点和终点 k 就用来循环
    	int i, j, k;
    	int weiInd = 0;						//权坐标
    	char start, end;				//边的起点和终点
    	//保存顶点信息 
    	for (i = 0; i < GM->VertexNum; i++) { 
    		GM->Vertex[i] = vertex[i];
    	}
    	//输入边的信息 
    	for (k = 0; k < GM->EdgeNum; k++) { 
    		//赋值给起点和终点
    		start = EdgeStart[k];
    		end = EdgeEnd[k];
    		//在已有的顶点中找到起始点 i 就是那个坐标
    		for (i = 0; start != GM->Vertex[i]; i++);
    		//在已有的顶点中找到终点 j 就是那个坐标
    		for (j = 0; end != GM->Vertex[j]; j++);
    		//判断图的类型
    		if (GM->GType == 1) { 
    			//对应位置保存权值 表示有一条边
    			GM->EdgeWeight[i][j] = weight[weiInd++];
    		}
    		//如果是无向图 就在对角位置保存权值
    		else { 
    			GM->EdgeWeight[j][i] = weight[weiInd++];
    		}
    	}
    }
    /* 清空图 */
    void ClearGraph(GraphMatrix *GM) { 
    	int i, j;
    	for (i = 0; i < GM->VertexNum; i++) { 
    		for (j = 0; j < GM->VertexNum; j++) { 
    			GM->EdgeWeight[i][j] = MaxValue;
    		}
    	}
    }
    
    /* 显示图 输出邻接矩阵 */
    void OutGraph(GraphMatrix *GM) { 
    	//先输出顶点信息
    	int i, j;
    	printf("图的顶点信息如下:\n");
    	for (i = 0; i < GM->VertexNum; i++) { 
    		printf("\t%c",GM->Vertex[i]);
    	}printf("\n");
    	//输出矩阵
    	for (i = 0; i < GM->VertexNum; i++) { 
    		printf("%c", GM->Vertex[i]);
    		for (j = 0; j < GM->VertexNum; j++) { 
    			//如果说权值是最大值
    			if (GM->EdgeWeight[i][j] == MaxValue) { 
    				//显示无穷大
    				printf("\tmax");
    			}
    			//否则直接输出边的权值
    			else { 
    				printf("\t%d",GM->EdgeWeight[i][j]);
    			}
    		}
    		printf("\n");
    	}
    }
    /* 深度优先遍历 */
    void DeepTraOne(GraphMatrix *GH, int n) { 
    	int j;
    	//标记该节点已经处理过
    	GH->isTrav[n] = 1;
    	//输出结点数据
    	printf("%c ", GH->Vertex[n]);
    	//添加处理结点的操作
    	for (j = 0; j < GH->VertexNum; j++) { 
    		//进行递归遍历
    		if (GH->EdgeWeight[n][j] != MaxValue && ! GH->isTrav[n]) { 
    			DeepTraOne(GH,j);
    		}
    	}
    }
    void DeepTraGraph(GraphMatrix *GH) { 
    	int i;
    	//清除各顶点遍历标志
    	for (i = 0; i < GH->VertexNum; i++) { 
    		GH->isTrav[i] = 0;
    	}
    	//开始遍历
    	for (i = 0; i < GH->VertexNum; i++) { 
    		//若该结点未遍历
    		if (!GH->isTrav[i]) { 
    			//调用函数遍历
    			DeepTraOne(GH,i);
    		}
    	}
    }
    
    int main(int argc,char *argv[]) { 
    	//顶点
    	char vertex[] = { 'A','B','C','D','E','F'};
    	//边的起始
    	char start[] = {  'A','A','D','D','D','C','C','F'};
    	//边的终点
    	char end[] = {  'B','F','B','A','F','D','E','E'};
    	//权
    	int weight[] = { 1,2,3,4,5,6,7,8};
    	//初始化
    	GraphMatrix *GM = initGraph(6,8);
    	//创建图
    	CreateGraph(GM,vertex,start,end,weight);
    	//显示图
    	OutGraph(GM);
    	//遍历图
    	printf("\n遍历图:\n");
    	DeepTraGraph(GM);
    	return 0;
    }

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/107977148