图的存储结构

这个也就是怎么在内存中表示一张图

第一种方式：采用邻接矩阵来表示一张图

        简单来说就是，采用二个数组来表示一张图

                1.第一个数组：用一维数组来存储图中的顶点信息

                2.第二个数组：用二维数组存储图中的边与弧的信息

        先来说无向图的邻接矩阵表示方法：

        

                来说一下这个二维矩阵，横向与纵向都代表这个图中的顶点，这样做，有助于来分析两个顶点的关系，比如方向(v1,v2)这个就很符合二维数组arr[v1][v2]的一个表示，这个时候如果一张图是有向图，那么方向就是v1->v2,v1代表弧尾，v2代表弧头，也代表v1的出度，v2的入度，然后比如在一个图中，每一个顶点的编号是，不要说没有，你就算自己设置，也要设置为有编号 ，是从v0->v4,那么就表示在这个图中有四个顶点，然后我们就可以把v0设置为0这个位置，相对于后面的结点来说，v1就代表1,v2就代表2，依次类推

                上面那个分段函数的表达意思就是，如果(v1,v2)这条边属于E(G),那么也就是说，v1与v2存在一条边，对于无向图来说，不用考虑顺序，只需要把(v1,v2)设置为一个数值就好了，比如就把这个邻接矩阵这个位置的值设为1，表示两者有联系 ，另外还要说一点的就是，因为邻接矩阵是二维数组，在这个数组中除了考虑(v1,v2)这个位置之外，还要考虑一个位置(v2,v1)，这两个位置一个看横向，一个看纵向，因为对于无向图来说，这两个位置对应都是(v1,v2)这两个顶点的关系，所以，如果这两个顶点之间存在边，需要把这两个位置的值都设置为1。

        

         我们就来表示上面这张图的一种关系，下面直接上代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//最大顶点数
#define MAX_VERTEX 30
 
//定义图结构
typedef struct _graph
{
	//顶点数组，存储顶点名字
	char **vertex;
	//边的数组
	int edge[MAX_VERTEX][MAX_VERTEX];
	//顶点个数
	int vertex_num;
	//边的条数
	int edge_num;
}graph;
 
//算出用户输入的顶点在数组中的位置
//这里就是比如输入一个v1,v2,那么对于无向图来说，(v1,v2)与(v2,v1)都代表的是同一条边
int calc_vertex_pos(graph &g,char* v)
{
	//遍历顶点数组
	for(int i = 0;i < g.vertex_num;i++) {
		//这里相当于就是字符串比较
		if(strcmp(v,g.vertex[i]) == 0) {
			return i;//找到直接返回这个位置
		}
	}
	return -1;
}
 
//创建一个图
void create_graph(graph &g)
{
	printf("请输入图的顶点数目与边数目:顶点 边\n");
	scanf("%d %d",&g.vertex_num,&g.edge_num);
	printf("请输入%d个顶点值\n",g.vertex_num);
 
	//开始循环给顶点数组赋顶点值
	//在赋值之前需要在堆上开辟空间存放字符串
	g.vertex = (char**)malloc(sizeof(char*) * g.vertex_num);
	for(int i = 0;i < g.vertex_num;i++) {
		char str[100] = {0};
		scanf("%s",str);
		//这个数组又指向了分配的一个空间
		g.vertex[i] = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.vertex[i],str);
	}
	//把边的二维数组也给初始化一下
	//以顶点数n，形成一个n*n的二维数组
	for(int i = 0;i < g.vertex_num;i++) {
		for(int j = 0;j < g.vertex_num;j++) {
			//把对应的边全部初始化为0表示不存在
			g.edge[i][j] = 0;
		}
	}
 
	//上面二个数组内容给初始化好了
	//下面来设置边与边的关系，就是是否有边
	printf("请输入%d条边和与之对应的顶点1，顶点2\n",g.edge_num);
	//设置两个有边的顶点之间的关系
	char v1[10];
	char v2[10];
	//有多少条边，就对应了有多少个顶点
	for(int i = 0;i < g.edge_num;i++) {
		scanf("%s %s",v1,v2);
		//然后我们计算顶点在数组中的位置
		//是0啊，1啊，还是2啊等等这样的关系
		int m = calc_vertex_pos(g,v1);//比如v1=0
		int n = calc_vertex_pos(g,v2);//v2 = 1 (0,1)就表示有边，就要把这个位置值设为1
		//同时(1,0)这个位置也要设置为1，毕竟是无向图
		g.edge[m][n] = 1;
		g.edge[n][m] = 1;
	}
}
 
