devbox
秋刀鱼在做梦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构Java】--图、BFS、DFS、拓扑结构_拓扑图数据结构

作者：秋刀鱼在做梦 | 2024-07-23 16:45:00

赞

踩

拓扑图数据结构

目录

一、图（Graph）

1.概念

2.有向图

 3.出度、入度

4.无向图

5.简单图、多重图

6.无向完全图

 7.有向完全图

8.有权图

9.连通图

 10.连通分量（无向图）

 11.强连通图（有向图）

12.强连通分量

 13.邻接矩阵

1.基本概念

2.邻接矩阵--有权图

14.邻接表

 1.基本概念 

 2.有权图

15.图的实现

图的基础接口

 添加边addEdge

图的总边（edgesSize）

图的点的接口

图的边的接口

删除边removeEdge

完整代码

二、图的遍历

新的图接口

三、广度优先搜索（BFS）

1.图解

​编辑 2.思路

3.代码实现

四、深度优先搜索（DFS）

1.前序遍历

 2.图解

3.递归实现

 4.通过栈-----非递归实现

1）步骤

2)图解

 3）代码实现

五、AOV网（Activity On Vertex Network）

六、拓扑排序（Topological Sort） 

1.简介

 2.思路

3.代码实现

一、图（Graph）

1.概念

2.有向图

 3.出度、入度

4.无向图

 

5.简单图、多重图

6.无向完全图

 7.有向完全图

8.有权图

 

9.连通图

 10.连通分量（无向图）

 11.强连通图（有向图）

12.强连通分量

 13.邻接矩阵

1.基本概念

2.邻接矩阵--有权图

 

14.邻接表

 1.基本概念 

 2.有权图

15.图的实现

图的基础接口

  1. package graph;
  2.  
  3. public interface Graph<V,E> {
  4. //    边的数量
  5.     int edgesSize();
  6. //    顶点数量
  7.     int verticesSize();
  8.  
  9. //    添加顶点
  10.     void addVertex(V v);
  11. //    添加边（无权值）
  12.     void addEdge(V from,V to);
  13. //    添加边（有权值）
  14.     void addEdge(V from,V to,E weight);
  15.  
  16. //    删除顶点
  17.     void removeVertex(V v);
  18. //    删除边
  19.     void removeEdge(V from,V to);
  20.  
  21.     interface vertexVisitor<V>{
  22.         boolean visit(V v);
  23.     }
  24.     
  25.     void print();
  26. }

 添加边addEdge

  1.     /**
  2.      * 添加无权值的边
  3.      * @param from
  4.      * @param to
  5.      */
  6.     @Override
  7.     public void addEdge(V from, V to) {
  8.         addEdge(from,to,null);
  9.     }
  10.  
  11.     /**
  12.      * 添加有权值的边
  13.      * @param from
  14.      * @param to
  15.      * @param weight
  16.      */
  17.     @Override
  18.     public void addEdge(V from, V to, E weight) {
  19.         //根据传入的参数from找到出发点，如果不存在则创建
  20.         Vertex<V,E> fromVertex=vertices.get(from);
  21.         if (fromVertex==null){
  22.             fromVertex=new Vertex<>(from);
  23.             //将点和对应的点关系存入
  24.             vertices.put(from,fromVertex);
  25.         }
  26.         //根据传入参数to找到终点，如果找不到则创建
  27.         Vertex<V,E> toVertex=vertices.get(to);
  28.         if (toVertex==null){
  29.             toVertex=new Vertex<>(to);
  30.             //将点和对应的点关系存入
  31.             vertices.put(to,toVertex);
  32.         }
  33.         //根据出发点和终点，创建边
  34.         Edge<V,E> edge=new Edge<>(fromVertex,toVertex);
  35.         edge.weight=weight;//有权值加上，无权值则为null
  36.  
  37.         //不管原来是否存在，都先删除，在添加进去
  38.         if (fromVertex.outEdges.contains(edge)){ //说明存在
  39.             toVertex.inEdges.remove(edge);
  40.             //在整个图中的边减少
  41.             edges.remove(edge);
  42.         }
  43.         fromVertex.outEdges.add(edge);
  44.         toVertex.inEdges.add(edge);
  45.         //在整个图中的边增加
  46.         edges.add(edge);
  47.  
  48.     }

图的总边（edgesSize）

  1.     public int edgesSize() {
  2.         return edges.size();
  3.     }

