数据结构与算法之图的进阶(一)

简介: 数据结构与算法之图的进阶

一、有向图


在实际生活中,很多应用相关的图都是有方向性的,最直观的就是网络,可以从A页面通过链接跳转到B页面,那么a和b连接的方向是a->b,但不能说是b->a,此时我们就需要使用有向图来解决这一类问题,它和我们之前学习的无向图,最大的区别就在于连接是具有方向的,在代码的处理上也会有很大的不同。


001c0725505248fc9f71708c474d213e.png1.1 有向图的定义及相关术语


定义:

有向图是一副具有方向性的图,是由一组顶点和一组有方向的边组成的,每条方向的边都连着一对有序的顶点。


出度:

由某个顶点指出的边的个数称为该顶点的出度。


入度:

指向某个顶点的边的个数称为该顶点的入度。


有向路径:

由一系列顶点组成,对于其中的每个顶点都存在一条有向边,从它指向序列中的下一个顶点。


有向环:

一条至少含有一条边,且起点和终点相同的有向路径。


dd5068de613f4d1b89419047e6a0d566.png


一副有向图中两个顶点 v和w可能存在以下四种关系:


1.没有边相连;

2.存在从v到w的边v—>w;

3.存在从w到v的边w—>v;

4.既存在w到v的边,也存在v到w的边,即双向连接;


理解有向图是一件比较简单的,但如果要通过眼睛看出复杂有向图中的路径就不是那么容易了。


b41d1e9155ad411ab2c486d5bb5593df.png


1.2 有向图API设计


image.png


在api中设计了一个反向图,其因为有向图的实现中,用adj方法获取出来的是由当前顶点v指向的其他顶点,如果能得到其反向图,就可以很容易得到指向v的其他顶点。


1.3 有向图实现

public class Digraph { 
  //顶点数目
  private final int V;
  //边的数目
  private int E;
  //邻接表
  private Queue<Integer>[] adj;
  public Digraph(int V){
    //初始化顶点数量
    this.V = V;
    //初始化边的数量
    this.E=0;
    //初始化邻接表
    this.adj = new Queue[V];
    //初始化邻接表中的空队列
    for (int i = 0; i < adj.length; i++) {
      adj[i] = new Queue<Integer>();
    }
    }
    //获取顶点数目
    public int V(){
      return V;
    }
    //获取边的数目
    public int E(){
      return E;
    }
    //向有向图中添加一条边 v->w
    public void addEdge(int v, int w) {
      //由于有向图中边是有向的,v->w 边,只需要让w出现在v的邻接表中,而不需要让v出现在w的邻接表中
      adj[v].enqueue(w);
      //边的数目自增1
      E++;
    }
    //获取由v指出的边所连接的所有顶点
    public Queue<Integer> adj(int v){
      return adj[v];
    }
    //该图的反向图
    private Digraph reverse(){
      //创建新的有向图对象
      Digraph r = new Digraph(V);
      //遍历0~V-1所有顶点,拿到每一个顶点v
      for (int v=0;v<V;v++){
        //得到原图中的v顶点对应的邻接表,原图中的边为 v->w,则反向图中边为w->v;
        for (Integer w : adj(v)) {
          r.addEdge(w,v);
        }
      }
    return r;
  }
}

二、扑排序


在现实生活中,我们经常会同一时间接到很多任务去完成,但是这些任务的完成是有先后次序的。以我们学习java学科为例,我们需要学习很多知识,但是这些知识在学习的过程中是需要按照先后次序来完成的。从java基础,到jsp/servlet,到ssm,到springboot等是个循序渐进且有依赖的过程。在学习jsp前要首先掌握java基础和html基础,学习ssm框架前要掌握jsp/servlet之类才行。


000f8f84a6e044d2ada5186a7ac7f077.png


为了简化问题,我们使用整数为顶点编号的标准模型来表示这个案例:


143a1e94a7514e8bbd9bbe09ef5d5ec8.png


此时如果某个同学要学习这些课程,就需要指定出一个学习的方案,我们只需要对图中的顶点进行排序,让它转换为一个线性序列,就可以解决问题,这时就需要用到一种叫拓扑排序的算法。


拓扑排序:


给定一副有向图,将所有的顶点排序,使得所有的有向边均从排在前面的元素指向排在后面的元素,此时就可以明确的表示出每个顶点的优先级。下列是一副拓扑排序后的示意图:


c34d1ea1bd174c8aab3e5fef7710f5c0.png


2.1 检测有向图中的环


