数据结构——邻接矩阵（图）

        图的存储结构主要有两种，分别是邻接矩阵和邻接表。本章先详看一下邻接矩阵，关于邻接矩阵，即用一个一维数组存储n个顶点，用一个n*n的二维数组存储边；在二维数组E [ i ] [ j ] 值为 1，则表示顶点V [ i ]到V [ j ]有边。

注意：由于不存在自己到自己的边，左对角线上的值一定为0

如果存储的是无向图则二维数组的值沿对角线对称，可以压缩成一维数组（参考矩阵压缩）

因为广度优先需要用队列进行，所以别忘了要加上存放队列操作函数声明的头文件

先定义一下邻接矩阵的结构：

//邻接矩阵
typedef struct Graph
{
	char *v;//顶点集 一维数组
	char *e;//边集 二位数组
	int cnt;//顶点数量
}Graph;

运算如下：

创建

//创建
Graph *create_graph(const char *str)
{
	//申请图结构所需的内存
	Graph *graph=malloc(sizeof(Graph));
	//计算顶点数量
	graph->cnt=strlen(str);
	//申请存储顶点的内存
	graph->v=malloc(graph->cnt);
	//存储顶点
	strcpy(graph->v,str);
	//申请边存储的内存
	graph->e=calloc(graph->cnt,graph->cnt);
	return graph;
}

添加边，有向图和无向图的构造就一行代码之差，详见下代码：

//添加边
bool add_graph(Graph *graph,char v1,char v2)
{
	int x=-1,y=-1;
	for(int i=0;i<graph->cnt;i++)
	{
		if(v1==graph->v[i]) x=i;
		if(v2==graph->v[i]) y=i;
	}
	if(x==-1 || y==-1) return false;
	//有向图
	graph->e[x*graph->cnt+y]=1;
	//无向图
	//graph->e[y*graph->cnt+x]=1;
	return true;
}

打印

//打印
void show_graph(Graph *graph)
{
	for(int i=0;i<graph->cnt;i++)
	{
		printf(" %c",graph->v[i]);	
	}
	printf("\n");
	for(int i=0;i<graph->cnt;i++)
	{
		printf("%c",graph->v[i]);
		for(int j=0;j<graph->cnt;j++)
		{
			printf(" %d",graph->e[i*graph->cnt+j]);	
		}
		printf("\n");
	}
}

计算顶点入度

//计算顶点的入度
int id_graph(Graph *graph,char v)
{
	for(int y=0;y<graph->cnt;y++)
	{
		if(v==graph->v[y])
		{
			int id=0;
			for(int x=0;x<graph->cnt;x++)
			{
				id+=graph->e[x*graph->cnt+y];	
			}
			return id;
		}
	}
	return -1;
}

计算顶点出度

//计算顶点的出度
int od_graph(Graph *graph,char v)
{
	for(int x=0;x<graph->cnt;x++)
	{
		if(v==graph->v[x])
		{
			int od=0;
			for(int y=0;y<graph->cnt;y++)
			{
				od+=graph->e[x*graph->cnt+y];	
			}
			return od;
		}
	}
	return -1;
}

深度优先遍历

//深度优先遍历
bool visit[7];//标记数组用于追踪访问情况
void _dfs_show(Graph *graph,int i)
{
	visit[i]=true;
	printf("%c ",graph->v[i]);
	int j;
	for(j=0;j<graph->cnt;j++)
	{
		if(graph->e[i*graph->cnt+j]==1 && !visit[j])
			_dfs_show(graph,j);
	}
}
void dfs_show(Graph *graph)
{
	int i;
	/*for(i=0;i<graph->cnt;i++)
	{
		visit[i]=false;
	}*/	//初始化默认全false
	for(i=0;i<graph->cnt;i++)
	{
		if(!visit[i])
			_dfs_show(graph,i);
	}
}

广度优先遍历

注意：需要借助队列进行操作，具体可以参考以前的链队列的文章

//广度优先遍历
void bfs_show(Graph *graph)
{
	bool visit[graph->cnt];
	ListQueue *queue=create_queue();
	for(int i=0;i<graph->cnt;i++)
	{
		if(!visit[i])
		{
			visit[i]=true;
			printf("%c ",graph->v[i]);
			in_queue(queue,i);

			while(queue->cnt)
			{
				int current=0;
				head_queue(queue,&current);
				out_queue(queue);

				for(int j=0;j<graph->cnt;j++)
				{
					if(graph->e[current*graph->cnt+j] && !visit[j])
					{
						visit[j]=true;
						printf("%c ",graph->v[j]);
						in_queue(queue,j);
					}
				}
			}
		}
	}
	destroy_queue(queue);
}

下面设计一个测试看看代码的完整性和正确性：

int main(int argc,const char* argv[])
{
	char *str="ABCDEFG";
	Graph *graph=create_graph(str);
	add_graph(graph,'A','B');
	add_graph(graph,'A','D');
	add_graph(graph,'B','D');
	add_graph(graph,'B','E');
	add_graph(graph,'C','D');
	add_graph(graph,'C','F');
	add_graph(graph,'D','C');
	add_graph(graph,'D','G');
	add_graph(graph,'E','G');
	add_graph(graph,'F','G');
	show_graph(graph);
	printf("id=%d\n",id_graph(graph,'C'));
	printf("od=%d\n",od_graph(graph,'C'));
	dfs_show(graph);
	printf("\n");
	bfs_show(graph);
		
	return 0;
}

测试的时候可以先构造一个连通图，然后根据添加边的逻辑来构造邻接矩阵

over