有向图

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

有向图的定义及相关术语

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

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

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

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

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

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

  1. 没有边相连
  2. 存在从v到w的边v->w
  3. 存在从w到v的边w->v
  4. 既存在w到v的边,又存在v到w的边,即双向连接

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

有向图API设计

类名Digraph
构造方法Digraph(int V):创建一个包含V个顶点但不包含边的有向图
成员方法1.public int V():获取图中顶点的数量 2.public int E():获取图中边的数量 3.public void addEdge(int v,int w):向有向图中添加一条边v->w 4.public Queue adj(int v):获取由v指出的边所连接的所有顶点 5.private Digraph reverse():该图的反向图
成员变量1.private final int V:记录顶点数量 2.private int E:记录边数量 3.private Queue[] adj:邻接表

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

有向图实现

Digraph

public class Digraph {

  /**
   * 顶点数目
   */
  private final int V;
  /**
   * 边的数目
   */
  private int E;
  /**
   * 邻接表
   */
  private Queue<Integer>[] adj;

  /**
   * 创建一个包含V个顶点但不包含边的有向图
   */
  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) {
    //只需要让顶点w出现在顶点的邻接表中,因为边是有方向的,邻接表的含义就是:v-->其他顶点
    adj[v].enqueue(w);
    //边的数目+1
    E++;
  }

  /**
   * 获取由v指出的边所连接的所有顶点
   */
  public Queue<Integer> adj(int v) {
    return adj[v];
  }

  /**
   * 该图的反向图
   */
  private Digraph reverse() {
    //创建有向图对象
    Digraph r = new Digraph(V);
    //遍历原图中的每一个顶点
    for (int v = 0; v < V; v++) {
      //获取该顶点v所指出的所有的边w
      for (Integer w : adj[v]) {
        //再反向连接回v
        r.addEdge(w, v);
      }
    }
    return r;
  }
}

拓扑排序

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

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

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

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

检测有向图中的环

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

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

检测有向环的API设计

类名DirectedCycle
构造方法DirectedCycle(Digraph G):创建一个检测环对象,检测图G中是否有环
成员方法1.private void dfs(Digraph G,int v):基于深度优先搜索,检测图G中是否有环 2.public boolean hasCycle():判断图中是否有环
成员变量1.private boolean[] marked:索引代表顶点,值表示当前顶点是否已经被搜索 2.private boolean hasCycle:记录图中是否有环 3.private boolean[] onStack:索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜索的有向路径上

检测有向环实现

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

  1. 在如果当前顶点正在搜索,则把对应的onStack数组中的值改为true,标识进栈
  2. 如果当前顶点搜索完毕,则把对应的onStack数组中值改为false,标识出栈
  3. 如果即将要搜索某个顶点,但该顶点已经在栈中,则图中有环

代码实现

DirectedCycle

public class DirectedCycle {

  /**
   * 索引代表顶点,值表示当前顶点是否已经被搜索
   */
  private boolean[] marked;
  /**
   * 记录图中是否有环
   */
  private boolean hasCycle;
  /**
   * 索引代表顶点,使用栈的思想,记录当前顶点有没有已经处于正在搜多的有向路径上
   */
  private boolean[] onStack;

  /**
   * 创建一个检测环对象,检测图G中是否有环
   */
  public DirectedCycle(Digraph G) {
    //初始化marked数组
    this.marked = new boolean[G.V()];
    //初始化hasCycle
    this.hasCycle = false;
    //初始化onStack数组
    this.onStack = new boolean[G.V()];
    //找到图中每一个顶点,让每一个顶点作为入口进行环的查找
    for (int v = 0; v < G.V(); v++) {
      //判断一下当前顶点有没有被搜索过,如果没被搜索过,则调用dfs进行搜索
      if (!marked[v]) {
        dfs(G, v);
      }
    }
  }

  /**
   * 基于深度优先搜索,检测图G中是否有环
   */
  private void dfs(Digraph G, int v) {
    //把当前顶点标识为已经搜索
    marked[v] = true;
    //把当前顶点进栈
    onStack[v] = true;
    //进行深度搜索
    for (Integer w : G.adj(v)) {
      //判断当前顶点w是否被搜索过,如果没有搜索过,则递归调用dfs
      if (marked[w] && w != null) {
        dfs(G, w);
      }
      //如果已经被搜索过,则判断当前顶点是否在栈stack中,如果在,则说明存在环
      if (onStack[w]) {
        hasCycle = true;
        return;
      }
    }
    //当前顶点出栈
    onStack[v] = false;
  }

  /**
   * 判断w顶点与s顶点是否相通
   */
  public boolean hasCycle() {
    return hasCycle;
  }
}

