文档章节

有向图问题1--深度优先、广度优先遍历和拓扑排序

akane_oimo
 akane_oimo
发布于 2017/12/20 22:01
字数 1150
阅读 421
收藏 1

有向图基础

术语定义:

  • 一个顶点的出度为由该顶点指出的边的总数
  • 一个顶点的入度为指向该顶点的边的总数
  • 一条有向边的第一个顶点称为它的头,第二个顶点称为它的尾

数据结构:

使用邻接表来表示有向图,其中v->w表示为顶点v对应的邻接链表中包含一个w顶点。

算法实现:

public class Digraph {
	private int V;//顶点数
	private int E;//边数
	private Bag<Integer>[] adj;//邻接表
	public Digraph(int V) {
		this.V = V;
		adj = (Bag<Integer>[]) new Bag[V];
		for(int i=0;i<adj.length;i++)
			adj[i] = new Bag<Integer>();
	}

	public int V() {return V;}
	public int E() {return E;}
	public void addEdge(int v,int w) 
    { adj[v].add(w);	E++;}
    //顶点v所关联的所有顶点
	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;
	}
}

深度优先遍历和广度优先遍历

有向图的深度优先遍历和广度优先遍历和无向图一模一样,可以通过之前的无向图遍历问题来学习。https://my.oschina.net/HuoQibin/blog/1592318

拓扑排序

拓扑排序:给定一幅有向图,将所有顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素(或者说明无法做到这一点)。

优先级限制下不应该存在有向环,一个优先级限制的问题如果存在有向环,那么这个问题 肯定是无解的。所以先来解决有向环检测问题。

有向环检测:

采用深度优先遍历来解决这个问题:用一个栈表示“当前”正在遍历的有向路径上的顶点。一旦找到一条有向边v->w,并且w已经存在于栈中,那么就找到了一个环;如果没有找到这条边,那么就是无环图。

算法实现:

public class DirectedCycle {
    private boolean[] marked;
    private int [] edgeTo;
    private Stack<Integer> cycle;//有向环中所有顶点
    private boolean[] onStack;//递归调用栈中所有顶点

    public DirectedCycle(Digraph G) {
		//略
    }
	//修改过的深度优先遍历
    public void dfs(Digraph G,int v) {
        onStack[v] = true;
        marked[v] = true;
        for(int w: G.adj(v)){
            if(this.hasCycle())    return;    //检测出有环,算法停止
            else if(!marked[v]) {
                edgeTo[w] = v; dfs(G,w);
            }
            else if(onStack[w]) {    //如果为真,则说明形成了环,把环路经保存下来
                cycle = new Stack<Integer>();
                for(int x = v;x!= w;x=edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        }
    }

    public boolean hasCycle() {  return cycle != null;  }
    public Iterable<Integer> cycle(){  return cycle;  }
}

拓扑排序:

其实,将有向无环图的深度优先遍历的路径记录下来就是一种拓扑排序。遍历的顺序取决于数据结构的性质以及是在递归调用之前还是之后保存。一般有三种排列排序:

  • 前序:在递归调用之前将顶点加入队列
  • 后序:在递归调用之后将顶点加入队列
  • 逆后序:在递归调用之后将顶点压入栈

算法实现:

基于深度优先搜索的顶点排序:

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<Integer>();
        post = new Queue<Integer>();
        revercePost = new Stack<Integer>();
        marked = new boolean[G.V()];
        for(int v = 0; v < G.V(); v++)
            if(!marked[v]) dfs(G,v);
    }
    //深度优先遍历
    private void 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;  }
}

实现拓扑排序:

public class Tolpological {
	private Iterable<Integer> order;
	public Tolpological(Digraph G) {
		DirectedCycle cyclefinder = new DirectedCycle(G);
        //如果无有向环,则调用深度优先遍历,最后输出逆后序排列
		if(!cyclefinder.hasCycle()) {
			DepthFirstOrder dfs = new DepthFirstOrder(G);
			order = dfs.reversePost();
		}
	}
	public Iterable<Integer> order(){return order;}
}
  • 一幅有向无环图的拓扑排序即为所有顶点的逆后序排序。
  • 使用深度优先搜索对有向无环图进行拓扑排序需要的时间和V+E成正比。

 

© 著作权归作者所有

akane_oimo
粉丝 22
博文 132
码字总数 161923
作品 0
南京
其他
私信 提问
有向图----有向环检测和拓扑排序

上一篇:有向图的深度优先和广度优先遍历 优先级限制下的调度问题:给定一组需要完成的任务,以及一组关于任务完成的先后次序的优先级限制。在满足限制条件的前提下应该如何安排并完成所有任...

SuperHeroes
2017/12/21
0
0
基本算法——深度优先搜索(DFS)和广度优先搜索(BFS)

深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 一、深度优先搜索 深度优先搜索属于图算法的一种,是一个针对...

安然若知
2018/07/13
0
0
图的搜索

前言 图的搜索指的是系统化地跟随图中的边来访问图中每一个结点,并不是随意地访问图中的结点。图的搜索算法可以用来发现图的结构,许多图的算法都要求先搜索全图,可以说,图的搜索是整个图...

某昆
2017/09/16
0
0
有向图----深度优先搜索和广度优先搜索

上一篇:有向图的可达性问题 有向图的深度优先搜索和广度优先搜索与无向图的算法相同,理解了无向图的搜索完全可以实现有向图的相关搜索。 无向图的深度优先搜索 无向图的广度优先搜索 下一篇...

Superheros
2017/12/21
8
0
小蚂蚁学习数据结构(30)——图的其他知识点简介

图的遍历 图的遍历,是对图中的每个顶点都进行一次访问且仅进行一次访问。 图的深度遍历: 类似于树的先根遍历。 图的广度遍历: 优先遍历第一顶点的所有邻接点,类似树的层次遍历。 连通网的...

嗜学如命的小蚂蚁
2016/02/05
91
0

没有更多内容

加载失败,请刷新页面

加载更多

一起来学Java8(三)——方法引用

在一起来学Java8(一)——函数式编程中有一个简单的函数式编程的例子: import java.util.function.Consumer;class Person { public static void sayHello(String name) { S...

猿敲月下码
13分钟前
6
0
读书笔记:深入理解ES6(十一)

第十一章 Promise与异步编程   Promise可以实现其他语言中类似Future和Deferred一样的功能,是另一种异步编程的选择,它既可以像事件和回调函数一样指定稍后执行的代码,也可以明确指示代码...

张森ZS
36分钟前
11
0
面试官,Java8 JVM内存结构变了,永久代到元空间

在文章《JVM之内存结构详解》中我们描述了Java7以前的JVM内存结构,但在Java8和以后版本中JVM的内存结构慢慢发生了变化。作为面试官如果你还不知道,那么面试过程中是不是有些露怯?作为面试...

程序新视界
44分钟前
26
0
Elasticsearch 实战(一) - 简介

官腔 Elasticsearch,分布式,高性能,高可用,可伸缩的搜索和分析系统 基本等于没说,咱们慢慢看 1 概述 百度:我们比如说想找寻任何的信息的时候,就会上百度去搜索一下,比如说找一部自己喜...

JavaEdge
49分钟前
18
0
【jQuery基础学习】11 jQuery性能简单优化

本文转载于:专业的前端网站➦【jQuery基础学习】11 jQuery性能简单优化 关于性能优化 合适的选择器 $("#id")会直接调用底层方法,所以这是最快的。如果这样不能直接找到,也可以用find方法继...

前端老手
57分钟前
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部