图的点的接口

  1.     /**
  2.      * 顶点
  3.      * @param <V>
  4.      * @param <E>
  5.      */
  6.     private static class Vertex<V,E>{
  7.         //顶点值
  8.         V value;
  9.         Set<Edge<V,E>> inEdges=new HashSet<>();
  10.         Set<Edge<V,E>> outEdges=new HashSet<>();
  11.  
  12.         public Vertex(V value) {
  13.             this.value = value;
  14.         }
  15.  
  16.         /**
  17.          * 比较两个顶点是否相等
  18.          * @param obj
  19.          * @return
  20.          */
  21.         @Override
  22.         public boolean equals(Object obj) {
  23.             return Objects.equals(value,((Vertex<V,E>)obj).value);
  24.         }
  25.  
  26.         @Override
  27.         public int hashCode() {
  28.             return value==null ? 0: value.hashCode();
  29.         }
  30.     }

图的边的接口

  1.     /**
  2.      * 边
  3.      * @param <V>
  4.      * @param <E>
  5.      */
  6.     private static class Edge<V,E> {
  7.         Vertex<V,E> from;
  8.         Vertex<V,E> to;
  9.         E weight;
  10.  
  11.         public Edge(Vertex<V, E> from, Vertex<V, E> to) {
  12.             this.from = from;
  13.             this.to = to;
  14.         }
  15.  
  16.         /**
  17.          * 判断两条边是否相同
  18.          * @param obj
  19.          * @return
  20.          */
  21.         @Override
  22.         public boolean equals(Object obj) {
  23.             Edge<V,E> edge=(Edge<V, E>) obj;
  24.             return Objects.equals(from,edge.from) && Objects.equals(to,edge.to);
  25.         }
  26.  
  27.         /**
  28.          * 如果equals的结果是true说明一样，则hashcode值也一样
  29.          * @return
  30.          */
  31.         @Override
  32.         public int hashCode() {
  33.             return from.hashCode()+to.hashCode();
  34.         }
  35.     }

删除边removeEdge

  1.     /**
  2.      * 删除边
  3.      * @param from
  4.      * @param to
  5.      */
  6.     @Override
  7.     public void removeEdge(V from, V to) {
  8. //        根据传入的from获得起点，不存在则不需要删除
  9.         Vertex<V,E> fromVertex=vertices.get(from);
  10.         if (fromVertex ==null){
  11.             return;
  12.         }
  13. //        根据传入的to找到终点，不存在则不需要删除
  14.         Vertex<V,E> toVertex=vertices.get(to);
  15.         if (toVertex==null) return;
  16.  
  17. //        根据起点和终点获得边，然后删除
  18.         Edge<V,E> edge=new Edge<>(fromVertex,toVertex);
  19.         if (fromVertex.outEdges.remove(edge)){ //表示删除成功
  20.             toVertex.inEdges.remove(edge);
  21.             edges.remove(edge);
  22.         }
  23.     }