如果学习x课程前必须先学习y课程,学习y课程前必须先学习z课程,学习z课程前必须先学习x课程,那么一定是有问题了,我们就没有办法学习了,因为这三个条件没有办法同时满足。其实这三门课程x、y、z的条件组成了一个环:


2a358484973f45319e7a3a23a82348b6.png


因此,如果我们要使用拓扑排序解决优先级问题,首先得保证图中没有环的存在


2.1.1 检测有向环的API设计


image.png


2.1.2 检测有向环实现


在API中添加了onStack[] 布尔数组,索引为图的顶点,当我们深度搜索时:


1.在如果当前顶点正在搜索,则把对应的onStack数组中的值改为true,标识进栈;

2.如果当前顶点搜索完毕,则把对应的onStack数组中的值改为false,标识出栈;

3.如果即将要搜索某个顶点,但该顶点已经在栈中,则图中有环;


代码:


public class DirectedCycle {
  //索引代表顶点,值表示当前顶点是否已经被搜索
  private boolean[] marked;
  //记录图中是否有环
  private boolean hasCycle;
  //索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜索的有向路径上
  private boolean[] onStack;
  //创建一个检测环对象,检测图G中是否有环
  public DirectedCycle(Digraph G){
    //创建一个和图的顶点数一样大小的marked数组
    marked = new boolean[G.V()];
    //创建一个和图的顶点数一样大小的onStack数组
    onStack = new boolean[G.V()];
    //默认没有环
    this.hasCycle=false;
    //遍历搜索图中的每一个顶点
    for (int v = 0; v <G.V(); v++) {
      //如果当前顶点没有搜索过,则搜索
      if (!marked[v]){
        dfs(G,v);
      }
    }
  }
  //基于深度优先搜索,检测图G中是否有环
  private void dfs(Digraph G, int v){
    //把当前顶点标记为已搜索
    marked[v]=true;
    //让当前顶点进栈
    onStack[v]=true;
    //遍历v顶点的邻接表,得到每一个顶点w
    for (Integer w : G.adj(v)){
      //如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
      if (!marked[w]){
        dfs(G,w);
      }
    //如果顶点w已经被搜索过,则查看顶点w是否在栈中,如果在,则证明图中有环,修改hasCycle标记,结束循环
      if (onStack[w]){
        hasCycle=true;
        return;
      }
    }
    //当前顶点已经搜索完毕,让当前顶点出栈
    onStack[v]=false;
  }
  //判断w顶点与s顶点是否相通
  public boolean hasCycle(){
    return hasCycle;
  }
}
//测试代码
public class DirectedCycleTest {
  public static void main(String[] args) throws Exception {
    //创建输入流
    BufferedReader reader = new BufferedReader(new
    InputStreamReader(DirectedCycleTest.class.getClassLoader().getResourceAsStream("cycle_test.txt")));
    //读取顶点个数,初始化Graph图
    int number = Integer.parseInt(reader.readLine());
    Digraph G = new Digraph(number);
    //读取边的个数
    int roadNumber = Integer.parseInt(reader.readLine());
    //读取边,并调用addEdge方法
    for (int i = 0; i < roadNumber; i++) {
      String line = reader.readLine();
      int p = Integer.parseInt(line.split(" ")[0]);
      int q = Integer.parseInt(line.split(" ")[1]);
      G.addEdge(p, q);
    }
    //创建测试检测环对象
    DirectedCycle cycle = new DirectedCycle(G);
    //输出图中是否有环
    System.out.println(cycle.hasCycle());
  }
}


2.2 基于深度优先的顶点排序


如果要把图中的顶点生成线性序列其实是一件非常简单的事,之前我们学习并使用了多次深度优先搜索,我们会发现其实深度优先搜索有一个特点,那就是在一个连通子图上,每个顶点只会被搜索一次,如果我们能在深度优先搜索的基础上,添加一行代码,只需要将搜索的顶点放入到线性序列的数据结构中,我们就能完成这件事。


2.2.1 顶点排序API设计


image.png

2.2.2 顶点排序实现


在API的设计中,我们添加了一个栈reversePost用来存储顶点,当我们深度搜索图时,每搜索完毕一个顶点,把该顶点放入到reversePost中,这样就可以实现顶点排序。


代码:

