C Programming Data Structures Detecting Cycles In Graphs Complete Guide

1. What are the primary algorithms used to detect cycles in a graph?

Answer: The primary algorithms used for detecting cycles in a graph are:

• Depth-First Search (DFS): A recursive approach where we keep track of visited vertices and check for a back edge. A back edge is an edge that is pointing to an already visited vertex, creating a cycle.
• Breadth-First Search (BFS): Typically used for undirected graphs. It uses a parent array to keep track of the parent of each node to detect back edges.
• Kahn's Algorithm/Topological Sorting: This is more generally used for directed graphs to detect cycles by checking if the graph has a topological ordering.

2. How does DFS work to detect cycles in a directed graph?

Answer: In a directed graph, DFS can detect a cycle by checking for back edges. A back edge connects a node to an ancestor in the DFS tree. The algorithm uses a visited array to mark nodes and a recStack array to keep track of vertices in the current recursion stack. If a node is found in recStack, it's a back edge.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int dest;
    struct Node* next;
} Node;

typedef struct Graph {
    int V;
    Node** adjList;
    bool* visited;
    bool* recStack;
} Graph;

Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->dest = v;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->V = vertices;

    graph->adjList = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(bool));
    graph->recStack = malloc(vertices * sizeof(bool));

    for (int i = 0; i < vertices; i++) {
        graph->adjList[i] = NULL;
        graph->visited[i] = false;
        graph->recStack[i] = false;
    }

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

bool isCyclicUtil(Graph* graph, int v) {
    if (graph->recStack[v]) return true;
    if (graph->visited[v]) return false;

    graph->visited[v] = true;
    graph->recStack[v] = true;

    Node* temp = graph->adjList[v];
    while (temp) {
        if (isCyclicUtil(graph, temp->dest))
            return true;
        temp = temp->next;
    }

    graph->recStack[v] = false;
    return false;
}

bool isCyclic(Graph* graph) {
    for (int v = 0; v < graph->V; v++) {
        if (!graph->visited[v] && isCyclicUtil(graph, v))
            return true;
    }
    return false;
}

int main() {
    Graph* graph = createGraph(4);
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1); // This will make the graph cyclic

    if (isCyclic(graph))
        printf("Graph contains cycle\n");
    else
        printf("Graph doesn't contain cycle\n");

    return 0;
}

3. Can BFS be used to detect cycles in an undirected graph?

Answer: Yes, BFS can be used to detect cycles in an undirected graph. An undirected graph has a cycle if BFS finds an adjacent vertex which is already visited and is not a parent of the current vertex.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define V 5

typedef struct QNode {
    int data;
    struct QNode* next;
} QNode;

typedef struct Queue {
    struct QNode *front, *rear;
} Queue;

Queue* createQueue() {
    Queue* queue = (Queue*) malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

QNode* createQNode(int v) {
    QNode* temp = (QNode*) malloc(sizeof(QNode));
    temp->data = v;
    temp->next = NULL;
    return temp;
}

void enQueue(Queue* queue, int v) {
    QNode* temp = createQNode(v);
    if (!queue->rear) {
        queue->front = queue->rear = temp;
        return;
    }
    queue->rear->next = temp;
    queue->rear = temp;
}

int deQueue(Queue* queue) {
    if (!queue->front)
        return -1;
    QNode* temp = queue->front;
    queue->front = queue->front->next;
    int v = temp->data;
    if (!queue->front)
        queue->rear = NULL;
    free(temp);
    return v;
}

bool isEmpty(Queue* queue) {
    return queue->front == NULL;
}

bool isCyclicUndirected(int adj[V][V]) {
    bool visited[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            Queue* queue = createQueue();
            visited[i] = true;
            enQueue(queue, i);

            while (!isEmpty(queue)) {
                int u = deQueue(queue);

                for (int v = 0; v < V; ++v) {
                    if (adj[u][v]) {
                        if (!visited[v]) {
                            visited[v] = true;
                            enQueue(queue, v);
                        } else if (adj[v][u]) {
                            return true;
                        }
                    }
                }
            }
        }
    }
    return false;
}

int main() {
    int adj[V][V] = {{0, 1, 0, 0, 1},
                     {1, 0, 1, 1, 0},
                     {0, 1, 0, 0, 0},
                     {0, 1, 0, 0, 1},
                     {1, 0, 0, 1, 0}};

    if (isCyclicUndirected(adj))
        printf("Graph contains cycle\n");
    else
        printf("Graph doesn't contain cycle\n");

    return 0;
}

4. What is Tarjan’s algorithm used for in terms of cycle detection?

Answer: Tarjan's algorithm is a depth first search (DFS) based algorithm used to find all strongly connected components (SCCs) in a directed graph. It can also be adapted to detect cycles and find the cut vertices and cut edges in a graph. It assigns an index to each node and keeps track of the lowest back-index it can reach (low-value). A node is a root of an SCC if it doesn’t have a node with a smaller low-value reachable from its children nodes in DFS.