基于深度优先的顶点排序

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

顶点排序API设计

类名DepthFirstOrder
构造方法DepthFirstOrder(Digraph G):创建一个顶点排序对象,生成顶点线性序列
成员方法1.private void dfs(Digraph G,int v):基于深度优先搜索,生成顶点线性序列 2.public Stack reversePost():获取顶点线性序列
成员变量1.private boolean[] marked:索引代表顶点,值表示当前顶点是否已经被搜索 2.private Stack reversePost:使用栈,存储顶点序列

顶点排序实现

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

代码实现

DepthFirstOrder

public class DepthFirstOrder {

  /**
   * 索引代表顶点,值表示当前顶点是否已经被搜索
   */
  private boolean[] marked;
  /**
   * 使用栈,存储顶点序列
   */
  private Stack<Integer> reversePost;

  /**
   * 创建一个检测环对象,检测图G中是否有环
   */
  public DepthFirstOrder(Digraph G) {
    //初始化marked数组
    this.marked = new boolean[G.V()];
    //初始化reversePost栈
    this.reversePost = new Stack<Integer>();
    //遍历图中的每一个顶点,让每一个顶点作为入口,从而完成一次深度优先搜索
    for (int v = 0; v < G.V(); v++) {
      //判断当前顶点是否已经搜索过,如果已经搜索过,则不搜索了
      if (!marked[v]) {
        dfs(G, v);
      }
    }
  }

  /**
   * 基于深度优先搜索,把顶点排序
   */
  private void dfs(Digraph G, int v) {
    //标记当前v已经被搜索过了
    marked[v] = true;
    //通过循环深度搜索顶点v
    for (Integer w : G.adj(v)) {
      //如果当前顶点w没有被搜索,则递归调用dfs
      if (!marked[w]) {
        dfs(G, w);
      }
    }
    //让顶点v进栈
    reversePost.push(v);
  }

  /**
   * 获取顶点线性序列
   */
  public Stack<Integer> reversePost() {
    return reversePost;
  }
}

拓扑排序

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

API设计:

类名TopoLogical
构造方法TopoLogical(Digraph G):构造拓扑排序对象
成员方法1.public boolean isCycle:判断图G是否有环 2.public Stack order:获取拓扑排序的所有顶点
成员变量1.private Stack order:顶点的拓扑排序

代码实现

TopoLogical

public class TopoLogical {

  /**
   * 顶点的拓扑排序
   */
  private Stack<Integer> order;

  /**
   * 构造拓扑排序对象
   */
  public TopoLogical(Digraph G) {
    //创建检测有向环的对象
    DirectedCycle cycle = new DirectedCycle(G);
    //判断G图中是否有环,如果没有环,则进行顶点排序
    if (!cycle.hasCycle()) {
      DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
      order = depthFirstOrder.reversePost();
    }
  }

  /**
   * 判断图G是否有环
   */
  private boolean isCycle() {
    //如果有环,order不会排序,则会默认为null
    return order == null;
  }

  /**
   * 获取拓扑排序的所有顶点
   */
  public Stack<Integer> order() {
    return order;
  }
}

TopoLogicalTest

public static void main(String[] args) {
    //准备一副有向图
    Digraph digraph = new Digraph(6);
    digraph.addEdge(0, 2);
    digraph.addEdge(0, 3);
    digraph.addEdge(2, 4);
    digraph.addEdge(3, 4);
    digraph.addEdge(4, 5);
    digraph.addEdge(1, 3);
    //通过TopoLogical对有向图中的顶点进行排序
    TopoLogical topoLogical = new TopoLogical(digraph);
    //获取顶点的线性序列并对其进行打印
    Stack<Integer> order = topoLogical.order();
    StringBuilder sb = new StringBuilder();
    for (Integer i : order) {
      sb.append(i + "-->");
    }
    String str = sb.toString();
    int index = str.lastIndexOf("-->");
    str = str.substring(0, index);
    System.out.println(str);
  }

加权无向图

加权无向图是一种为每条边关联一个权重值或是成本的图模型,这种图能自然地表示许多应用,在一副航空图中,边表示航线,权值则可以表示距离或是费用,在一副电路图中,边表示导线,权值则可能表示导线的长度即成本,或是信号通过这条边所需的时间,此时我们很容易就能想到,最小成本的问题,例如从西安飞往纽约,怎样飞才能使时间成本最低或者是金钱成本最低

在下图中,从顶点0到顶点4有三条路径,分别为0-2-3-4,0-2-4,0-5-3-4,那我们如果要通过哪条路径到达4顶点最好呢?此时就应该考虑哪条路径的成本最低

加权无向图边的表示