完整代码

  1. package graph;
  2.  
  3. import java.util.*;
  4.  
  5. public class ListGraph<V,E> implements Graph<V,E>{
  6.  
  7.     // 传入的V与顶点类Vertex的映射【要记录该点的出入是inEdges还是outEdges】
  8.     private Map<V, Vertex<V, E>> vertices = new HashMap<>();
  9.     // 边的Set集合
  10.     private Set<Edge<V, E>> edges = new HashSet<>();
  11.  
  12.     public void print(){
  13.         System.out.println("[顶点]-------------------");
  14.         vertices.forEach((V v, Vertex<V, E> vertex) -> {
  15.             System.out.println(v);
  16.             System.out.println("out-----------");
  17.             System.out.println(vertex.outEdges);
  18.             System.out.println("int-----------");
  19.             System.out.println(vertex.inEdges);
  20.         });
  21.         System.out.println("[边]-------------------");
  22.         edges.forEach((Edge<V, E> edge) -> {
  23.             System.out.println(edge);
  24.         });
  25.     }
  26.  
  27.     @Override
  28.     public int edgesSize() {
  29.         return edges.size();
  30.     }
  31.  
  32.     @Override
  33.     public int verticesSize() {
  34.         return vertices.size();
  35.     }
  36.  
  37.     @Override
  38.     public void addVertex(V v) {
  39. //        put(key,value)
  40.         vertices.put(v,new Vertex<>(v));
  41.     }
  42.  
  43.     /**
  44.      * 添加无权值的边
  45.      * @param from
  46.      * @param to
  47.      */
  48.     @Override
  49.     public void addEdge(V from, V to) {
  50.         addEdge(from,to,null);
  51.     }
  52.  
  53.     /**
  54.      * 添加有权值的边
  55.      * @param from
  56.      * @param to
  57.      * @param weight
  58.      */
  59.     @Override
  60.     public void addEdge(V from, V to, E weight) {
  61.         //根据传入的参数from找到出发点，如果不存在则创建
  62.         Vertex<V,E> fromVertex=vertices.get(from);
  63.         if (fromVertex==null){
  64.             fromVertex=new Vertex<>(from);
  65.             //将点和对应的点关系存入
  66.             vertices.put(from,fromVertex);
  67.         }
  68.         //根据传入参数to找到终点，如果找不到则创建
  69.         Vertex<V,E> toVertex=vertices.get(to);
  70.         if (toVertex==null){
  71.             toVertex=new Vertex<>(to);
  72.             //将点和对应的点关系存入
  73.             vertices.put(to,toVertex);
  74.         }
  75.         //根据出发点和终点，创建边
  76.         Edge<V,E> edge=new Edge<>(fromVertex,toVertex);
  77.         edge.weight=weight;//有权值加上，无权值则为null
  78.  
  79.         //不管原来是否存在，都先删除，在添加进去
  80.         if (fromVertex.outEdges.contains(edge)){ //说明存在
  81.             toVertex.inEdges.remove(edge);
  82.             //在整个图中的边减少
  83.             edges.remove(edge);
  84.         }
  85.         fromVertex.outEdges.add(edge);
  86.         toVertex.inEdges.add(edge);
  87.         //在整个图中的边增加
  88.         edges.add(edge);
  89.  
  90.     }
  91.  
  92.     /**
  93.      * 删除点
  94.      * @param v
  95.      */
  96.     @Override
  97.     public void removeVertex(V v) {
  98.         //根据传入的值找到点并且删除，不存在则不做操作
  99.         Vertex<V,E> vertex=vertices.remove(v);
  100.         if (vertex==null) return;
  101. //        迭代器遍历集合vertex.outEdges，删除所有从该点出去的边
  102. //        iterator.hasNext():相当于i++
  103.         for (Iterator<Edge<V,E>> iterator = vertex.inEdges.iterator();iterator.hasNext();){
  104.             Edge<V,E> edge=iterator.next();//遍历从该点出去的边
  105.             edge.to.inEdges.remove(edge);//获取终点进入的边，并从中删除遍历到的边
  106.             //这个remove方法是将当前的这个边删除
  107.             iterator.remove();//将当前遍历到当前遍历到的元素edge从集合vertex.outEdges中删除
  108.             edges.remove(edge);
  109.         }
  110.         // 迭代器遍历集合vertex.inEdges, 删除所有进入该点的边
  111.         for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext();) {
  112.             Edge<V, E> edge = iterator.next(); // 遍历到的进入该点的边
  113.             edge.from.outEdges.remove(edge); // 获取起点出去的边,并从中删除遍历到的边
  114.             iterator.remove(); // 将当前遍历到的元素edge从集合vertex.inEdges中删掉
  115.             edges.remove(edge);
  116.         }
  117.     }
  118.  
  119.     /**
  120.      * 删除边
  121.      * @param from
  122.      * @param to
  123.      */
  124.     @Override
  125.     public void removeEdge(V from, V to) {
  126. //        根据传入的from获得起点，不存在则不需要删除
  127.         Vertex<V,E> fromVertex=vertices.get(from);
  128.         if (fromVertex ==null){
  129.             return;
  130.         }
  131. //        根据传入的to找到终点，不存在则不需要删除
  132.         Vertex<V,E> toVertex=vertices.get(to);
  133.         if (toVertex==null) return;
  134.  
  135. //        根据起点和终点获得边，然后删除
  136.         Edge<V,E> edge=new Edge<>(fromVertex,toVertex);
  137.         if (fromVertex.outEdges.remove(edge)){ //表示删除成功
  138.             toVertex.inEdges.remove(edge);
  139.             edges.remove(edge);
  140.         }
  141.     }
  142.  
  143.     /**
  144.      * 顶点
  145.      * @param <V>
  146.      * @param <E>
  147.      */
  148.     private static class Vertex<V,E>{
  149.         //顶点值
  150.         V value;
  151.         Set<Edge<V,E>> inEdges=new HashSet<>();
  152.         Set<Edge<V,E>> outEdges=new HashSet<>();
  153.  
  154.         public Vertex(V value) {
  155.             this.value = value;
  156.         }
  157.  
  158.         /**
  159.          * 比较两个顶点是否相等
  160.          * @param obj
  161.          * @return
  162.          */
  163.         @Override
  164.         public boolean equals(Object obj) {
  165.             return Objects.equals(value,((Vertex<V,E>)obj).value);
  166.         }
  167.  
  168.         @Override
  169.         public int hashCode() {
  170.             return value==null ? 0: value.hashCode();
  171.         }
  172.     }
  173.  
  174.     /**
  175.      * 边
  176.      * @param <V>
  177.      * @param <E>
  178.      */
  179.     private static class Edge<V,E> {
  180.         Vertex<V,E> from;
  181.         Vertex<V,E> to;
  182.         E weight;
  183.  
  184.         public Edge(Vertex<V, E> from, Vertex<V, E> to) {
  185.             this.from = from;
  186.             this.to = to;
  187.         }
  188.  
  189.         /**
  190.          * 判断两条边是否相同
  191.          * @param obj
  192.          * @return
  193.          */
  194.         @Override
  195.         public boolean equals(Object obj) {
  196.             Edge<V,E> edge=(Edge<V, E>) obj;
  197.             return Objects.equals(from,edge.from) && Objects.equals(to,edge.to);
  198.         }
  199.  
  200.         /**
  201.          * 如果equals的结果是true说明一样，则hashcode值也一样
  202.          * @return
  203.          */
  204.         @Override
  205.         public int hashCode() {
  206.             return from.hashCode()+to.hashCode();
  207.         }
  208.     }
  209. }

