Check if a Cycle Exists Between Nodes S and T in an Undirected Graph with only S and T Repeating

Approach

We can use Depth-First Search with backtracking to solve this problem. A simple cycle is present between S & T if two different paths exist, one from S to T and the other from T to S, such that no vertices except S & T are repeated in them. We will run a DFS from S. When we reach node T, we will change the dest node to S. Since DFS only visits node unvisited, we will get a path with no repeated vertices. After visiting the subtree of a node, we will set it as unvisited (backtracking) to explore all possible paths.

Algorithm

1. Create a boolean array of size N to keep track of the visited node. (Initialize the array with a false value, which means that no node has been visited yet)
2. Run a DFS from S, with T as the destination node. 
3. If we cannot reach T from S (i.e., there is no path from S to T), then it is impossible to have a simple cycle between S & T.
4. If we reach T, we change the destination to S and continue DFS. From here, nodes already visited (in the path from S to T) will not be revisited.
5. Finally, if S is reached, we print Yes, otherwise No.

Dry Run

Let us consider the undirected graph given in the sample example,

Step 1

The first half of the cycle from Source(1) to Destination(7) would be like this, we will cover the path from source to destination using DFS Algorithm.

Step 2

In the second half of the cycle, we will change the source and destination, now we will swap the value of the previous source and destination, and the new source will be 7 and the new destination will be 1. This time we will have to make sure that the path from the new source to the destination should not contain any nodes which have been visited previously.

Now, the cycle is complete and we have not discovered any node which already had been visited, the cycle would look like this,

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// to check if a node is visited or not
bool visited[1001];

// function to check if a cycle exists or not
bool dfs(int node, int source, int destination, bool flag, vector<int> *adj)
{

    // When reaching destination, change the destination node to source
    if (!flag && node == destination)
    {
        destination = source;
        flag = true;
    }

    //  If source is reached from destination, without  
   // visiting any node twice except themselves, then return True
    if (flag and node == destination)
        return true;

    bool found = false;
    visited[node] = true;
    for (auto v : adj[node])
    {

        // Visit a node only if it hasn't been visited
        // OR if it is S or T
        if (!visited[v] || v == destination)
        {
            found = found | dfs(v, source, destination, flag, adj);
        }
    }

    // Mark current node as unvisited so that all the
    // paths can be traversed (BackTracking)
    visited[node] = false;

    return found;
}

// function to add an edge in the undirected graph
void add(int u, int v, vector<int> adj[])
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

int main()
{
    // Number of nodes and edges
    int N = 7, E = 7;
    // cout << N << endl;
    // vector to make adjacency list
    vector<int> adj[N + 1];

    add(1, 2, adj);
    add(1, 3, adj);
    add(3, 5, adj);
    add(2, 4, adj);
    add(5, 6, adj);
    add(4, 7, adj);
    add(6, 7, adj);

    // Source and Destination
    int S = 1, T = 7;

    bool flag = false;
    // If there exists a simple cycle between Source and Destination
    if (dfs(S, S, T, flag, adj))
    {
        cout << "Yes there is a cycle";
    }
    // If no cycle exists between Source and Destination
    else
    {
        cout << "No there is no cycle!!";
    }
}

Output

Yes there is a cycle

Time Complexity

O(N!) is the time complexity, where N is the number of nodes in the graph. Because in the worst case, all paths are traversed using back-tracking.

Space Complexity

The space complexity of the above approach is O(N^2), where N is the number of nodes in the graph. 

Frequently Asked Questions

How does DFS handle cycles in a graph? 

DFS uses a visited array to keep track of the nodes it has visited. If a node is visited again, it means that there is a cycle in graph and DFS terminates.

What are the different forms to represent a graph?

A graph can be represented as an array of edges or using an adjacency list or in the form of a V x V matrix where (i, j) is non-zero if i and j are connected in the graph. This form is also called adjacency matrix representation.

What are the different applications of DFS?

We can use DFS to detect graph cycles. It helps determine a path between two vertices. It's useful for determining topological sort. We can also use it to determine whether or not a graph is bipartite.

What is the time complexity of DFS search with adjacency matrix representation?

The time complexity of DFS with adjacency matrix representation is O(N^2), here N is the number of nodes in the graph.

What are the advantages of using DFS over BFS?

DFS can be more memory efficient than BFS as it does not need to store all the nodes at a given depth before visiting the next depth. DFS is also simpler to implement than BFS.

Conclusion

Cheers if you reached here!! 

This article aimed to discuss an intriguing problem using graph DFS. We saw an exciting application of the DFS technique in this article. DFS-related coding problems are sometimes simple to implement, but finding an efficient approach based on certain observations remains difficult.

Recommended Readings

• Detect cycle in an undirected graph
   

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.

Learn various topics from Web Technologies, Programming Fundamentals, Data Structures, and Algorithms from our Library.