//打印一张图
void print_graph(graph& g)
{
	//打印图也就是打印这个二维数组
	printf("\t");
	//循环水平的顶点表头
	for(int i = 0;i < g.vertex_num;i++) {
		printf("%s\t",g.vertex[i]);
	}
	//循环二维数组内容
	for(int i = 0;i < g.vertex_num;i++) {
		//打印水平的顶点表头
		printf("\n");//每次换一个行
		printf("%s\t",g.vertex[i]);
		//然后输出一行的内容
		for(int j = 0;j < g.vertex_num;j++) {
			printf("%d\t",g.edge[i][j]);
		}
	}
	printf("\t");
}
 
 
//构建图
void test01()
{
	graph g;
	create_graph(g);
	print_graph(g);
}
 
int main() 
{
	test01();
	return 0;			
}

运行结果：

 下面说一下有向图，有向图，无非就是边带了方向对吧，比如对于无向图来说(v1,v2)和(v2,v1)其实啊都表示一个意思，什么意思呢，就代表这条边呗，那么有向图来说,如果这条边是v1->v2,也就是说v1表示狐尾，v2表示狐头，v1出度，v2入度，那么这个时候(v1,v2)与(v2,v1)就不是一个意思，(v1,v2)才能表示v1->v2，那么(v2,v1)这个坐标在邻接矩阵中怎么表示呢？这个位置其实我们就可以设置一个不可能的值，然后其他满足方向条件的，我们就设置一个权值，为什么你说方向不相关的位置为什么不设置为0,因为0也可能代表权值，一般权值就表示这两个点的距离啊，时间啊这些相关的一些东西。这就是有向图的设计思想，下面用一张图展示一下

话不多说，直接上代码；

directed_graph.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
//最大顶点数
#define MAX_VERTEX 30
 
//定义图结构
typedef struct _graph
{
	//顶点数组，存储顶点名字
	char **vertex;
	//边的数组
	int edge[MAX_VERTEX][MAX_VERTEX];
	//顶点个数
	int vertex_num;
	//边的条数
	int edge_num;
}graph;
 
//算出用户输入的顶点在数组中的位置
//这里就是比如输入一个v1,v2,那么对于无向图来说，(v1,v2)与(v2,v1)都代表的是同一条边
int calc_vertex_pos(graph &g,char* v)
{
	//遍历顶点数组
	for(int i = 0;i < g.vertex_num;i++) {
		//这里相当于就是字符串比较
		if(strcmp(v,g.vertex[i]) == 0) {
			return i;//找到直接返回这个位置
		}
	}
	return -1;
}
 
//创建一个图
void create_graph(graph &g)
{
	printf("请输入图的顶点数目与边数目:顶点 边\n");
	scanf("%d %d",&g.vertex_num,&g.edge_num);
	printf("请输入%d个顶点值\n",g.vertex_num);
 
	//开始循环给顶点数组赋顶点值
	//在赋值之前需要在堆上开辟空间存放字符串
	g.vertex = (char**)malloc(sizeof(char*) * g.vertex_num);
	for(int i = 0;i < g.vertex_num;i++) {
		char str[100] = {0};
		scanf("%s",str);
		//这个数组又指向了分配的一个空间
		g.vertex[i] = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.vertex[i],str);
	}
	//把边的二维数组也给初始化一下
	//以顶点数n，形成一个n*n的二维数组
	for(int i = 0;i < g.vertex_num;i++) {
		for(int j = 0;j < g.vertex_num;j++) {
			//对于有向图来说，这些点应该初始化成一个不太可能的值
			g.edge[i][j] = INT_MAX;
		}
	}
 
	//上面二个数组内容给初始化好了
	//下面来设置边与边的关系，就是是否有边
	printf("请输入%d条边和与之对应的顶点1，顶点2\n",g.edge_num);
	//设置两个有边的顶点之间的关系
	char v1[10];
	char v2[10];
	//设置一个权值
	int weight;
	//有多少条边，就对应了有多少个顶点
	for(int i = 0;i < g.edge_num;i++) {
		scanf("%s %s %d",v1,v2,&weight);
		//然后我们计算顶点在数组中的位置
		//是0啊，1啊，还是2啊等等这样的关系
		int m = calc_vertex_pos(g,v1);//比如v1=0
		int n = calc_vertex_pos(g,v2);//v2 = 1 (0,1)就表示有边，就要把这个位置值设为1
		//现在这两个点是有方向的，所以都设置不可能啊，只有一个方向嘛
		g.edge[m][n] = weight;//直接变为权值
	}
}
 
