图的邻接矩阵

图的邻接矩阵和邻接表

ps：本文主要针对还没有学过数据结构的人群，所以会尽量写得简单易懂，但用词上不一定十分准确。

一般来说，我们保存一个图常用的方法有两种，分别是邻接矩阵和邻接表。
下面我们用这张图来做例子：

这是一张无向图，无向图指的是通路没有方向的图。也就是说，如果点1和点2之间有通路，那么可以从点1到点2，也能从点2到点1。

有向图则是指通路有方向的图。也就是说，如果点1到点2有一条通路，那么只能从点1到点2，而不能从点2到点1。（当然可以同时存在点1到点2通路和点2到点1的通路，这种情况会构成一个环）
比如这样：

1.邻接矩阵

邻接矩阵相对而言更好理解。
假设有图有n个顶点，那么我们就建一个大小为（n+1）*（n+1）的二维数组。（注意这里顶点的编号是从1开始所以才需要+1）

现在有五个点，分别叫1 2 3 4 5（也可以用字符类型的名字，方法是用一个char数组存下每个点的名字，数组的下标就是点的编号，其实也就是在数字编号的基础上加一个char类型的名字）

我们建一个大小为6*6的二维数组map[6][6];
先用循环把二维数组的所有数全部初始化为一个很大的数，比如11111
然后再将图输入
一般输入图是这种输入格式：点1 点2 权值（权值不一定有）
把上面的例子（无向图）输入就是这样的：
1 2 7
2 3 12
3 4 2
4 5 8
3 5 3
4 1 17
这个图有六条边，所以有六行输入。
以输入的第一行为例，我们只要把map[1][2]和map[2][1]都置为7即可（因为是无向图所以可以从1到2也能从2到1，如果没有权值可以置为0），以此类推。
如果是有向图则只将map[1][2]置为7（单向通路）
这样我们就把图存好了。（没错邻接矩阵就是这么简单，但是它占的空间比较大
下面是代码

#include <stdio.h>
int main()
{
	int i,j;
	int point=5,side=6;//点的序号从1开始 ，point是点，side是边 
	int map[point+1][point+1];//建图 
	for(i=0;i<point+1;i++)//初始化为11111 
		for(j=0;j<point+1;j++)
			map[i][j]=11111;
	for(i=0;i<side;i++)//输入图的side条边 
	{
		int p1,p2,weigh;
		scanf("%d%d%d",&p1,&p2,&weigh);
		map[p1][p2]=weigh;
		map[p2][p1]=weigh;//无向图双向 
	}
	for(i=1;i<point+1;i++)//输出 
	{
		for(j=1;j<point+1;j++)
			printf("%d\t",map[i][j]);
		printf("\n");
	}
	return 0;
} 

输出效果为：

//本来要和邻接表一起讲的但是我最近头有点凉，让我缓缓……