一步一步写算法（之图结构）
【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：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）图的表示是图运算的基础，掌握它们是我们进一步学习的基本条件
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
