I am doing an assignment in which I need to do a DFS of a undirected graph, and then print a cycle if one is found. The issue is that any algorithms I can locate for finding cycle do not store the cycle-- they are simply true/false. My current code only works for some graphs, but not for others. For example, it can't find a 2-node cycle (4-5, 5-4). Also, it only works for directed right now when it should be undirected.
Edit: this is not a duplicate of other questions about finding and printing cycles, because as far as I can see, none of the other problems addressed how to store and subsequently print a cycle-- just how to find whether or not it exists and return true/false.
Edit: Formatting
Attached is my traversal code and my main method
-- Main Method
public static void main(String args[]) {
//
// Graph g = new Graph(8);
//
// g.add(0, 2);
// g.add(2, 3);
// g.add(3, 1);
// g.add(1, 0);
//
// g.add(4, 5);
// g.add(5, 6);
// g.add(6, 7);
// g.add(7, 4);
//
// Graph g = new Graph(6);
//
// g.add(0, 1);
// g.add(1, 3);
// g.add(2, 3);
// g.add(3, 4);
// g.add(3, 5);
//
// Graph g = new Graph(7);
//
// g.add(0, 1);
// g.add(0, 2);
// g.add(0, 3);
// g.add(3, 4);
// g.add(4, 3);
// g.add(4, 5);
// g.add(4, 6);
Graph g = new Graph(5);
g.add(0, 1);
g.add(2, 3);
g.add(2, 4);
g.add(3, 4);
DepthFirstTraversal dfs = new DepthFirstTraversal(g);
System.out.println("Following is Depth First Traversal");
dfs.DFS();
if (!dfs.isCyclic())
System.out.println("This graph is acyclic");
}
-- Graph class
import java.util.LinkedList;
public class Graph {
//Number of Vertices
private int vertices;
//Linked List to hold edges
private LinkedList<Integer> edges[];
public Graph(int verticesGiven) {
this.vertices = verticesGiven;
this.edges = new LinkedList[vertices];
fillNodes(edges, vertices);
}
private static void fillNodes(LinkedList<Integer> edges[], int
vertices) {
for (int counter = 0; counter < vertices; ++counter) {
edges[counter] = new LinkedList();
}
}
void add(int x, int y) {
edges[x].add(y);
}
public int getVertices() {
return vertices;
}
public LinkedList<Integer>[] getEdges() {
return edges;
}
}
-- Traversal and Cyclic Search
import java.util.*;
public class DepthFirstTraversal {
//Each traversal has a graph
private Graph graph;
//Holds the nodes for each cycle
private List<Integer> cycle = new ArrayList<Integer>();
public DepthFirstTraversal(Graph graph) {
this.graph = graph;
}
private void DFSRecursive(int current, boolean visited[],
LinkedList<Integer> edges[]) {
// Say you visited current node
visited[current] = true;
//Print the current node
System.out.print(current + " ");
// Look at all vertices connected to this one
Iterator<Integer> iterate = edges[current].listIterator();
//Check to see everything this is connected to
while (iterate.hasNext()) {
//Check to see what the next one is
int connected = iterate.next();
//check if you've already visited what it's connected to.
If you haven't, check that one out.
if (!visited[connected])
//Check whatever the current one is connected to
DFSRecursive(connected, visited, edges);
}
}
public void DFS() {
//Check to see how many vertices graph has
int vertices = graph.getVertices();
//Keeps track of which vertices have already been visited
boolean visited[] = new boolean[vertices];
//Visits all of the nodes
for (int counter = 0; counter < vertices; ++counter)
//calls recursive method if this node has not been visited
if (!visited[counter])
DFSRecursive(counter, visited, graph.getEdges());
}
private Boolean isCyclicRecursive(int index, Boolean visited[], int
parent, LinkedList<Integer> edges[]) {
// Mark the current node as visited
visited[index] = true;
//Integer to hold what the node is connected to
Integer connection;
// Recur for all the vertices adjacent to this vertex
Iterator<Integer> iterator = edges[index].iterator();
//Check to see if the current node has a connection
while (iterator.hasNext()) {
//Looks at what is connected to it.
connection = iterator.next();
//If you haven't visited the connection, look at that. Sets the current as the parent of the connection.
if (!visited[connection]) {
cycle.add(index);
if (isCyclicRecursive(connection, visited, index,
graph.getEdges())) {
return true;
} else {
Integer item = new Integer(index);
cycle.remove(item);
}
}
//Checks to see if the thing it's connected to is its parent (you've completed a cycle)
else if (connection != parent) {
//Add parent and connection
cycle.add(index);
cycle.add(connection);
//Only find the things in current cycle
for (int i = 0; i < cycle.size(); i++) {
//Not a true cycle
// if (cycle.size() <= 1)
// return false;
int first = cycle.get(i);
int last = cycle.get(cycle.size() - 1);
if (first == last) {
System.out.print("Cycle Detected: ");
for (int j = 0; j < cycle.size(); j++) {
System.out.print(cycle.get(j).toString() + " ");
}
System.out.println();
return true;
} else {
//only prints things actually in this cycle
cycle.remove(i);
i--;
}
}
return true;
}
}
return false;
}
/**************************************************************/
/* Method: isCyclic
/* Purpose: Checks to see if graph is cyclic
/* Parameters: None
/* Returns: None
/**************************************************************/
public Boolean isCyclic() {
//Mark all vertices as not visited
int vertices = graph.getVertices();
Boolean visited[] = new Boolean[vertices];
for (int counter = 0; counter < vertices; counter++)
visited[counter] = false;
//For every node, check if it is cyclic
for (int counter = 0; counter < vertices; counter++)
//Only check for cyclic if this has been visited
if (!visited[counter])
if (isCyclicRecursive(counter, visited, -1, graph.getEdges()))
return true;
return false;
}
}
