数据结构--图的定义及存储结构
一、 图的定义和术语
1、 图按照无方向和有方向分为“无向图”和“有向图”
image.png
无向图是由顶点和边构成，有向图是由顶点和弧（有向边）构成。一条从x到y的弧， “弧头”（初始点）为y，“弧尾”（终端点）为x，如上图有向图，A到D的弧，A为弧尾，D为弧头。
2、 如果任意两个顶点之间都存在边叫“完全图”，上方第一个图就是完全图，有向的边叫“有向完全图”
3、 带权的图称为“网”，权可以表示一个顶点到另一个顶点的距离或耗费
image.png
4、 顶点的“度”是和顶点相关联的边的数目。有向图图中又有“入度”--方向指向顶点的边；“出度”--方向背向顶点的边。在有向图中顶点的度就是入度与出度之和。
image.png
上图：无向图顶点3的度为3
image.png
上图：有向图，顶点A的入度=2，出度=3，顶点A的度=2+3=4
5、 “路径长度”为路径上边或弧的数目，上图从B到D的路径长度为3
6、 第一个顶点和最后一个顶点相同的路径为“回路”或“环”，序列中顶点不重复出现的路径称为“简单路径”，除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为“简单回路”或“简单环”
image.png
7、 两个顶点之间有路径，则称两个顶点是“连通”的，任意两个顶点都是连通的称为“连通图”
image.png
左图A与E没有连通，不是连通图
8、 “连通分量”为无向图中的极大连通子图。（子图必须是连通的且含有极大顶点数）。上图左有两个连通分量
9、在有向图中，如果任意两个顶点之间都存在路径，则称这个有向图为“强连通图”（下图）。有向图中的极大强连通子图称作有向图的 “强连通分量”
image.png
下图1不是强连通图，但是有两个强连通分量（下图2、3）
image.png
10、 一个连通图的“生成树”是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n – 1条边，下图右是下图左中最大连通分量的一棵生成树。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得其中两个顶点之间有了第二条路径。一棵有n个顶点的生成树有且仅有n – 1条边。如果一个图有n个顶点，n – 1条边，是非连通图。如果多于n – 1条边，则一定有环。但有n – 1条边的图不一定是生成树，生成树一定有n – 1条边。
image.png
二、 图的存储结构
图的结构比较复杂，任意两个顶点间都可能存在联系，因此用多重链表表示图是很自然的事，由一个数据域和多个指针域组成的结点表示一个顶点，数据域存储该顶点的信息，指针域存储指向其相邻结点的指针，但是图中各个结点度数不同，最大度数和最小度数可能相差很多，因此若按最大度数的顶点设计结点结构，会存在浪费，若按每个顶点自己的度数设计不同的结点结构，会给操作带来不便。实际应用中通常采用邻接表，邻接多重表和十字链表来进行数据的存储。
1、 邻接矩阵
图的邻接矩阵存储方式是用两个数组来表示图。有n个顶点的图，用一个长度为n的一维数组来存储图中顶点信息，用一个n x n的二维数组（邻接矩阵）存储图中的边或弧的信息。
图的结构定义：
typedef struct {
char vexs[n]; //存储顶点信息
int arc[n][n]; //邻接矩阵，可看作边
int numVertexes, numEdges; //图中当前的顶点数和边数
} Graph;
举例：
A、无向图
image.png
从上面可以看出，无向图的边数组是一个对称矩阵。
从这个矩阵中，可知：
(1) 可判断任意两顶点是否有边
(2) 某个顶点的度，就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和
(3) 顶点vi的所有邻接点就是其所在的第i行（或第i列），值为1的元素
B、有向图
顶点vi的出度为第i行元素的和，入度为第i列元素的和。
C、网图（边带权值）
image.png
2、 邻接表
对于顶点多而边数少的图来说，使用邻接矩阵会使存储空间产生极大的浪费，因此使用数组与链表相结合的存储方式来解决这个问题，这种存储方式称为邻接表。
邻接表的处理方法：
(1) 图中的顶点用一个一维数组存储
(2) 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储。每个链表上设一个表头结点，表头结点含有两个域： 数据域（vexdata）--存储顶点的信息，指针域（firstearc）--指向链表中第一个结点。表结点由三个域组成：邻接点域（adjvex）--指示与顶点vi邻接的点在图中的位置，也就是存储这个顶点的邻接点在表中的下标，链域（nextarc）--指向下一条边或弧的结点的指针，数据域（info）--存储和边或弧相关的信息，如权值。
image.png
图的结构定义：
typedef struct EdgeNode { //表结点结构
int adjvex; //邻接点域，存储该顶点对应的下标
int weigth; //用于存储权值，对于非网图可以不需要
struct EdgeNode *next; //链域，指向下一个邻接点
} EdgeNode;
typedef struct VertexNode { //头结点结构
char data; //数据域，存储头结点信息
EdgeNode *firstedge; //指向与该头结点相连的第一个结点的指针
} VertexNode, AdjList[n];
typedef struct {
AdjList adjList;
int numVertexes, numEdges; //图中当前顶点数和边数
} GraphList;
举例：
A、 无向图（没有权值，所以表结点的结构可以不定义info这个域）
image.png
B、 网图（带权值，需要使用info这个域来存储权值）
image.png
在无向图的邻接表中，顶点vi的度为第i个链表中的结点数，而在有向图中，第i个链表中的结点数只是顶点vi的出度，求入度，须遍历整个邻接表，找到在所有链表中其连接点域的值为i的结点个数，这个个数才是顶点vi的入度。
为了便于确定顶点的入度，可以建立一个有向图的逆邻接表，即对每个顶点vi建立一个链接以vi为头的弧的表。
image.png
在邻接表上容易找到任意顶点的第一个邻接点和下一个邻接点，但要判断任意两个顶点间是否有边或弧相邻，则要搜索第i个或第j个链表，因此不及邻接矩阵方便。
3、 十字链表
十字链表可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表，十字链表的结点定义如下
image.png
弧结点有四个域：尾域(tailvex)--弧尾所在的结点在表中的下标，头域(headvex)--弧头所在的结点在表中的下标，hlink--指向弧头相同的下一条弧，tlink--指向弧尾相同的下一条弧。如果是网，还可以增加一个weight域来存储权值。
顶点结点（头结点）由三个域组成：data域--存储和顶点相关的信息，如名称等， firstin--指向以该顶点为弧头的第一个弧结点，也就是入边的第一个结点，firstout--指向以该顶点为弧尾的第一个弧结点，也就是出边的第一个结点。
举例：
image.png
如上图所示的图，实线箭头指针的图示完全与邻接表相同。以顶点v0举例，firstout指向的是出边中的第一个结点v3。所以v0的hearvex 表示v3在整个表中的下标为 3，之后的弧结点中所有域的值，说明的就是v0到v3这条弧。headlink指向以v0作为弧头的另一条弧，示例中没有，所以为空，tailvex指向以v3作为弧尾的另一条弧，示例中没有，所以为空。
对应顶点v0，它有两个顶点为v1和v2的入边。因此的firstin指向以顶点v0为弧头的第一个弧结点，也就是寻找弧结点中handvex这个域的值为0的弧结点，如上图圆圈1。v0还有一个入边，因此这个弧结点的handlink指向下一个handvex为0的弧结点，如上图圆圈2。对于顶点v1，它有一个顶点v2的入边，所以它的firstin指向以顶点v2为弧头的第一个弧结点，也就是寻找弧结点中handvex这个域的值为1的弧结点，如上图圆圈3。
十字链表因为把邻接表和逆邻接表组合在一起，所有很容易找到以vi为弧尾的弧，也能很容易找到以vi为弧头的弧，因此很容易求得任意顶点的入度和出度。
