图
图 是由顶点的有穷非空集合和顶点之间边的集合组成。
图 是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。
线性表中我们把数据元素叫元素，树中将数据元素节点，在图中数据元素，我们则称之为顶点。
线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的节点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
若顶点到顶点之间的边没有方向，则称这条边为 无向边。
若顶点到顶点之间的边有方向，则称这条边为 有向边，也称为 弧。
如果图中任意两个顶点之间的边都是有向边，则称该图为 有向图。
如果图中任意两个顶点之间的边都是无向边，则称该图为 无向图。
在无向图中，如果任意两个顶点之间都存在边，则称该图为 无向完全图。
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为 有向完全图。
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为 简单图。
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做 权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为 网。
与该顶点相关联的总边数称为 度。在有向图中，顶点的度还可分为出度和入度。以该顶点为起点的边称为 出度，以该顶点为终点的边称为 入度。
从一个顶点到另一个顶点之间的边序列叫做 路径，路径上的边或弧的数目称为 路径的长度。
第一个顶点和最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。
无向图中连通且 n 个顶点 n-1 条边叫 生成树。有向图中一顶点入度为 0 其余顶点入度为 1 的叫 有向树。一个有向图由若干棵有向树构成 生成森林。
图的存储
1.邻接矩阵
用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组存储图中的边或弧的信息。
在无向图中，顶点到顶点之间有边，就把二维数组里对应的值设为 1，否则设为 0。如果需要知道某个顶点的度，就是邻接矩阵某行元素之和。实际上，无向图的边数组是一个对称矩阵。
从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的称为 对称矩阵。
在有向图中，边是有方向的，根据方向分 入度 和 出度。因此，一个顶点到另一个顶点之间有边时二维数组对应的值设为 1，否则为 0。出度为某行之和，入度为某列之和。
如果在图中每条边带权时，称为 网。比如计算最短路径时，需要用到这个权值，因此需要把对应的权值存储下来。上面二维数组中用 1 和 0 来区分顶点之间是否有边，我们可以把真实的权值存储到对应的二维数组中去，这样就解决来存储权值的问题。
2.邻接表
上面的邻接矩阵看起来是一个存储图不错的方案，但是，当边树比较少的图中，会浪费大量的存储空间。这个时候就可以变二维数组为 一维数组 + 链表 来存储对应的图了，称为邻接表。
图中顶点用一个一维数组存储，每个顶点的所有邻接点在对应一维数组后构成一个线性表，在无向图中称为顶点的边表，在有向图中称为顶点作为弧尾的出边表。
这样用 一维数组 + 链表 来存储图的方式叫做邻接表。
3.十字链表
上面的存储看似很完美，但有向图有方向，我们是以顶点为弧尾来存储边表的，这样很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧，我们可以建立一个有向图的逆邻接表，即对每个顶点都建立一个链接顶点为弧头的表。
把邻接表与逆邻接表结合起来的一种存储方法称为 十字链表。
新的顶点表节点结构，分别是 data、firstin、firstout。
data 表示顶点的信息。
firstin 表示入边表头指针，指向该顶点的入边表中第一个节点。
firstout 表示出边表头指针，指向该顶点的出边表中的第一个节点。
新的边表节点结构，分别是 tailvex、headvex、headlink、taillink。
tailvex 是指弧起点在顶点表的下标。
headvex 是指弧终点在顶点表中的下标。
headlink 是指入边表指针域，指向终点相同的下一条边。
taillink 是指边表指针域，指向起点相同的下一条边。
如果是网，还可以再增加一个 weight 域来存储权值。
十字链表的好处就是容易求得顶点的出度和入度。
4.邻接多重表
十字链表是对有向图的优化，可以很容易的求得顶点的出度和入度。
在无向图中，邻接表主要是关注的顶点，如果是要标记或者删除一条边的时候，邻接表的操作就比较麻烦了，这时候就可以参考有向图的优化十字链表了。
新的顶点表节点结构，分别是 data、firstedge。
data 表示顶点的信息。
firstin 表示第一个边表指针，指向该顶点的边表中第一个节点。
新的边表节点结构，分别是 ivex、ilink、jvex、jvex。
ivex 和 jvex 是与某条边依附的两个顶点在顶点表中的下标。
ilink 指向依附顶点 ivex 的下一条边，jlink 指向依附顶点 jvex 的下一条边。
这样的结构称为 邻接多重表。邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个节点表示，而在邻接多重表中只有一个节点。
图的遍历
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。
对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通常有两种遍历次序方案：它们是 深度优先遍历 和 广度优先遍历。
1.深度优先遍历
深度优先遍历（Depth First Search），也有称为深度优先搜索，简称为 DFS。
沿着顶点，尽可能深的遍历的分支。当顶点的所在边都己被探寻过，遍历将回溯到发现顶点的那条边的起始顶点。这一过程一直进行到已发现从源顶点可达的所有顶点为止。如果还存在未被发现的顶点，则选择其中一个作为源顶点并重复以上过程，整个进程反复进行直到所有顶点都被访问为止。
深度优先遍历 就像是树的前序遍历。
2.广度优先遍历
广度优先遍历（Breadth First Search），又称为广度优先搜索，简称BFS。
图的广度优先遍历就类似于树的层序遍历，就是从最上面的顶点，一层一层向下遍历，直到遍历所有的顶点。
总结
图 分为 无向图 和 有向图，与该顶点相关联的总边数称为 度，有向图中又分为 出度 和 入度。
从一个顶点到另一个顶点之间的边序列叫做 路径，路径上的边或弧的数目称为 路径的长度。
存储图的结构主要有 邻接矩阵、邻接表、十字链表 和 邻接多重表。
图的遍历分别为 深度优先遍历 和 广度优先遍历。
-- END
PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
微信公众号：「清尘闲聊」。
欢迎一起谈天说地，聊代码。
网友评论