二、图的遍历

图的遍历

从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次
图有2种常见的遍历方式（有向图、无向图都适用）

  • 广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索、横向优先搜索。
  • 深度优先搜索（Depth First Search，DFS）

发明“深度优先搜索”算法的2位科学家在1986年共同获得计算机领域的最高奖：图灵奖。

新的图接口

  1. package graph;
  2.  
  3. import java.util.List;
  4. import java.util.Set;
  5.  
  6. public interface Graph<V,E> {
  7. //    边的数量
  8.     int edgesSize();
  9. //    顶点数量
  10.     int verticesSize();
  11.  
  12. //    添加顶点
  13.     void addVertex(V v);
  14. //    添加边（无权值）
  15.     void addEdge(V from,V to);
  16. //    添加边（有权值）
  17.     void addEdge(V from,V to,E weight);
  18.  
  19. //    删除顶点
  20.     void removeVertex(V v);
  21. //    删除边
  22.     void removeEdge(V from,V to);
  23.  
  24.     void print();
  25.  
  26.  
  27.  
  28.     void bfs(V begin, vertexVisitor<V> visitor); // 广度优先搜索
  29.  
  30.  
  31.     /**
  32.      * 非递归版的深度优先搜索
  33.      * @param begin
  34.      * @param visitor
  35.      */
  36.     void dfs(V begin, vertexVisitor<V> visitor);
  37.  
  38.  
  39.     List<V> topologicalSort(); // 拓扑排序
  40.  
  41.     interface vertexVisitor<V>{
  42.         boolean visit(V v);
  43.     }
  44. }

三、广度优先搜索（BFS）

1.图解

之前所学的二叉树层序遍历就是一种广度优先搜索。

注：BFS结果不唯一。

经历一层可以访问到的

 2.思路

将该点从队列取出来，然后再将其所子节点依次放入队列

从某个点开始，将它可以到达的点放入队列，如果已经访问过则跳过，然后从队列中取出点重复该过程。

