图结构

feixiaoxing · 更新于 2017-12-22 09:00:57

图结构

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

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个节点，那么1000010000该是多大的一个空间啊。重要的是，这1000010000上面大多数点都是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）图的表示是图运算的基础，掌握它们是我们进一步学习的基本条件