Java 程序用于在图中查找良好反馈边集

javaobject oriented programmingprogramming更新于 2024/7/30 21:32:17

图中的反馈边集是指一组边,当从图中删除时,会消除所有循环或反馈回路。换句话说,它是边的子集,当删除时,会将原始图转换为有向无环图 (DAG)。良好的反馈边集是具有最少可能边数的反馈边集。

在本教程中,我们将学习如何在图中查找良好反馈边集。

问题陈述

编写一个 Java 程序,识别并删除图中的反馈边以构建良好反馈边集。该程序应将由其顶点和边表示的图作为输入。程序的输出应为反馈边列表,或者如果未找到反馈边则给出指示

示例

输入

顶点 (v):3
边:(1, 2)、(2, 3)、(3, 1)

输出

反馈边集:(3, 1)

说明

边 (3, 1) 在图中形成循环。当我们删除此边时,图将变为有向无环图 (DAG)。

输入

顶点 (v):4
边:(1, 2)、(2, 3)、(3, 4)、(4, 1)、(2, 4)

输出

反馈边集:(3, 4)、(4, 1)

解释

当我们删除边 (3, 4) 和 (4, 1) 时,图将变为有向无环图 (DAG)。

算法

  • 步骤 1 - 创建一个名为"Graph"的类,使用 Map<Integer, List<Integer>> 类型的私有实例变量 adjacencyList 来存储图的邻接列表。

  • 步骤 2 - 实现一个构造函数 Graph(int v),使用从 1 到 v 的每个顶点的空列表初始化邻接列表。

  • 步骤 3 - 实现一个方法 setEdge(int src, int dest) 来向图添加一条新边。如果源顶点已经存在于邻接列表中,则将目标顶点添加到其邻居列表中。否则,创建一个新的邻居列表,并将其添加到邻接列表中,并以源顶点为键。

  • 步骤 4 - 实现方法 removeSinkVertices( ) 以从图中删除所有接收器顶点。遍历邻接列表中的每个顶点,并检查其邻居列表是否为空。如果是,则将其添加到接收器顶点列表中。然后,从邻接列表中删除这些接收器顶点及其对应的边。

  • 步骤 5.1 - 实现方法 hasFeedbackEdgeSet( ) 来检查图是否包含反馈边集(循环)。创建一个大小为 v + 1 的访问数组来跟踪访问过的顶点

  • 步骤 5.2 - 将标志"flag"初始化为 false。从邻接列表中获取所有顶点的集合。将该集合转换为列表 nodeList 并对其进行迭代。

  • 步骤 5.3 - 对于 nodeList 中的每个顶点索引,获取其邻居列表。将 visit[index] 设置为 1 以将其标记为已访问。

  • 步骤 5.4 - 如果邻居列表不为空,则迭代每个邻居。如果邻居之前已被访问过,则将 flag 设置为 true,表示存在反馈边。否则,将邻居标记为已访问。

  • 步骤 6 - 使用 main 方法创建一个名为"Main"的类。使用给定的顶点数 (v) 实例化 Graph 对象。

  • 步骤 6.1 - 使用 setEdge( ) 方法向图添加边。使用 removeSinkVertices 方法从图中删除接收顶点。打印结果。

示例

在示例代码中,我们构建一个图,删除接收顶点,并识别反馈边,以确定给定图中是否存在良好的反馈边集。

import java.util.*;

class Graph {
   private Map<Integer, List<Integer>> adjacencyList;
   // 图形构造函数
   public Graph(int v) {
      adjacencyList = new HashMap<>();
      for (int i = 1; i <= v; i++) {
         adjacencyList.put(i, new ArrayList<>());
      }
   }
   // 添加新边
   public void setEdge(int src, int dest) {
      if (adjacencyList.containsKey(src)) {
         // 如果源顶点已经存在于邻接列表中,则将目标顶点添加到其邻居列表中
         List<Integer> neighbors = adjacencyList.get(src);
         neighbors.add(dest);
      } else {
         List<Integer> neighbors = new ArrayList<>();
         neighbors.add(dest);
         adjacencyList.put(src, neighbors);
      }
   }
   public Graph removeSinkVertices() {
      List<Integer> sinkVertices = new ArrayList<>();
      // 查找所有汇聚顶点(没有出边的顶点)
      for (Integer vertex : adjacencyList.keySet()) {
         if (adjacencyList.get(vertex).isEmpty()) {
            sinkVertices.add(vertex);
         }
      }
      // 删除汇聚顶点及其边
      for (Integer sinkVertex : sinkVertices) {
         adjacencyList.remove(sinkVertex);
         for (List<Integer> edges : adjacencyList.values()) {
            edges.remove(sinkVertex);
         }
      }
      return this;
   }
   // 检查图是否包含反馈边集
   public boolean hasFeedbackEdgeSet() {
      int v = this.adjacencyList.size();
      boolean flag = false;
      int[] visited = new int[v + 1];
      Set<Integer> nodes = this.adjacencyList.keySet();
      List<Integer> nodeList = new ArrayList<>(nodes);
      for (int nodeIndex = 0; nodeIndex < nodeList.size(); nodeIndex++) {
         Integer index = nodeList.get(nodeIndex);
         List<Integer> neighbours = this.adjacencyList.get(index);
         visited[index] = 1;
         if (neighbours.size() != 0) {
            for (int i = 0; i < neighbours.size(); i++) {
               if (visited[neighbours.get(i)] == 1) {
                  // Found a feedback edge (cycle) in the graph
                  flag = true;
                  System.out.println(index + " -> " + neighbours.get(i));
               } else {
                  visited[neighbours.get(i)] = 1;
               }
            }
         }
      }
      return flag;
   }
}
public class Main {
   public static void main(String[] args) {
      // Number of vertices
      int v = 4;
      Graph graph = new Graph(v);
      graph.setEdge(1, 2);
      graph.setEdge(2, 3);
      graph.setEdge(3, 4);
      graph.setEdge(4, 1);
      graph.setEdge(2, 4);
      graph = graph.removeSinkVertices();
      System.out.println("Feedback Edge Set is as follows:");
      if (!graph.hasFeedbackEdgeSet()) {
         System.out.println("None");
      }
   }
}

输出

Feedback Edge Set is as follows:
3 -> 4
4 -> 1

时间复杂度:O(V*E)

由于我们需要访问每个顶点及其每条边来检查反馈边,因此时间复杂度与顶点数乘以每个顶点的平均边数成正比,结果为 O(v * e)。

结论

总之,图中良好反馈边集的概念在识别和消除图中的循环或反馈回路方面起着至关重要的作用。通过删除最小边集,我们可以将原始图转换为有向无环图 (DAG),它在网络优化、电路设计和调度等领域具有各种实际应用。


相关文章


有用资源