第一层：假设从点A开始，它可以到达B、F，则将B、F入队。
此时队列中元素 [B、F]
第二层：队头B出队，B可以到达C、I、G，将C、I、G入队。
此时队列中元素 [F、C、I、G]
第三层：队头F出队，F可以到达G、E，但G已访问过，将E入队。
此时队列中元素 [C、I、G、E]
第四层：队头C出队，C可以到达I、D，但I已访问过，将D入队。
此时队列中元素 [I、G、E、D]
第五层：队头I出队，I可以到达D，但D已访问过，不执行操作。
此时队列中元素 [G、E、D]
第六层：队头G出队，G可以到达D、H，但D已访问过，将H入队。
此时队列中元素 [E、D、H]
第七层：队头E出队，E可以到达D、H、F，都访问过，不执行操作。
此时队列中元素 [D、H]
第八层：队头D出队，D可以到达C、H、E，都访问过，不执行操作。
此时队列中元素 [H]
第九层：队头H出队，H可以到达D、G、E，都访问过，不执行操作。
此时队列中元素 []
队列为空，广度优先搜索结束。

3.代码实现

  1.     /**
  2.      * 广度优先搜索:BFS
  3.      * @param begin
  4.      * @param visitor
  5.      */
  6.     @Override
  7.     public void bfs(V begin, vertexVisitor<V> visitor) {
  8.         if (visitor ==null) return;
  9.         //根据传入的值begin找到顶点
  10.         Vertex<V,E> beginVertex=vertices.get(begin);
  11.         //该顶点不存在，不做操作
  12.         if (beginVertex==null) return;
  13.  
  14.         //存放已经访问过的节点
  15.         //因为如果不存放，则遍历到下一个顶点的时候，会将刚刚出队列的数值再一次放入
  16.         Set<Vertex<V,E>> visitedVertices=new HashSet<>();
  17.         //临时存放
  18.         Queue<Vertex<V,E>> queue=new LinkedList<>();
  19.         queue.offer(beginVertex); //元素入队
  20.         //将已经加入过队列的元素标记一下
  21.         visitedVertices.add(beginVertex);
  22.  
  23.         //思考参考二叉树层次遍历，队列存放每一层的顶点，用集合记录已经访问过的点
  24.         while (!queue.isEmpty()){
  25.             //从队列中取出第一个顶点
  26.             Vertex<V,E> vertex=queue.poll();
  27.             if (visitor.visit(vertex.value)) return;
  28.             //遍历【从队列中取出的顶点】的出去的边，将【这些边的终点】入队，并且标记为已经访问过
  29.             for (Edge<V,E> edge:vertex.outEdges){
  30.                 //如果集合中已经记录该顶点，说明已经访问过，跳过进行下一轮
  31.                 if (visitedVertices.contains(edge.to)) continue;
  32.                 queue.offer(edge.to);
  33.                 visitedVertices.add(edge.to);
  34.             }
  35.         }
  36.     }

四、深度优先搜索（DFS）

之前所学的二叉树前序遍历就是一种深度优先搜索。

注：DFS结果不唯一。

1.前序遍历

 2.图解

 

3.递归实现

  1.     /**
  2.      * 递归实现--->深度优先遍历：DFS
  3.      * @param begin
  4.      * @param visitedVertices 已经访问过的节点
  5.      */
  6.     /**
  7.      * 递归实现深度优先搜索DFS
  8.      */
  9.     public void dfs(V begin) {
  10.         Vertex<V, E> beginVertex = vertices.get(begin); // 根据传入的值获取顶点
  11.         if (beginVertex == null) return; // 顶点不存在则不执行操作
  12.         dfs(beginVertex, new HashSet<>()); // 传入的集合,用来记录访问过的顶点
  13.     }
  14.     private void dfs(Vertex<V, E> vertex, Set<Vertex<V, E>> vistedVertices){
  15.         System.out.println(vertex.value);
  16.         vistedVertices.add(vertex);
  17.  
  18.         for(Edge<V, E> edge : vertex.outEdges){
  19.             if(vistedVertices.contains(edge.to)) continue;
  20.             //dfs会自己后退
  21.             dfs(edge.to, vistedVertices);
  22.         }
  23.     }

 4.通过栈-----非递归实现

1）步骤

1.从outEdge中选择一条边

2.将选择边的from和to边，按顺序入栈【先入from再入to】

3.打印选择边的to

4.将to边添加到已经访问的范围中

5.break

