打印无向图中循环的边
Print edges of a cycle in an undirected graph
我有一个无向图，它作为邻接矩阵加载。我有一种使用 BFS 算法检测图中循环的方法。我想要实现的是以指示已找到的循环的方式打印所有边缘。
我能够打印图形中的所有边，但我无法只打印那些创建循环的边。我如何让它发挥作用？
这是图形实现：
边缘：
public class Edge {
int source, dest;
public Edge(int source, int dest) {
this.source = source;
this.dest = dest;
}
}
图表：
public class Graph {
// A List of Lists to represent an adjacency list
// Each insideList contains pointers to the next vertex
// list with an index of 1 (vertex 1) contains elements 2 and 3 (where 2, 3 are vertices connected to 1)
List<List<Integer>> adjList = null;
// Constructor
public Graph(List<Edge> edges, int N) {
adjList = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}
// add edges to the undirected graph
for (Edge edge : edges) {
int src = edge.source;
int dest = edge.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
节点：
public class Node {
int v, parent;
public Node(int v, int parent) {
this.v = v;
this.parent = parent;
}
}
算法与测试：
public class GraphTest {
// Perform BFS on graph starting from vertex src and
// returns true if cycle is found in the graph
// while traversing the graph, it should display the edges which create a cycle, but I am unable to do it (the result is wrong)
public static boolean BFS(Graph graph, int src, int N) {
// stores booleans if a vertex is discovered or not
boolean[] discovered = new boolean[N];
// mark source vertex as discovered
discovered[src] = true;
// create a queue used to do BFS and
// push source vertex into the queue
Queue<Node> q = new ArrayDeque<>();
q.add(new Node(src, -1));
// run till queue is not empty
while (!q.isEmpty()) {
// pop front node from queue and print it
Node node = q.poll();
// do for every edge (v -> u)
for (int u : graph.adjList.get(node.v)) {
if (!discovered[u]) {
// mark it as discovered
discovered[u] = true;
// construct the queue node containing info
// about vertex and push it into the queue
System.out.println(node.v + " -- " + u);
q.add(new Node(u, node.v));
}
// u is discovered and u is not a parent
else if (u != node.parent) {
// we found a cross-edge ie. cycle is found
return true;
}
}
}
// No cross-edges found in the graph
return false;
}
// Check if an undirected graph contains cycle or not
public static void main(String[] args) {
// In my case I load an adjacency matrix from file and then perform an action to create Edges.
// 0 1 1 0
// 1 0 1 0
// 1 1 0 1
// 0 0 1 0
// Edge(1, 2), Edge(2, 3), Edge(3, 1), Edge(3, 4)
// Edge(3, 1) introduces a cycle in the graph
List<Edge> edges = new ArrayList<Edge>();
ArrayList<ArrayList<Integer>> matrixList = loadFromFile(filePath);
System.out.println("Graph: (Adjacency Matrix)");
for (int i = 0; i < matrixList.size(); i++) {
for (int j = 0; j < matrixList.size(); j++) {
System.out.print(matrixList.get(i).get(j) + " ");
}
System.out.println();
}
System.out.println("All the edges: ");
for (int i = 0; i < matrixList.size(); i++) {
// ' + 1' is added so as to start vertices from 1 instead of 0
int temp = i + 1;
for (int j = 0; j < matrixList.size(); j++) {
if (matrixList.get(i).get(j) == 1) {
System.out.println(temp + "--" + (j + 1) + " ");
// each edge is added one-way only since it is an undirected graph
// if Edge(1,3) is already present, Edge(3,1) is not added
boolean isFound = false;
for (Edge e : edges) {
if (e.dest == temp && e.source == (j + 1)) {
isFound = true;
}
}
if (!isFound)
edges.add(new Edge(temp, j + 1));
}
}
System.out.println();
}
// sets number of vertices in the graph
final int N = 5;
// creates a graph from edges
Graph graph = new Graph(edges, N);
boolean[] discovered = new boolean[N];
// do BFS traversal in connected components of graph
System.out.println("Detect a cycle: ");
if (BFS(graph, 1, N))
System.out.println("Graph contains cycle");
else
System.out.println("Graph doesn't contain any cycle");
}
输入：邻接矩阵（或预建边列表）
当前错误输出：显示部分边，但不显示循环的所有边
预期输出：打印所有创建循环的边，如上例所示，
我要显示：1--2, 2--3, 3--1
一条边的结束顶点是循环中另一条边的起始顶点。
我并不是说这是实现结果的最佳方式，但这是其中一种方式。
首先，我要更改您的节点的定义：
public class Node {
int v;
Node parent;
public Node(int v, Node parent) {
this.v = v;
this.parent = parent;
}
}
然后在你的方法 BFS 中，我将发现的布尔数组更改为节点数组，所以你知道，哪条路径通向这个节点。
// stores booleans if a vertex is discovered or not
Node[] discovered = new Node[N];
你的 BFS 方法将像这样工作：
public static boolean BFS(Graph graph, int src, int N) {
// stores booleans if a vertex is discovered or not
Node[] discovered = new Node[N];
// mark source vertex as discovered
Node start = new Node(src, null);
discovered[src] = start;
// create a queue used to do BFS and
// push source vertex into the queue
Queue<Node> q = new LinkedList<>();
q.add(start);
// run till queue is not empty
while (!q.isEmpty()) {
// pop front node from queue and print it
Node node = q.poll();
// do for every edge (v -> u)
for (int u : graph.adjList.get(node.v)) {
if (discovered[u] == null) {
// mark it as discovered
Node newNode = new Node(u, node);
discovered[u] = newNode;
// construct the queue node containing info
// about vertex and push it into the queue
q.add(newNode);
}
// u is discovered and u is not a parent
else if (u != node.parent.v) {
Node newNode = new Node(u, node);
int commonParent = findCommonParent(discovered[u], newNode);
String result = "";
Node current;
current = discovered[u];
while(current.v != commonParent) {
result = current.parent.v + "--" + current.v + ", " + result;
current = current.parent;
}
current = newNode;
while(current.v != commonParent) {
result = result + current.v + "--" + current.parent.v + ", ";
current = current.parent;
}
result = result.substring(0, result.length() - 2);
System.out.println(result);
// we found a cross-edge ie. cycle is found
return true;
}
}
}
// No cross-edges found in the graph
return false;
}
方法 findCommonParent 可以这样实现，例如：
private static int findCommonParent(Node n1, Node n2) {
Set<Integer> n1Parents = new HashSet<Integer>();
Node temp = n1.parent;
while(temp != null) {
n1Parents.add(temp.v);
temp = temp.parent;
}
temp = n2.parent;
while(temp != null) {
if(n1Parents.contains(temp.v)) {
break;
}
temp = temp.parent;
}
return temp.v;
}
我有一个无向图，它作为邻接矩阵加载。我有一种使用 BFS 算法检测图中循环的方法。我想要实现的是以指示已找到的循环的方式打印所有边缘。
我能够打印图形中的所有边，但我无法只打印那些创建循环的边。我如何让它发挥作用？
这是图形实现：
边缘：
public class Edge {
int source, dest;
public Edge(int source, int dest) {
this.source = source;
this.dest = dest;
}
}
图表：
public class Graph {
// A List of Lists to represent an adjacency list
// Each insideList contains pointers to the next vertex
// list with an index of 1 (vertex 1) contains elements 2 and 3 (where 2, 3 are vertices connected to 1)
List<List<Integer>> adjList = null;
// Constructor
public Graph(List<Edge> edges, int N) {
adjList = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}
// add edges to the undirected graph
for (Edge edge : edges) {
int src = edge.source;
int dest = edge.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
节点：
public class Node {
int v, parent;
public Node(int v, int parent) {
this.v = v;
this.parent = parent;
}
}
算法与测试：
public class GraphTest {
// Perform BFS on graph starting from vertex src and
// returns true if cycle is found in the graph
// while traversing the graph, it should display the edges which create a cycle, but I am unable to do it (the result is wrong)
public static boolean BFS(Graph graph, int src, int N) {
// stores booleans if a vertex is discovered or not
boolean[] discovered = new boolean[N];
// mark source vertex as discovered
discovered[src] = true;
// create a queue used to do BFS and
// push source vertex into the queue
Queue<Node> q = new ArrayDeque<>();
q.add(new Node(src, -1));
// run till queue is not empty
while (!q.isEmpty()) {
// pop front node from queue and print it
Node node = q.poll();
// do for every edge (v -> u)
for (int u : graph.adjList.get(node.v)) {
if (!discovered[u]) {
// mark it as discovered
discovered[u] = true;
// construct the queue node containing info
// about vertex and push it into the queue
System.out.println(node.v + " -- " + u);
q.add(new Node(u, node.v));
}
// u is discovered and u is not a parent
else if (u != node.parent) {
// we found a cross-edge ie. cycle is found
return true;
}
}
}
// No cross-edges found in the graph
return false;
}
// Check if an undirected graph contains cycle or not
public static void main(String[] args) {
// In my case I load an adjacency matrix from file and then perform an action to create Edges.
// 0 1 1 0
// 1 0 1 0
// 1 1 0 1
// 0 0 1 0
// Edge(1, 2), Edge(2, 3), Edge(3, 1), Edge(3, 4)
// Edge(3, 1) introduces a cycle in the graph
List<Edge> edges = new ArrayList<Edge>();
ArrayList<ArrayList<Integer>> matrixList = loadFromFile(filePath);
System.out.println("Graph: (Adjacency Matrix)");
for (int i = 0; i < matrixList.size(); i++) {
for (int j = 0; j < matrixList.size(); j++) {
System.out.print(matrixList.get(i).get(j) + " ");
}
System.out.println();
}
System.out.println("All the edges: ");
for (int i = 0; i < matrixList.size(); i++) {
// ' + 1' is added so as to start vertices from 1 instead of 0
int temp = i + 1;
for (int j = 0; j < matrixList.size(); j++) {
if (matrixList.get(i).get(j) == 1) {
System.out.println(temp + "--" + (j + 1) + " ");
// each edge is added one-way only since it is an undirected graph
// if Edge(1,3) is already present, Edge(3,1) is not added
boolean isFound = false;
for (Edge e : edges) {
if (e.dest == temp && e.source == (j + 1)) {
isFound = true;
}
}
if (!isFound)
edges.add(new Edge(temp, j + 1));
}
}
System.out.println();
}
// sets number of vertices in the graph
final int N = 5;
// creates a graph from edges
Graph graph = new Graph(edges, N);
boolean[] discovered = new boolean[N];
// do BFS traversal in connected components of graph
System.out.println("Detect a cycle: ");
if (BFS(graph, 1, N))
System.out.println("Graph contains cycle");
else
System.out.println("Graph doesn't contain any cycle");
}
输入：邻接矩阵（或预建边列表）
当前错误输出：显示部分边，但不显示循环的所有边
预期输出：打印所有创建循环的边，如上例所示，
我要显示：1--2, 2--3, 3--1
一条边的结束顶点是循环中另一条边的起始顶点。
我并不是说这是实现结果的最佳方式，但这是其中一种方式。
首先，我要更改您的节点的定义：
public class Node {
int v;
Node parent;
public Node(int v, Node parent) {
this.v = v;
this.parent = parent;
}
}
然后在你的方法 BFS 中，我将发现的布尔数组更改为节点数组，所以你知道，哪条路径通向这个节点。
// stores booleans if a vertex is discovered or not
Node[] discovered = new Node[N];
你的 BFS 方法将像这样工作：
public static boolean BFS(Graph graph, int src, int N) {
// stores booleans if a vertex is discovered or not
Node[] discovered = new Node[N];
// mark source vertex as discovered
Node start = new Node(src, null);
discovered[src] = start;
// create a queue used to do BFS and
// push source vertex into the queue
Queue<Node> q = new LinkedList<>();
q.add(start);
// run till queue is not empty
while (!q.isEmpty()) {
// pop front node from queue and print it
Node node = q.poll();
// do for every edge (v -> u)
for (int u : graph.adjList.get(node.v)) {
if (discovered[u] == null) {
// mark it as discovered
Node newNode = new Node(u, node);
discovered[u] = newNode;
// construct the queue node containing info
// about vertex and push it into the queue
q.add(newNode);
}
// u is discovered and u is not a parent
else if (u != node.parent.v) {
Node newNode = new Node(u, node);
int commonParent = findCommonParent(discovered[u], newNode);
String result = "";
Node current;
current = discovered[u];
while(current.v != commonParent) {
result = current.parent.v + "--" + current.v + ", " + result;
current = current.parent;
}
current = newNode;
while(current.v != commonParent) {
result = result + current.v + "--" + current.parent.v + ", ";
current = current.parent;
}
result = result.substring(0, result.length() - 2);
System.out.println(result);
// we found a cross-edge ie. cycle is found
return true;
}
}
}
// No cross-edges found in the graph
return false;
}
方法 findCommonParent 可以这样实现，例如：
private static int findCommonParent(Node n1, Node n2) {
Set<Integer> n1Parents = new HashSet<Integer>();
Node temp = n1.parent;
while(temp != null) {
n1Parents.add(temp.v);
temp = temp.parent;
}
temp = n2.parent;
while(temp != null) {
if(n1Parents.contains(temp.v)) {
break;
}
temp = temp.parent;
}
return temp.v;
}