一步一步写算法（之图结构）

原文: 一步一步写算法（之图结构）

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】

     图是数据结构里面的重要一章。通过图，我们可以判断两个点之间是不是具有连通性；通过图，我们还可以计算两个点之间的最小距离是多少；通过图，我们还可以根据不同的要求，寻找不同的合适路径。当然，有的时候为了计算的需要，我们还需要从图中抽象出最小生成树，这样在遍历计算的时候就不需要持续判断是不是遇到了循环节点。当然，这所有的一切都是从图的表示开始的。

    1）矩阵表示

    矩阵表示可以说是最简单的表示方法，如果说一个图中有5个点，那么我们就可以构建一个5*5的矩阵。如果点和点之间存在连接，那么填上1；反之如果不存在连接，那么可以用0表示，当然对角线上面的点是没有意义的。如下图所示：

static int graph[5][5] = 
{
	{0, 1, 0, 1, 1},
	{1, 0, 1, 0, 1},
	{0, 1, 0, 1, 0},
	{1, 0, 1, 0, 1},
	{1, 1, 0, 1, 0}
};

    如果点和点之间还是存在方向的，那么它们关于(x，x)对称轴就是不对称的，所以结果也可能是这样的：

static int graph[5][5] = 
{
	{0, 0, 0, 0, 0},
	{1, 0, 0, 0, 0},
	{0, 1, 0, 0, 0},
	{1, 0, 1, 0, 0},
	{1, 1, 0, 1, 0}
};

    当然，如果点和点之间的关系存在某种权重，比如说距离，那我们可以用它来代替原来的数据1：

static int graph[5][5] = 
{
	{0, 0, 0, 0, 0},
	{3, 0, 0, 0, 0},
	{0, 6, 0, 0, 0},
	{8, 0, 4, 0, 0},
	{9, 2, 0, 7, 0}
};

    矩阵表示下的图结构非常直观。但是，矩阵有一个特点，就是比较浪费空间。因为我们这里举例的顶点比较少，只有5个，但是请大家试想一下，如果一张图上有10000个节点，那么10000*10000该是多大的一个空间啊。重要的是，这10000*10000上面大多数点都是0，所以浪费的空间是相当可观的。

    2）数组结构

    为了改变矩阵浪费空间的特点，我们可以建立一个只有顶点和边组成的数据空间。比如说，我们定义一个这样的结构：

typedef struct _LINE
{
	int start;
	int end;
	int weight;
	int isDirection;
}LINE;

    上面定义的数据结构非常简洁。第1个为起始顶点，第2个为终点，第3个为权重，第4个判断当前边是否有向。图中要是有多少边，我们就要定义多少个这样的数据。如果把这些边的数据都放在一起构成一个数组，那么我们就可以用这个数组来表示图的全部信息了。

    但是，我们还是觉得有遗憾的地方。这个数据结构过分强调了边的意义和重要性，忽略了顶点本身的含义。因为，我们在强调边的时候，应该添加进顶点的相关特性。离开顶点的支持，单纯的边信息是没有什么含义的。

    3）基于顶点链表的图表示

    首先，我们定义顶点的基本结构：

typedef struct _LINE
{
	int end;
	int weight;
	struct _LINE* next;
}LINE;

typedef struct _VECTEX
{
	int start;
	int number;
	LINE* neighbor;
}VECTEX;

    我们用VECTEX记录顶点的相关信息，LINE表示节点的相关信息。如果LINE是在VECTEX中的变量，那么neighbor表示当前所有节点的起始点都是start点。如果它是PATH中的变量呢，那么next的起始点就是LINE链接的前面一个点，不知道我讲清楚了没有？下面就是点与点之间PATH的定义。

typedef struct _PATH
{
	int start;
	int end;
	int lenth;
	LINE* next;
}PATH;

    其中start为起始点，end为终结点，next为start链接的下一个点，lenth为路径的总长度，当然也可以修改成其他的权重形式。

注意事项：

    1）数组和链表是图结构的基础，朋友们应该好好掌握

    2）每一种数据结构都有自己的应用场合，关键是理解其中的思想和方法

    3）图的表示是图运算的基础，掌握它们是我们进一步学习的基本条件