2)图解

 3）代码实现

  1.     /**
  2.      * 非递归版（通过栈实现）：深度优先搜索（DFS）
  3.      * @param
  4.      */
  5.  
  6.     @Override
  7.     public void dfs(V begin, vertexVisitor<V> visitor) {
  8.         if (visitor ==null) return;
  9.  
  10.         //查看该点是否存在
  11.         Vertex<V,E> beginVertex=vertices.get(begin);
  12.         if (begin==null) return;
  13.         //创建一个set存放已经访问过的节点
  14.         Set<Vertex<V,E>> visitedVertices=new HashSet<>();
  15.         //创建一个栈临时存放
  16.         Stack<Vertex<V,E>> stack=new Stack<>();
  17.  
  18.         //先访问起点
  19.         stack.push(beginVertex);
  20.         visitedVertices.add(beginVertex);
  21.         //如果该节点已经访问过，则不再放入
  22.         if (visitor.visit(begin)) return;
  23.  
  24.         while (!stack.isEmpty()){ //如果栈不为空
  25.             Vertex<V,E> vertex=stack.pop();
  26.  
  27.             for (Edge<V,E> edge :vertex.outEdges){ //访问出发点的每一条边
  28.                 if (visitedVertices.contains(edge.to)) continue; //表示这条边已经访问过
  29.                 //找了一条适合且未遍历过的边
  30.                 stack.push(edge.from);//将出发点加入栈中
  31.                 stack.push(edge.to);//将出度点加入栈中
  32.                 //将加入栈中的节点加入已经访问过发范围中
  33.                 visitedVertices.add(edge.to);
  34.                 if (visitor.visit(edge.to.value)) return;
  35.                 break;
  36.             }
  37.         }
  38.     }

五、AOV网（Activity On Vertex Network）

一项大的工程常被分为多个小的子工

子工程之间可能存在一定的先后顺序，即某些子工程必须在其他的一些子工程完成后才能开始。
在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，子工程被称为活动（Activity）

以顶点表示活动、有向边表示活动之间的先后关系，这样的图简称为 AOV 网。【有很强的依赖关系】
标准的AOV网必须是一个有向无环图（Directed Acyclic Graph，简称 DAG）

六、拓扑排序（Topological Sort） 

1.简介

前驱活动：有向边起点的活动称为终点的前驱活动

  • 只有当一个活动的前驱全部都完成后，这个活动才能进行

后继活动：有向边终点的活动称为起点的后继活动

 2.思路

可以使用卡恩算法（Kahn于1962年提出）完成拓扑排序。

假设 L 是存放拓扑排序结果的列表：

  • ① 把所有入度为 0 的顶点放入 queue 中，然后把这些顶点从图中去掉，放入list中
  • ② 然后找到已经从queue中移除的入度为0的节点的下一个节点，将下一个节点的入度-1，如果-1后，入度为0，则直接加入queue
  • ③ 重复操作 ①，直到找不到入度为 0 的顶点
  • 如果此时 L 中的元素个数和顶点总数相同，说明拓扑排序完成
  • 如果此时 L 中的元素个数少于顶点总数，说明原图中存在环，无法进行拓扑排序

3.代码实现

  1.     /**
  2.      * 拓扑排序
  3.      * @return
  4.      */
  5.     @Override
  6.     public List<V> topologicalSort() {
  7.         List<V> list = new ArrayList<>();
  8.         Queue<Vertex<V, E>> queue = new LinkedList<>();
  9.         Map<Vertex<V, E>, Integer> ins = new HashMap<>();
  10.  
  11.         // 初始化（将度为0的节点放入队列）
  12.         vertices.forEach((V v, Vertex<V, E> vertex) -> {
  13.             int indegree = vertex.inEdges.size(); // 入度
  14.             if(indegree == 0) { // 入度为0，放入队列
  15.                 queue.offer(vertex);
  16.             } else { // 入度不为0，用map记录它的入度
  17.                 ins.put(vertex, indegree);
  18.             }
  19.         });
  20.  
  21.         while(!queue.isEmpty()){ // 从队列中取节点
  22.             //取出队列中的第一个元素
  23.             Vertex<V, E> vertex = queue.poll();
  24.             list.add(vertex.value); // 放入返回结果中
  25.  
  26.             //遍历取出的节点的出度边
  27.             for (Edge<V, E> edge : vertex.outEdges){
  28.                 // 队列中取出节点所通向节点的入度
  29.                 int toIndegree = ins.get(edge.to) - 1;
  30.                 if(toIndegree == 0) { // 入度为0，放入队列
  31.                     queue.offer(edge.to);
  32.                 } else { // 入度不为0，用map记录它的入度
  33.                     ins.put(edge.to, toIndegree);
  34.                 }
  35.             }
  36.         }
  37.  
  38.         return list;
  39.     }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/870726
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号