//打印一张图
void print_graph(graph& g)
{
	//打印图也就是打印这个二维数组
	printf("\t");
	//循环水平的顶点表头
	for(int i = 0;i < g.vertex_num;i++) {
		printf("%s\t",g.vertex[i]);
	}
	//循环二维数组内容
	for(int i = 0;i < g.vertex_num;i++) {
		//打印水平的顶点表头
		printf("\n");//每次换一个行
		printf("%s\t",g.vertex[i]);
		//然后输出一行的内容
		for(int j = 0;j < g.vertex_num;j++) {
			printf("%d\t",g.edge[i][j]);
		}
	}
	printf("\t");
}
 
 
//构建图
void test01()
{
	graph g;
	create_graph(g);
	print_graph(g);
}
 
int main() 
{
	test01();
	return 0;			
}

 上面说了邻接矩阵的表示方法，这个方法呢，就是利用二维数组来做的，那么如果点特别多，边少的情况下，空间、时间是比较浪费的，所以，为了避免空间太过于浪费我们就可以用邻接表这样一种方法来做，它的意思就是类似于在内存上面开辟空间，就说当两个顶点之间有关系的时候，就开一个内存来指明这种关系，所以不会浪费空间，就是实现比较麻烦

下面说一下用邻接表来实现无向图：

先来分析一下数据结构：

        

在来具体分析一下它的每一个顶点的插入思路：

         

继续

 

 继续

 另外说一点；

上无向图完整代码：

undirected_graph1.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
//最多能存放的顶点数目
#define MAX_VERTEX 100
 
struct edge_node {
	int position;//这个表示vertex数组中的哪一个结点索引
	edge_node *next;//存放下一个邻接点的指针
	//这里权重可写可不写
};
 
struct vertex {
	char *name;//存放顶点名字,一级指针指向一个堆上面分配的空间
	//还有存放每一个与之相邻的第一个邻接点，其实这里它就相当于是头结点
	edge_node *first_node;
};
 
//最后需要整个图的结构
//来存放相应图的信息
struct graph {
	//存放顶点的所有信息
	vertex head[MAX_VERTEX];
	//顶点数与边数
	int vertex_num;
	int edge_num;
};
 
 
 
//这里还是来确定一下顶点位置
int find_pos(graph &g,char *v)//这里v如果有指向就可以打印,我的意思就是scanf直接赋值是不行的
{
	for (int i = 0; i < g.vertex_num; i++) {
		//循环存放顶点名字的那一片空间
		if (strcmp(g.head[i].name, v) == 0) {
			return i;
		}
	}
	return -1;
}
 
//先来创建一张图
void create_graph(graph &g)
{
	printf("请输入顶点数与边数:\n");
	scanf("%d %d", &g.vertex_num, &g.edge_num);
	//循环输入顶点的值
	printf("请输入%d个顶点值:\n", g.vertex_num);
	//循环给顶点赋值
	for (int i = 0; i < g.vertex_num; i++){
		char str[30] = { 0 };
		scanf("%s", str);
		//单纯scanf("%s",&g.head[i].name)肯定不行，这个name事一个二级指针
		g.head[i].name = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.head[i].name, str);//在哪一个索引位置存放顶点
		//除了赋值字符串之外，还需要初始化一个邻接点的地址
		g.head[i].first_node = NULL;//类似于每一个头顶点的next全是NULL
	}
 
	//下面开始来输入边，也就是两个顶点
	printf("请输入%d条边，顶点1，顶点2", g.edge_num);
	char v1[10];
	char v2[10];
	//循环给边赋值
	for (int i = 0; i < g.edge_num; i++) {
		scanf("%s %s", v1,v2);
		int m = find_pos(g, v1);
		int n = find_pos(g, v2);
		//在内存中找到了每个顶点的编号
		//然后比如说m是不是就是代表某个顶点的头部，这里可以
		//当成链表的头部处理
		//然后我们实现头插，表示某种联系
		//最后我们实现关系的一个交互，这是对于无向图来说v1与v2和v2与v1的关系一样
		
		//创建一个新的邻接点
		edge_node *p_new = (edge_node*)malloc(sizeof(edge_node));
		//然后开始在头部插入，这个头部也就是m点
		p_new->position = n;
		//这里p_new必须先指
		p_new->next = g.head[m].first_node;
		g.head[m].first_node = p_new;
 
		//然后实现v0与v1的一个交替，也就是一个意思
		edge_node *p_new1 = (edge_node*)malloc(sizeof(edge_node));
		//其实就是实现一个m与n的交替
		p_new1->position = m;
		p_new1->next = g.head[n].first_node;
		g.head[n].first_node = p_new1;
	}
}
 
 
//打印这张图
void print_graph(graph &g)
{
	for (int i = 0; i < g.vertex_num; i++) {
		printf("%s: ", g.head[i].name);
		//拿到头部结点进行一个单链表的遍历
		edge_node *p_node =  g.head[i].first_node;
		while (p_node != NULL) {
			//拿到的是n，找它的m
			int index = p_node->position;
			printf("%s ", g.head[index].name);
			p_node = p_node->next;
		}
		//换行
		printf("\n");
	}
}
 
