算法_有向图
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法_有向图，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6114字，纯文字阅读大概需要9分钟。
内容图文
一.定义以及和无向图的区别
一幅有向图是由一组顶点和一组有方向的边组成的,每条有方向的边都连接着有序的一对顶点.有向边是由第一个顶点指出并指向第二个顶点,用v->w来表示有向图中一条由顶点v指向顶点w的一条边.当存在从v->w的有向路径的时候,称顶点w能够由顶点v达到.和无向图不同的是,在有向图中由v能够到达w,并不意味着由w也能到达v.下图为一个有向图举例.
二.有向图的数据类型
使用Bag表示有向图,其中边v->w表示为顶点v所对应的邻接链表中包含一个w顶点,与无向图不同的是,这里每条边只会出现一次.有向图的数据结构类型如下:
/**
* 有向图的数据类型
*
@author
Administrator
*
*/
public
class
Digraph {
private
final
int
V;
private
int
E;
private Bag<Integer>[] adj;
public Digraph(int V) {
this.V=V;
this.E=0;
adj=(Bag<Integer>[])new Bag[V];
for(int v=0;v<V;v++) {
adj[v]=new Bag<Integer>();
}
}
publicint V() {
return V;
}
publicint E() {
return E;
}
//添加一条边v->w,由于是有向图只要添加一条边就可以了publicvoid addEdge(int v,int w) {
adj[v].add(w);
E++;
}
public Iterable<Integer> adj(int v) {
return adj[v];
}
//返回当前图的一个反向的图public Digraph reverse() {
Digraph R=new Digraph(V);
for(int v=0;v<V;v++) {
for(int w:adj(v)) {
R.addEdge(w, v);
}
}
return R;
}
}
三.有向图中的可达性
利用深度优先搜索可以解决有向图中的单点可达性问题:即:给定一幅有向图和一个起点s,回答是否存在一条从s到达给定顶点v的有向路径的问题.
/**
* 从指定的图中查找从s可达的所有顶点.
* 判断一个点是否是从s可达的.
*
@author
Administrator
*
*/
public
class
DirectedDFS {
private
boolean
[] marked;
//
从G中找出所有s可达的点
public DirectedDFS(Digraph G,int s) {
marked=newboolean[G.V()];
dfs(G,s);
}
//G中找出一系列点可达的点public DirectedDFS(Digraph G,Iterable<Integer> sources) {
marked=newboolean[G.V()];
for(int s:sources) {
if(!marked[s]) dfs(G,s);
}
}
//深度优先搜素判断.privatevoid dfs(Digraph G, int v) {
marked[v]=true;
for(int w:G.adj(v)) {
if(!marked[w]) dfs(G,w);
}
}
//v是可达的吗publicboolean marked(int v) {
return marked[v];
}
}
四.寻找有向环
下面的代码可以用来检测给定的有向图中是否含有有向环,如果有,则按照路径的方向返回环上的所有顶点.在执行dfs的时候,查找的是从起点到v的有向路径,onStack数组标记了递归调用的栈上的所有顶点,同时也加入了edgeTo数组,在找到有向环的时候返回环中的所有顶点.
/**
* 有向图G是否含有有向环
* 获取有向环中的所有顶点
*
@author
Administrator
*
*/
public
class
DirectedCycle {
private
boolean
[] marked;
private
int
[] edgeTo;
private Stack<Integer> cycle; //有向环中的所有顶点privateboolean[] onStack; //递归调用的栈上的所有顶点public DirectedCycle(Digraph G) {
edgeTo=newint[G.V()];
onStack=newboolean[G.V()];
marked=newboolean[G.V()];
for(int v=0;v<G.V();v++) {
if(!marked[v]) dfs(G,v);
}
}
/**
* 该算法的关键步骤在于onStack数组的运用.
* onStack数组标记的是当前遍历的点.如果对于一个点指向的所有点中的某个点
* onstack[v]=true.代表该点正在被遍历也就是说
* 该点存在一条路径,指向这个点.而这个点现在又可以指向该点,
* 即存在环的结构~
* @param G
* @param v
*/privatevoid dfs(Digraph G, int v) {
onStack[v]=true;
marked[v]=true;
for(int w:G.adj(v)) {
if(this.hasCycle()) return;
elseif(!marked[w]) {
edgeTo[w]=v;
dfs(G,w);
}
elseif(onStack[w]) {
cycle=new Stack<Integer>();
for(int x=v;x!=w;x=edgeTo[x])
cycle.push(x);
cycle.push(w);
cycle.push(v);
}
}
//dfs方法结束,对于该点的递归调用结束.该点指向的所有点已经遍历完毕
onStack[v]=false;
}
privateboolean hasCycle() {
return cycle!=null;
}
public Iterable<Integer> cycle() {
return cycle;
}
}
五.顶点的深度优先次序以及拓补排序
拓补排序:给定一幅有向图,将所有的顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素.如果存在有向环的话,那么拓补排序无法完成.
要实现有向图的拓补排序,利用标准深度优先搜索顺序即可完成任务.这里顶点会有三种排列顺序:
1.前序:在递归调用前将顶点加入队列
2.后序:在递归调用之后将顶点加入队列
3.逆后序:在递归调用之后将顶点压入栈.
具体的操作见下面的代码:
//
有向图中基于深度优先搜索的拓补排序
public
class
DepthFirstOrder {
private
boolean
[] marked;
private Queue<Integer> pre; //所有顶点的前序排列private Queue<Integer> post; //所有顶点的后序排列private Stack<Integer> reversePost;//所有顶点的逆后序排列public DepthFirstOrder(Digraph G) {
pre=new Queue<>();
post=new Queue<>();
reversePost=new Stack<>();
marked=newboolean[G.V()];
for(int v=0;v<G.V();v++) {
if(!marked[v]) dfs(G,v);
}
}
privatevoid dfs(Digraph G, int v) {
pre.enqueue(v);
marked[v]=true;
for(int w:G.adj(v)) {
if(!marked[w]) {
dfs(G,w);
}
}
post.enqueue(v);
reversePost.push(v);
}
public Iterable<Integer> pre() {
return pre;
}
public Iterable<Integer> post() {
return post;
}
public Iterable<Integer> reversePost() {
return reversePost;
}
}
拓补排序的实现依赖于上面的API,实际上拓补排序即为所有顶点的逆后序排列,证明如下:
对于任意边v->w,在调用dfs(v)的时候,下面三种情况必然有一种成立:
1.dfs(w)被调用且返回.(此时w被标记)
2.dfs(w)还没有被调用,因此v->w会返回dfs(w),且dfs(w)在dfs(v)之前返回
3.dfs(w)已经被调用没有返回,在有向无环图中这种情况不可能!
在1,2这两种情况中dfs(w)都在dfs(v)之前返回,也就是说在逆后序排列中,顺序为v,w.满足拓补排序的要求!
拓补排序的代码如下:
public
class
Topological {
private Iterable<Integer> order; //顶点的拓补排序public Topological(Digraph G) {
DirectedCycle cyclefinder=new DirectedCycle(G);
if(!cyclefinder.hasCycle()) {//只有无环才能进行拓补排序
DepthFirstOrder dfs=new DepthFirstOrder(G);
order=dfs.reversePost();
}
}
public Iterable<Integer> order() {
return order;
}
publicboolean isDAG() {
return order!=null;
}
}
六.有向图的强连通性
定义:如果两个顶点v和w是互相可达的,则称它们为强连通的.也就是说既存在一条从v到w的有向路径也存在一条从w到v的有向路径.如果一幅有向图中的任意两个顶点都是强连通的,则称这副有向图也是强连通的.任意顶点和自己都是强连通的.
强连通性将顶点分为了一些等价类,每个等价类都是由相互均为强连通的顶点的最大子集组成的.我们将这些子集称为强连通分量.需要注意的是强连通分量是基于顶点的,而并非基于边.
下面的代码采用如下步骤来计算强连通分量以及两个点是否是强连通的:
1.在给定的有向图中,使用DepthFirsetOrder来计算它的反向图GR的逆后序排列
2.按照第一步计算得到的顺序采用深度优先搜索来访问所有未被标记的点
3.在构造函数中,所有在同一个递归dfs()调用中被访问到的顶点都是在同一个强连通分量中.
下面的代码实现遵循了上面的思路:
/**
* 该算法实现的关键:
* 使用深度优先搜索查找给定有向图的反向图GR.根据由此得到的所有顶点的逆后序
* 再次用深度优先搜索处理有向图G.其构造函数的每一次递归调用所标记的顶点都在
* 同一个强连通分量中.
* 解决问题:
* 判断两个点是否是强连通的
* 判断总共有多少个连通分量
*
@author
Administrator
*
*/
public
class
KosarajuSCC {
private
boolean[] marked;//已经访问过的顶点privateint[] id; //强连通分量的标识符privateint count; //强联通分量的数量public KosarajuSCC(Digraph G) {
marked=newboolean[G.V()];
id=newint[G.V()];
DepthFirstOrder order=new DepthFirstOrder(G.reverse());
for(int s:order.reversePost()) {
if(!marked[s]) {
dfs(G,s);
count++;
}
}
}
privatevoid dfs(Digraph G, int v) {
marked[v]=true;
id[v]=count;
for(int w:G.adj(v)) {
if(!marked[w]) {
dfs(G,w);
}
}
}
publicboolean stronglyConnected(int v,int w) {
return id[v]==id[w];
}
publicint id(int v) {
return id[v];
}
publicint count() {
return count;
}
}
为了验证这个代码的正确性,需要证明这个命题,即:
使用深度优先搜索查找给定有向图的GR,根据由此得到的所有顶点的逆后序再次用深度优先搜索处理有向图G,其构造函数的每一次递归调用所标记的顶点都在同一个强连通分量中.
证明如下:
首先用反证法证明每个和s强连通的顶点v都会在构造函数中调用的dfs(G,s)中被访问到.假设有一个顶点v没有被访问到.因为存在从s到v的路径,那么说明v肯定在之前被访问过了.但是因为也存在v到s的路径,那么dfs(G,v)调用中,s肯定会被标记,因此构造函数肯定不会调用dfs(G,s)的,矛盾.
其次要证明构造函数调用的dfs(G,s)所到达的任意顶点v都必然是和s强连通的.设v为dfs(G,s)所到达的某个顶点.那么G中必然存在从s到v的路径.因此现在只需要证明在GR中存在一条从s到v的路径即可.而由于按照逆后序进行的深度优先搜索,因此在GR中进行的深度优先搜索意味着,dfs(G,v)必然在dfs(G,s)之前就结束了.这样dfs(G,v)的调用存在两种情况:
1.调用在dfs(G,s)的调用之前(并且也在dfs(G,s)的调用之前结束.这种情况不可能存在,因为在GR中存在一条从v到s的路径.
2.调用在dfs(G,s)的调用之后(并且也在dfs(G,s)的结束之前结束.这种情况说明GR中存在一条从s到v的路径.证明完成.
原文：http://www.cnblogs.com/hlhdidi/p/5960018.html
内容总结
以上是互联网集市为您收集整理的算法_有向图全部内容，希望文章能够帮你解决算法_有向图所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。