数据结构之图(存储结构、遍历) - 时光漫步LH

本邮件内容由第三方提供，如果您不想继续收到该邮件，可 点此退订 。

数据结构之图(存储结构、遍历) - 时光漫步LH  阅读原文»

　　新学期开始了，开始专心于技术上了，上学期的寒假总是那么短暂，飘飘乎就这样逝去，今天补补上学期还没学完的数据结构---图，希望能和大家一起探讨，共同进步~

定义：

　　图是由顶点集合及顶点间的关系集合组成的一种数据结构。

　　

图的存储结构：

1.1 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

看一个实例，下图左就是一个无向图。

从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足a_ij = a_ji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。

从这个矩阵中，很容易知道图中的信息。

（1）要判断任意两顶点是否有边无边就很容易了；

（2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；

（3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[j]为1就是邻接点；

而有向图讲究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。

若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：

这里的w_ij表示(v_i,v_j)上的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。下面左图就是一个有向网图，右图就是它的邻接矩阵。

那么邻接矩阵是如何实现图的创建的呢？代码如下。

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <curses.h>
4
5 typedef char VertexType; //顶点类型应由用户定义
6 typedef int EdgeType; //边上的权值类型应由用户定义
7
8 #define MAXVEX 100 //最大顶点数，应由用户定义
9 #define INFINITY 65535 //用65535来代表无穷大
10 #define DEBUG
11
12 typedef struct
13 {
14 VertexType vexs[MAXVEX]; //顶点表
15 EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵，可看作边
16 int numVertexes, numEdges; //图中当前的顶点数和边数
17 }Graph;
18
19 //定位
20 int locates(Graph *g, char ch)
21 {
22 int i = 0;
23 for(i = 0; i < g->numVertexes; i++)
24 {
25 if(g->vexs == ch)
26 {
27 break;
28 }
29 }
30 if(i >= g->numVertexes)
31 {
32 return -1;
33 }
34
35 return i;
36 }
37
38 //建立一个无向网图的邻接矩阵表示
39 void CreateGraph(Graph *g)
40 {
41 int i, j, k, w;
42 printf("输入顶点数和边数:\n");
43 scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
44
45 #ifdef DEBUG
46 printf("%d %d\n", g->numVertexes, g->numEdges);
47