int main()
{
	graph g;
	create_graph(g);
	print_graph(g);
	return 0;
}

 运行结果：

   在来说有向图怎么来实现，比如下面这个有向图

     

        对于有向图来说，无非就是把上面代码需要处理反转的地方给删除，因为v0 v1与v1 v0已经不是一个意思了，直接上代码

        directed_graph1.cpp

        

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
//最多能存放的顶点数目
#define MAX_VERTEX 100
 
struct edge_node {
	int position;//这个表示vertex数组中的哪一个结点索引
	edge_node *next;//存放下一个邻接点的指针
	//这里权重可写可不写
};
 
struct vertex {
	char *name;//存放顶点名字,一级指针指向一个堆上面分配的空间
	//还有存放每一个与之相邻的第一个邻接点，其实这里它就相当于是头结点
	edge_node *first_node;
};
 
//最后需要整个图的结构
//来存放相应图的信息
struct graph {
	//存放顶点的所有信息
	vertex head[MAX_VERTEX];
	//顶点数与边数
	int vertex_num;
	int edge_num;
};
 
 
 
//这里还是来确定一下顶点位置
int find_pos(graph &g,char *v)//这里v如果有指向就可以打印,我的意思就是scanf直接赋值是不行的
{
	for (int i = 0; i < g.vertex_num; i++) {
		//循环存放顶点名字的那一片空间
		if (strcmp(g.head[i].name, v) == 0) {
			return i;
		}
	}
	return -1;
}
 
//先来创建一张图
void create_graph(graph &g)
{
	printf("请输入顶点数与边数:\n");
	scanf("%d %d", &g.vertex_num, &g.edge_num);
	//循环输入顶点的值
	printf("请输入%d个顶点值:\n", g.vertex_num);
	//循环给顶点赋值
	for (int i = 0; i < g.vertex_num; i++){
		char str[30] = { 0 };
		scanf("%s", str);
		//单纯scanf("%s",&g.head[i].name)肯定不行，这个name事一个二级指针
		g.head[i].name = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.head[i].name, str);//在哪一个索引位置存放顶点
		//除了赋值字符串之外，还需要初始化一个邻接点的地址
		g.head[i].first_node = NULL;//类似于每一个头顶点的next全是NULL
	}
 
	//下面开始来输入边，也就是两个顶点
	printf("请输入%d条边，顶点1，顶点2", g.edge_num);
	char v1[10];
	char v2[10];
	//循环给边赋值
	for (int i = 0; i < g.edge_num; i++) {
		scanf("%s %s", v1,v2);
		int m = find_pos(g, v1);
		int n = find_pos(g, v2);
		//在内存中找到了每个顶点的编号
		//然后比如说m是不是就是代表某个顶点的头部，这里可以
		//当成链表的头部处理
		//然后我们实现头插，表示某种联系
		//最后我们实现关系的一个交互，这是对于无向图来说v1与v2和v2与v1的关系一样
		
		//创建一个新的邻接点
		edge_node *p_new = (edge_node*)malloc(sizeof(edge_node));
		//然后开始在头部插入，这个头部也就是m点
		p_new->position = n;
		//这里p_new必须先指
		p_new->next = g.head[m].first_node;
		g.head[m].first_node = p_new;
/*
 * 有向图把这个位置注释掉就行
		//然后实现v0与v1的一个交替，也就是一个意思
		edge_node *p_new1 = (edge_node*)malloc(sizeof(edge_node));
		//其实就是实现一个m与n的交替
		p_new1->position = m;
		p_new1->next = g.head[n].first_node;
		g.head[n].first_node = p_new1;
*/
	}
}
 
 
//打印这张图
void print_graph(graph &g)
{
	for (int i = 0; i < g.vertex_num; i++) {
		printf("%s: ", g.head[i].name);
		//拿到头部结点进行一个单链表的遍历
		edge_node *p_node =  g.head[i].first_node;
		while (p_node != NULL) {
			//拿到的是n，找它的m
			int index = p_node->position;
			printf("%s ", g.head[index].name);
			p_node = p_node->next;
		}
		//换行
		printf("\n");
	}
}
 
int main()
{
	graph g;
	create_graph(g);
	print_graph(g);
	return 0;
}

运行结果：

   有向图与无向图就都做完了。