CODEWITHSUNDEEP
graph-theorygraph-algorithmcycle
Sushil Verma
Sushil Verma

Reputation: 697

Finding cycle in the graph

We are given a simple un-directed graph G=(V,E) and a subset S of V.

We are told that all the vertices of S are making a simple cycle (of length |S|) in G.

Now, we are to find that exact cycle (or its any cyclic shift) (a sequence of all vertices of S). How can we find it ? Any approach ?

I tried DFS/BFS but it does not seem working fine.

For example: if we have 4 vertices A, B, C, D in G and edges are (A,C), (A,D), (B,C), (B,D). Let given S= {A, B, C, D}

Then our answer should be ADBCA (or BCADB or its any cyclic shift).

Upvotes: 2

Views: 459

Answers (2)

uSeemSurprised
uSeemSurprised

Reputation: 1834

I have written a solution using adjacency matrix in c++, a adjacency list solution should also work in the same way, since we know that it is a simple cycle we can start from any vertex and start searching for a possible path, that contains only the nodes that we want, if we find the path of corresponding length we store it, or else search untill we find one.

#include<bits/stdc++.h>

using namespace std;

int G[100][100], n, m, S[100], sz;
int ans[100], curr[100], vis[100];
bool fd = false;

void solve(int start, int len){
    vis[start] = 1;
    curr[len] = start;
    if(len == m-1){
        fd = true;
        for(int i = 0;i <= m;i++) ans[i] = curr[i];return;
    }
    for(int i = 0;i < n;i++){
        if(G[start][i] == 1 && vis[i] == 0 && S[i] == 1){
            solve(i, len+1);
        }
    }
    vis[start] = 0;
}

int main(){
    cin >> n >> sz;
    int p, q;
    for(int i = 0;i < sz;i++){
        cin >> p >> q;G[p][q] = 1;G[q][p] = 1;
    }
    cin >> m;
    for(int i = 0;i < m;i++){
        cin >> p;S[p] = 1;
    }
    for(int i = 0;i < n;i++){
        if(S[i] == 1){
            solve(i, 0);
            break;
        }
    }
    if(fd == false){
        cout << "No such path" << endl;
    }else{
        for(int i = 0;i < m;i++){
            cout << ans[i] << " ";
        }cout << endl;
    }
return 0;
}

Link to solution on ideone : https://ideone.com/FVTyJX

Upvotes: 1

Lajos Arpad
Lajos Arpad

Reputation: 76424

First, you need to iterate all your nodes in S. If there are any nodes having less than two vertices, then you will not find such a cycle. Then, you need to generate with backtracking paths containing all nodes, checking for each whether there is a vertice between the last and the first node. If you find such a path, then you have found such a cycle. If not, then there is no such cycle in the node set you work with.

Upvotes: 1

Related Questions