5. Can Union-Find data structure be used to detect cycles in an undirected graph?

Answer: Yes, the Union-Find data structure can be used to detect cycles in an undirected graph. The idea is to maintain the connected components. For every edge, check if both nodes of the edge belong to the same component. If yes, a cycle is detected because they would already be connected. Otherwise, union the two sets.

#include <stdio.h>
#include <stdlib.h>

typedef struct Edge {
    int src, dest;
} Edge;

typedef struct Graph {
    int V, E;
    Edge* edge;
} Graph;

Graph* createGraph(int V, int E) {
    Graph* graph = (Graph*) malloc(sizeof(Graph));
    graph->V = V;
    graph->E = E;

    graph->edge = (Edge*) malloc(graph->E * sizeof(Edge));

    return graph;
}

int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

void Union(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    if(xset != yset)
        parent[xset] = yset;
}

int isCycle( Graph* graph )
{
    int *parent = (int*) malloc( graph->V * sizeof(int) );

    for(int i = 0; i < graph->V; ++i)
        parent[i] = -1;

    for(int i = 0; i < graph->E; ++i) {
        int x = find(parent, graph->edge[i].src);
        int y = find(parent, graph->edge[i].dest);

        if (x == y)
            return 1;

        Union(parent, x, y);
    }
    return 0;
}

int main()
{
    int V = 3, E = 3;
    Graph* graph = createGraph(V, E);

    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;

    graph->edge[1].src = 1;
    graph->edge[1].dest = 2;

    graph->edge[2].src = 0;
    graph->edge[2].dest = 2;

    if (isCycle(graph))
        printf( "Graph contains cycle\n" );
    else
        printf( "Graph doesn't contain cycle\n" );

    return 0;
}

6. How can we modify DFS to detect cycles in an undirected graph?

Answer: In an undirected graph, we can modify DFS to detect cycles by keeping track of the parent node of each node. A cycle is detected if we visit an already visited node that is not the parent of the current node.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define V 5

typedef struct Node {
    int dest;
    struct Node* next;
} Node;

typedef struct Graph {
    int V;
    Node** adjList;
    bool* visited;
} Graph;

Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->dest = v;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->V = vertices;

    graph->adjList = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(bool));

    for (int i = 0; i < vertices; i++) {
        graph->adjList[i] = NULL;
        graph->visited[i] = false;
    }

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;

    newNode = createNode(src);
    newNode->next = graph->adjList[dest];
    graph->adjList[dest] = newNode;
}

bool isCyclicUtil(Graph* graph, int v, int parent) {
    graph->visited[v] = true;

    Node* temp = graph->adjList[v];
    while (temp) {
        int adjacent = temp->dest;

        if (!graph->visited[adjacent]) {
            if (isCyclicUtil(graph, adjacent, v))
                return true;
        } else if (adjacent != parent) {
            return true;
        }
        temp = temp->next;
    }

    return false;
}

bool isCyclicUndirectedGraph(Graph* graph) {
    for (int v = 0; v < graph->V; v++) {
        if (!graph->visited[v]) {
            if (isCyclicUtil(graph, v, -1))
                return true;
        }
    }
    return false;
}

int main() {
    Graph* graph = createGraph(V);
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 0, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 1); // This will make the graph cyclic

    if (isCyclicUndirectedGraph(graph))
        printf("Graph contains cycle\n");
    else
        printf("Graph doesn't contain cycle\n");

    return 0;
}

7. What is the time complexity of the cycle detection algorithm in an undirected graph using BFS?

Answer: The time complexity of the cycle detection algorithm in an undirected graph using BFS is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex and edge are visited once during the BFS traversal.

8. Why is Tarjan's algorithm efficient in cycle detection?

Answer: Tarjan's algorithm is efficient in cycle detection because it uses a single DFS traversal, and it maintains auxiliary arrays to keep track of discovery times and low values. This allows it to identify SCCs in O(V + E) time, making it efficient for large graphs.

9. How does the Union-Find algorithm perform union and find operations?

Answer: The Union-Find algorithm consists of two main operations:

• Find: It determines the root of the set containing i. It uses path compression heuristic to flatten the structure of the tree so that each node points directly to the root, optimizing future operations.
• Union: It connects the roots of the sets containing x and y. It uses union by rank heuristic, which optimizes the structure of the tree by always attaching the smaller tree under the root of the larger tree.

10. Can BFS be used to detect cycles in a directed graph?

Answer: BFS alone cannot detect cycles in a directed graph directly. It can be adapted to detect cycles by keeping track of back edges, but it's more commonly used for undirected graphs. For directed graphs, DFS is more straightforward and efficient for cycle detection.