public class DepthFirstOrder {
  //索引代表顶点,值表示当前顶点是否已经被搜索
  private boolean[] marked;
  //使用栈,存储顶点序列
  private Stack<Integer> reversePost;
  //创建一个检测环对象,检测图G中是否有环
  public DepthFirstOrder(Digraph G){
    //创建一个和图的顶点数一样大小的marked数组
    marked = new boolean[G.V()];
    reversePost = new Stack<Integer>();
    //遍历搜索图中的每一个顶点
    for (int v = 0; v <G.V(); v++) {
      //如果当前顶点没有搜索过,则搜索
      if (!marked[v]){
        dfs(G,v);
      }
    }
  }
  //基于深度优先搜索,检测图G中是否有环
  private void dfs(Digraph G, int v){
    //把当前顶点标记为已搜索
    marked[v]=true;
    //遍历v顶点的邻接表,得到每一个顶点w
    for (Integer w : G.adj(v)){
      //如果当前顶点w没有被搜索过,则递归搜索与w顶点相通的其他顶点
      if (!marked[w]){
        dfs(G,w);
      }
    }
    //当前顶点已经搜索完毕,让当前顶点入栈
    reversePost.push(v);
  }
  //获取顶点线性序列
  public Stack<Integer> reversePost(){
    return reversePost;
  }
}

2.3 拓扑排序实现


前面已经实现了环的检测以及顶点排序,那么拓扑排序就很简单了,基于一幅图,先检测有没有环,如果没有环,则调用顶点排序即可。


API设计:


image.png

代码:

public class TopoLogical {
  //顶点的拓扑排序
  private Stack<Integer> order;
  //构造拓扑排序对象
  public TopoLogical(Digraph G) {
    //创建检测环对象,检测图G中是否有环
    DirectedCycle dCycle = new DirectedCycle(G);
    if (!dCycle.hasCycle()){
      //如果没有环,创建顶点排序对象,进行顶点排序
      DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
      order = depthFirstOrder.reversePost();
    }
  }
  //判断图G是否有环
  private boolean isCycle(){
    return order==null;
  }
  //获取拓扑排序的所有顶点
  public Stack<Integer> order(){
    return order;
  }
}
//测试代码
public class TopoLogicalTest {
  public static void main(String[] args) throws Exception {
    //创建输入流
    BufferedReader reader = new BufferedReader(new
    InputStreamReader(TopoLogicalTest.class.getClassLoader().getResourceAsStream("topological_test.txt")));
    //读取顶点个数,初始化Graph图
    int number = Integer.parseInt(reader.readLine());
    Digraph G = new Digraph(number);
    //读取边的个数
    int roadNumber = Integer.parseInt(reader.readLine());
    //读取边,并调用addEdge方法
    for (int i = 0; i < roadNumber; i++) {
      String line = reader.readLine();
      int p = Integer.parseInt(line.split(" ")[0]);
      int q = Integer.parseInt(line.split(" ")[1]);
      G.addEdge(p, q);
    }
    //创建拓扑排序对象对象
    TopoLogical topo = new TopoLogical(G);
    Stack<Integer> order = topo.order();
    //遍历打印
    StringBuilder sb = new StringBuilder();
    for (Integer v : order) {
      sb.append(v+"->");
    }
    sb.deleteCharAt(sb.length()-1);
    sb.deleteCharAt(sb.length()-1);
    System.out.println(sb);
  }
}


目录
相关文章
|
算法
研究生考试.数据结构与算法之十一 图
研究生考试.数据结构与算法之十一 图
54 0
|
6月前
|
存储 算法 Python
数据结构与算法 - 图
数据结构与算法 - 图
29 0
|
7月前
|
存储 算法
数据结构与算法 图
数据结构与算法 图
31 0
|
存储 算法
第七章 图【数据结构与算法】3
第七章 图【数据结构与算法】3
74 0
|
算法 vr&ar
第七章 图【数据结构与算法】2
第七章 图【数据结构与算法】2
65 0
|
7月前
|
存储 人工智能 算法
第七章 图【数据结构与算法】【精致版】
第七章 图【数据结构与算法】【精致版】
82 0
|
算法 Java
图【数据结构与算法java】
图【数据结构与算法java】
55 0
|
存储 人工智能 算法
第七章 图【数据结构与算法】1
第七章 图【数据结构与算法】1
89 0
|
存储 算法
【数据结构与算法】图的概述(内含源码)
【数据结构与算法】图的概述(内含源码)
96 0
|
存储 算法
数据结构/数据结构与算法实验三 图的相关算法实现
数据结构/数据结构与算法实验三 图的相关算法实现
123 0
数据结构/数据结构与算法实验三 图的相关算法实现