Java 来在图中找到一个好的反馈边集

图中的反馈边集是指一组边，在从图中删除后，能消除所有循环或反馈环。换句话说，它是一组边的子集，当被删除时，将原始图转化为有向无环图（DAG）。好的反馈边集是拥有最小可能边数的反馈边集。

在本教程中，我们将学习如何在图中找到一个好的反馈边集。

问题陈述

编写一个Java程序，识别并移除图中的反馈边，构建一个好的反馈边集。程序应接受以顶点和边表示的图作为输入。程序的输出应为反馈边的列表，或者如果未找到反馈边，则指示。

示例示范

输入

Vertices (v): 3
Edges: (1, 2), (2, 3), (3, 1)

输出

Feedback Edge Set: (3, 1)

解释

Edge (3, 1) makes cycle in a graph. When we remove this edge, graph will become directed acyclic graph (DAG).

输入

Vertices (v): 4
Edges: (1, 2), (2, 3), (3, 4), (4, 1), (2, 4)

输出

Feedback Edge Set: (3, 4), (4, 1)

解释

When we remove edges (3, 4) and (4, 1), graph will become directed acyclic graph (DAG).

步骤

• 步骤 1 - 创建一个名为‘图(Graph)’的类，并具有一个私有实例变量adjacencyList，类型为Map>，用于存储图的邻接表。

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

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

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

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

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

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

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

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

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

示例

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

import java.util.*;

class Graph {
   private Map<Integer, List<Integer>> adjacencyList;
   // Graph Constructor
   public Graph(int v) {
      adjacencyList = new HashMap<>();
      for (int i = 1; i <= v; i++) {
         adjacencyList.put(i, new ArrayList<>());
      }
   }
   // Adding new edge
   public void setEdge(int src, int dest) {
      if (adjacencyList.containsKey(src)) {
         // If the source vertex already exists in the adjacency list, add the destination vertex to its list of neighbors
         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<>();
      // Find all sink vertices (vertices with no outgoing edges)
      for (Integer vertex : adjacencyList.keySet()) {
         if (adjacencyList.get(vertex).isEmpty()) {
            sinkVertices.add(vertex);
         }
      }
      // Remove sink vertices and their edges
      for (Integer sinkVertex : sinkVertices) {
         adjacencyList.remove(sinkVertex);
         for (List<Integer> edges : adjacencyList.values()) {
            edges.remove(sinkVertex);
         }
      }
      return this;
   }
   // Check if the graph contains a feedback edge set
   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），该图在网络优化、电路设计和调度等领域具有各种实际应用。