1.关于图模型
图是由结点(顶点)和连接(边)组成的模型。可以应用网页信息、调用关系,调度顺序等问题上。这里我们将依次介绍4种比较重要的图模型:无向图,有向图,加权图,加权有向图。
2.无向图
2.1.简介
无向图是指边没有方向性的图。我们在这里约定,用0-V的整数来表示有V个顶点的图的顶点,用v-w表示两个顶点的连接(此处无向图w-v和v-w表示的连接一致)。后续的内容暂不考虑自环和平行边的情况,但是这些数据结构和算法是支持的。
2.2.实现无向图
我们首先需要将模型实现为一个数据结构,我们通常希望它支持的算法能够有足够低的时间复杂度和空间复杂度,而邻接表数组能够满足我们的需求。
在这里的邻接表数组的具体结构是一个V长度的数组,用顶点作为数组的引索,每个元素是一个链表,链表的元素是与这个顶点相连接的顶点。这里我们使用vector来作为链表的代替来实现。
现在我们要实现的有以下内容,其中有辅助的函数。
1 | class Graph{ |
具体实现:
1 | Graph(int V) |
2.3.DFS算法
图模型中有一类问题,即连通性问题和路径问题。比如在一个无向图中,判断从起点s开始,到某个顶点v是否有路径可达。
我们很容易能想到先从起点开始,顺序检查每个连接起点的边,从第一个边连接的另一个顶点开始不断重复这个过程,一条边一条边的往下深入,为了防止重复,给每个能检查到的顶点标记(使用一个数组储存标记bool marked[V]
),如果一条路线最后没有到达目标顶点,则返回换另外一条路线,直到找到路线或者遍历完所有可能路线。
这样一个思路所对应的算法就是DepthFirstSearch(DFS)算法。上面的描述中深入和返回就对应了递归的实现细节。见下面的代码。
1 | void dfs(Graph G, int s) |
DFS算法的时间复杂度是很低的,而且代码量也很少,这个算法所花费的时间是正比于顶点的度数之和。
下面我们来利用DFS算法解决刚才提到的路径问题
2.3.1. DFS应用——寻找无向图的路径
根据DFS的访问结点的特性,每个结点只会访问一次,那么最终所有从起点出发能被访问到的结点都会被标记,而且不会有环出现。那么我们可以用一个数组int edgeTo[V]
来储存所有可达的路径,其含义是“到达顶点V的顶点”,如此它也存在一种递归的思想,在dfs的过程中如果发现下一个顶点w没有被标记,就令edgeTo[w] = s
。当dfs完成后,根据marked数组判断有无可达路径,再利用egeTo数组结合栈导出路径。
1 | void dfs(Graph G, int s) |
2.3.2. 路径问题的延申——最短路径问题
将上述的路径问题所求路径增加限制最短,那么DFS就不怎么管用了,但这个思想可以继续沿用,DFS是优先探索的深度,对于问题就是找到路径优先,它会把一条路线走尽才会切换另一条,找到的路径通常不是最短的。要想最短,我们需要改变探索策略,对于起点而言,最短的路径是到邻接顶点的路径,同样对于任意一个顶点,从它开始的路径最短就是邻接顶点。
那么我们如果每次探索的时候以路径长度为层级,优先探索邻接顶点,当同一层级的顶点被探索完再探索一下一层级,那么对于每一个被标记的顶点,从起点到它的路径都是最短的。到达某个顶点,对于同样的长度可能有不同的路径,我们取其中一个(最早探索的)。而路径不同并不影响后续,因为都到达同一个顶点,后续操作也只是由这个顶点开始,所以只要长度一样就行。这里我们为了方便操作使用队列来储存未被标记的点。
上述的内容对应一个新的算法BreadthFirstSearch(BFS),其具体实现如下。
1 | void bfs(Graph G, int s)//s指start,起点 |
后面的获取路径同上面的一般路径问题是一致的。
2.3.3. 连通分量问题
如果任意顶点间都可达,把这样的图称为连通图,而一幅非连通的图可能由若干个连通子图(连通分量)构成,我们将要研究找出一个图里的所有连通分量。
DFS算法可以从一个点开始遍历这个点所在的连通分量,那么我们对于图的每个未标记的结点都进行一次DFS,每次DFS对应一个不同的连通分量,就可以解决问题。
这里我们构造一个连通分量的类,如下。
1 | class CC{ |
2.3.4. 双色问题
判断一个图是否能用两种颜色将所有顶点着色,使得任意一边的两个顶点颜色都不相同。(即是否是二分图)
我们用一个颜色数组bool color[V]
来标记顶点颜色,bool isTwoColorable
变量来表示是否成立。解决这个问题,实际上只需要稍微改动dfs。双色对称,着色互换无影响,所以只考虑边的颜色相反,起点是那种颜色不影响。dfs过程中,对于这个顶点,探索它的邻接顶点时会,对于未被标记的邻接顶点,会标记并且着色为顶点的反色(true和false对应两色);如果探索到已标记的顶点,会检查是否反色,否的话则不是二分图。
这是一个逻辑上递进的过程,从起点开始着色,一步步dfs访问邻接顶点,理解的要点是这个过程的每个邻接顶点着色是可以根据顶点颜色确定的,所以一旦遇到已标记而且同色,就可以确定不可能是二分图。
1 | void dfs(Graph G, int v) |