Graphs

//DFS


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

#define MAX 10

// Structure to represent a graph node
struct Graph {
    int adjacencyMatrix[MAX][MAX];  // Adjacency matrix to represent the graph
    int visited[MAX];  // Array to keep track of visited nodes
};

// Function to initialize the graph
void initializeGraph(struct Graph *g) {
    for (int i = 0; i < MAX; i++) {
        g->visited[i] = 0;
        for (int j = 0; j < MAX; j++) {
            g->adjacencyMatrix[i][j] = 0;  // Initialize all edges to 0 (no edges)
        }
    }
}

// Function to add an edge between two nodes
void addEdge(struct Graph *g, int u, int v) {
    g->adjacencyMatrix[u][v] = 1;
    g->adjacencyMatrix[v][u] = 1;  // As the graph is undirected
}

// DFS Iterative Function using stack
void DFSIterative(struct Graph *g, int startVertex) {
    int stack[MAX], top = -1;
    stack[++top] = startVertex;  // Push the start vertex onto the stack

    while (top >= 0) {
        int v = stack[top--];  // Pop an element from the stack

        if (!g->visited[v]) {
            printf("%d ", v);  // Process the vertex
            g->visited[v] = 1;  // Mark the vertex as visited
        }

        // Push all adjacent vertices of v onto the stack
        for (int w = 0; w < MAX; w++) {
            if (g->adjacencyMatrix[v][w] == 1 && !g->visited[w]) {
                stack[++top] = w;
            }
        }
    }
}

int main() {
    struct Graph g;
    initializeGraph(&g);

    // Adding edges to the graph
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 4);

    // Performing DFS starting from vertex 0
    printf("DFS traversal starting from vertex 0:\n");
    DFSIterative(&g, 0);

    return 0;
}

//BFS

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

#define MAX 10

// Structure to represent a graph
struct Graph {
    int adjacencyMatrix[MAX][MAX];  // Adjacency matrix for the graph
    int visited[MAX];  // Array to keep track of visited nodes
};

// Function to initialize the graph
void initializeGraph(struct Graph *g) {
    for (int i = 0; i < MAX; i++) {
        g->visited[i] = 0;
        for (int j = 0; j < MAX; j++) {
            g->adjacencyMatrix[i][j] = 0;  // Initialize all edges to 0 (no edges)
        }
    }
}

// Function to add an edge between two nodes
void addEdge(struct Graph *g, int u, int v) {
    g->adjacencyMatrix[u][v] = 1;
    g->adjacencyMatrix[v][u] = 1;  // As the graph is undirected
}

// BFS function using queue
void BFS(struct Graph *g, int startVertex) {
    int queue[MAX], front = -1, rear = -1;

    // Mark the start vertex as visited and enqueue it
    g->visited[startVertex] = 1;
    queue[++rear] = startVertex;
    if (front == -1) front = 0;

    printf("BFS traversal starting from vertex %d:\n", startVertex);

    while (front <= rear) {
        // Dequeue a vertex from the queue and process it
        int v = queue[front++];
        printf("%d ", v);

        // Enqueue all unvisited adjacent vertices of the dequeued vertex
        for (int w = 0; w < MAX; w++) {
            if (g->adjacencyMatrix[v][w] == 1 && !g->visited[w]) {
                g->visited[w] = 1;
                queue[++rear] = w;
            }
        }
    }
}

int main() {
    struct Graph g;
    initializeGraph(&g);

    // Adding edges to the graph
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 4);

    // Performing BFS starting from vertex 0
    BFS(&g, 0);

    return 0;
}

//Topological sort

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

#define MAX 100

int graph[MAX][MAX]; // Adjacency matrix representation
bool visited[MAX];   // Visited array
int stack[MAX];      // Stack to store topological order
int top = -1;        // Stack pointer

void push(int v) {
    stack[++top] = v;
}

int pop() {
    return stack[top--];
}

void dfs(int v, int n) {
    visited[v] = true;

    // Visit all adjacent vertices of v
    for (int i = 0; i < n; i++) {
        if (graph[v][i] && !visited[i]) {
            dfs(i, n);
        }
    }

    // Push the vertex onto the stack after visiting all its neighbors
    push(v);
}

void topologicalSort(int n) {
    // Initialize visited array to false
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }

    // Perform DFS from all unvisited nodes
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, n);
        }
    }

    // Print the topological order (reverse of stack)
    printf("Topological Order: ");
    while (top != -1) {
        printf("%d ", pop());
    }
    printf("\n");
}

int main() {
    int n, e;

    printf("Enter the number of vertices: ");
    scanf("%d", &n);

    printf("Enter the number of edges: ");
    scanf("%d", &e);

    // Initialize graph with 0s
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }

    printf("Enter the edges (from to):\n");
    for (int i = 0; i < e; i++) {
        int from, to;
        scanf("%d %d", &from, &to);
        graph[from][to] = 1; // Directed edge
    }

    topologicalSort(n);

    return 0;
}