图的定义
-
图是由顶点的有穷非空集合和顶点之间边的集合组成，通过表示为G(V,E)，其中，G标示一个图，V是图G中顶点的集合，E是图G中边的集合。
-
无边图：若顶点Vi到Vj之间的边没有方向，则称这条边为无项边（Edge），用序偶对(Vi,Vj)标示。
-
有向图：若从顶点Vi到Vj的边是有方向的，则成这条边为有向边，也称为弧（Arc）。用有序对（Vi，Vj）标示，Vi称为弧尾，Vj称为弧头。如果任意两条边之间都是有向的，则称该图为有向图。
有向图G2中，G2=（V2,{E2}），顶点集合（A,B,C,D）,弧集合E2={<A,D>,{B,A},<C,A>,<B,C>}.
- 权（Weight）：有些图的边和弧有相关的数，这个数叫做权（Weight）。这些带权的图通常称为网（Network）。
图的表示
邻接矩阵
- 说明
拥有n个顶点的图，它所包含的连接数量最多是n（n-1）个；因此，要表达各个顶点之间的关联关系，最清晰易懂的方式是使用二维数组（矩阵）。无向图/有向图：
AdjacencyMatrix.png
AdjacencyMatrix1.png
* 顶点0和顶点1之间有边关联，那么矩阵中的元素A[0][1]与A[1][0]的值就是1；
* 顶点1和顶点2之间没有边关联，那么矩阵中的元素A[1][2]与A[2][1]的值就是0。
* 矩阵从左上到右下的一条对角线，其上的元素值必然是0：任何一个顶点与它自身是没有连接的。
* 无向图对应的矩阵是一个对称矩阵，因此A[m][n]和A[n][m]的值一定相等。
* 有向图不再是一个对称矩阵，，因此A[m][n]和A[n][m]的值不一定相等。
-
优点：简单直观，可以快速查到一个顶点和另一顶点之间的关联关系。
-
缺点：占用空间大，如果一个图有1000个顶点，其中只有10个顶点之间有关联（这种情况叫做稀疏图），却不得不建立一个1000X1000的二维数组。
邻接表 和 逆邻接表
-
邻接表
为了解决邻接矩阵占用空间的问题。邻接表中，图的每一个顶点都是一个链表的头节点，其后连接着该顶点能够直接达到的相邻顶点。
AdjacencyTable.png
* 邻接表的存储方式，占用的空间比邻接矩阵要小得多;
* 想查出从顶点0能否到达顶点1，该怎么做呢？很简单，我们从顶点0开始，顺着链表的头节点向后遍历，看看后继的节点中是否存在顶点1。
* 想查出顶点0能够到达的所有相邻节点，也很简单，从顶点0向后的所有链表节点，就是顶点0能到达的相邻节点。
* 要想查出有哪些节点能一步到达顶点1，这样就麻烦一些了，我们要遍历每一个顶点所在的链表，看看链表节点中是否包含节点1，最后发现顶点0和顶点3可以到达顶点1。
-
逆邻接表
针对上述逆向查找的麻烦的问题，可以是用逆邻接表来解决。逆邻接表，和邻接表是正好相反的。逆邻接表每一个顶点作为链表的头节点，后继节点所存储的是能够直接达到该顶点的相邻顶点。
要想查出有哪些节点能一步到达顶点1就容易了，从顶点1向后的所有链表节点，就是能一步到达顶点1的节点。
根据实际需求，选择使用邻接表还是逆邻接表。
ReverseAdjacency.png
十字链表
同理，上述一个图可能会存在要维护正反连个邻接表。十字链表正好是将两种结合起来。
CrossLinked.png
十字链表的每一个顶点，都是两个链表的根节点，其中一个链表存储着该顶点能到达的相邻顶点，另一个链表存储着能到达该顶点的相邻节点。
我们没有必要把链表的节点都重复存储两次。在优化之后的十字链表中，链表的每一个节点不再是顶点，而是一条边，里面包含起止顶点的下标。
CrossLinked-finish.png
图中每一条带有黑色箭头的链表，存储着从顶点出发可到达的边；每一条彩色箭头的链表，存储着进入顶点的边。
图的搜索
- 深度优先遍历：
也有称为深度优先搜索，简称DFS（Depth First Search）。其实，就像是一棵树的前序遍历。它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有 路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。
基本实现思想：
（1）访问顶点v；
（2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
（3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
- 广度优先遍历：
也称广度优先搜索，简称BFS（Breadth First Search）。BFS算法是一个分层搜索的过程，和树的层序遍历算法类同，它也需要一个队列以保持遍历过的顶点顺序，以便按出队的顺序再去访问这些顶点的邻接顶点。
基本实现思想：
（1）顶点v入队列。
（2）当队列非空时则继续执行，否则算法结束。
（3）出队列取得队头顶点v；访问顶点v并标记顶点v已被访问。
（4）查找顶点v的第一个邻接顶点col。
（5）若v的邻接顶点col未被访问过的，则col入队列。
（6）继续查找顶点v的另一个新的邻接顶点col，转到步骤（5）。
直到顶点v的所有未被访问过的邻接点处理完。转到步骤（2）。
广度优先遍历图是以顶点v为起始点，由近至远，依次访问和v有路径相通而且路径长度为1，2，……的顶点。为了使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，需设置队列存储访问的顶点。
下一节主要实现：
网友评论