数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学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 − 如果邻居列表不为空，则遍历每个邻居。如果之前已访问过该邻居，则将flag设置为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)，这在网络优化、电路设计和调度等领域具有各种实际应用。
浏览量 182