加权无向图中的边我们就不能简单的使用v-w两个顶点表示了,而必须要关联一个权重值,因此我们可以使用对象来描述一条边

API设计:

类名Edge implements Comparable
构造方法Edge(int v,int w,double weight):通过顶点v和w,以及权重weight值构造一个边对象
成员方法1.public double weight():获取边的权重值 2.public int either():获取边上的一个点 3.public int other(int vertex):获取边上除了顶点vertex外的另外一个顶点 4.public int compareTo(Edge that):比较当前边和参数that边的权重,如果当前边权重大,返回1,如果一样大,返回0,如果当前权重小,返回-1
成员变量1.private final int v:顶点一 2.private final int w:顶点w 3.private final double weight:当前边的权重

代码实现

Edge

public class Edge implements Comparable<Edge> {


  /**
   * 顶点一
   */
  private final int v;
  /**
   * 顶点二
   */
  private final int w;
  /**
   * 当前边的权重
   */
  private final double weight;

  /**
   * 通过顶点v和w,以及权重weight值构造一个边对象
   */
  public Edge(int v, int w, double weight) {
    this.v = v;
    this.w = w;
    this.weight = weight;
  }

  /**
   * 获取边的权重值
   */
  public double weight() {
    return weight;
  }

  /**
   * 获取边上的一个点
   */
  public int either() {
    return v;
  }

  /**
   * 获取边上除了顶点vertex外的另一个顶点
   */
  public int other(int vertex) {
    if (vertex == v) {
      return w;
    } else {
      return v;
    }
  }

  @Override
  public int compareTo(Edge that) {
    //使用一个遍历记录比较的结果
    int cmp;
    if (this.weight() > that.weight()) {
      //如果当前边的权重值大,则cpm=1
      cmp = 1;
    } else if (this.weight() < that.weight()) {
      //如果当前边的权重值小,则cmp=-1
      cmp = -1;
    } else {
      //如果当前边的权重值与that值一样大,则cmp=0
      cmp = 0;
    }
    return cmp;
  }
}

加权无向图的实现

之前我们已将完成了无向图,在无向图的基础上,我们只需要把边的表示切换成Edge对象即可

API设计:

类名EdgeWeightedGraph
构造方法EdgeWeightedGraph(int V):创建一个含有V个顶点的空加权无向图
成员方法1.public int V():获取图中顶点的数量 2.public int E():获取图中边的数量 3.public void addEdge(Edge e):向加权无向图中添加一条边e 4.public Queue adj(int v):获取和顶点v关联的所有边 5.public Queue edges():获取加权无向图的所有边
成员变量1.private final int V:记录顶点的数量 2.private int E:记录边数量 3.private Queue []adj:邻接表

代码实现

EdgeWeightedGraph

public class EdgeWeightedGraph {

  /**
   * 顶点总数
   */
  private final int V;
  /**
   * 边的总数
   */
  private int E;
  /**
   * 邻接表
   */
  private Queue<Edge>[] adj;

  /**
   * 创建一个含有V个顶点的空加权无向图
   */
  public EdgeWeightedGraph(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<Edge>();
    }
  }

  /**
   * 获取图中顶点的数量
   */
  public int V() {
    return V;
  }

  /**
   * 获取图中边的数量
   */
  public int E() {
    return E;
  }

  /**
   * 向加权无向图中添加一条边e
   */
  public void addEdge(Edge e) {
    //需要让e同时出现在e的两个顶点的邻接表中
    int v = e.either();
    int w = e.other(v);
    adj[v].enqueue(e);
    adj[w].enqueue(e);
    //边的数目+1
    E++;
  }

  /**
   * 获取和顶点v相关的所有边
   */
  public Queue<Edge> adj(int v) {
    return adj[v];
  }

  /**
   * 获取加权无向图的所有边
   */
  public Queue<Edge> edges() {
    //创建一个队列对象来存储所有的边
    Queue<Edge> allEdges = new Queue<>();
    //遍历图中的每一个顶点,找到该顶点的邻接表,邻接表中存储了该顶点关联的所有边
    //但需要注意的是,因为是无向图,所以1-->2==2-->1,所以我们需要判断该边是否找到了2次
    for (int i = 0; i < V; i++) {
      //遍历i顶点的邻接表,这里的adj是adj方法而非adj变量,其实用adj[i]也可,因为adj方法也是返回adj[i]
      for (Edge e : adj(i)) {
        //如果另外个顶点大于当前顶点,则添加
        if (e.other(i) < i) {
          allEdges.enqueue(e);
        }
      }
    }
    return allEdges;
  }
}
Last modification:July 19th, 2021 at 06:38 pm