[+]文章目录

图结构

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

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)图的表示是图运算的基础,掌握它们是我们进一步学习的基本条件


« 前一篇