資料結構
網路
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
