MST-Prim(G,r)
for each u ∈ G.V
       u.key = ∞
	   u.pred = nil
	   r.key = 0
	   Q = G.V
while Q ≠ ∅
	 u = ExtractMin(Q)
	 for each v ∈ G.Adj[u]
	 if v ∈ Q and w(u,v) < v.key
	 v.pred = u
	 v.key = w(u,v)

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

// Define the maximum number of vertices in the graph
#define MAX_VERTICES 100

// Structure to represent a vertex
struct Vertex {
    int key;
    int pred;
};

// Function to extract the vertex with the minimum key from the queue
int extractMin(struct Vertex Q[], int size, bool visited[]) {
    int minIndex = -1;
    int minValue = INT_MAX;
    
    for (int i = 0; i < size; i++) {
        if (!visited[i] && Q[i].key < minValue) {
            minValue = Q[i].key;
            minIndex = i;
        }
    }
    
    return minIndex;
}

// Main Prim's algorithm function
void MST_Prim(int G[MAX_VERTICES][MAX_VERTICES], int numVertices, int r) {
    struct Vertex vertices[MAX_VERTICES];
    bool visited[MAX_VERTICES] = {false};
    
    // Initialize vertices
    for (int u = 0; u < numVertices; u++) {
        vertices[u].key = INT_MAX;
        vertices[u].pred = -1;
    }
    
    vertices[r].key = 0;
    
    for (int i = 0; i < numVertices; i++) {
        int u = extractMin(vertices, numVertices, visited);
        visited[u] = true;
        
        for (int v = 0; v < numVertices; v++) {
            if (G[u][v] && !visited[v] && G[u][v] < vertices[v].key) {
                vertices[v].pred = u;
                vertices[v].key = G[u][v];
            }
        }
    }
    
    // Print the minimum spanning tree
    printf("Edge   Weight\n");
    for (int i = 0; i < numVertices; i++) {
        if (vertices[i].pred != -1) {
            printf("%d - %d   %d\n", vertices[i].pred, i, vertices[i].key);
        }
    }
}

int main() {
    int numVertices, r;
    int G[MAX_VERTICES][MAX_VERTICES];
    
    printf("Enter the number of vertices: ");
    scanf("%d", &numVertices);
    
    printf("Enter the adjacency matrix:\n");
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            scanf("%d", &G[i][j]);
        }
    }
    
    printf("Enter the root vertex: ");
    scanf("%d", &r);
    
    MST_Prim(G, numVertices, r);
    
    return 0;
}

DFS(G):
	  for each u ∈ G.V
      u.color = white
      time = 0
	  for each u ∈ G.V
	  if u.color == white
	  DFS-Visit(G,u)

DFS-Visit(G,u):
	 u.d = ++time
	 u.color = gray
	 for each v ∈ G.Adj[u]
	 if v.color == white
	 DFS-Visit(G,v)
     u.color = black
	 u.f = ++time

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

#define MAX_NODES 5

typedef struct Node {
    int value;
    int color;
    int d;
    int f;
} Node;

void DFS(Node graph[], int u, int *time) {
    graph[u].color = 1;
    graph[u].d = ++(*time);

    for (int i = 0; i < MAX_NODES; i++) {
        if (graph[u].color == 0 && graph[u].value != graph[i].value) {
            DFS(graph, i, time);
        }
    }

    graph[u].color = 2;
    graph[u].f = ++(*time);
}

int main() {
    Node graph[MAX_NODES] = {
        {0, 0, 0, 0},
        {1, 0, 0, 0},
        {2, 0, 0, 0},
        {3, 0, 0, 0},
        {4, 0, 0, 0}
    };

    int adjacencyMatrix[MAX_NODES][MAX_NODES] = {
        {0, 1, 1, 0, 0},
        {0, 0, 0, 1, 1},
        {0, 0, 0, 0, 1},
        {0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0}
    };

    int time = 0;

    for (int i = 0; i < MAX_NODES; i++) {
        if (graph[i].color == 0) {
            DFS(graph, i, &time);
        }
    }

    printf("Node\tColor\tDiscovery Time\tFinish Time\n");
    for (int i = 0; i < MAX_NODES; i++) {
        printf("%d\t%d\t%d\t%d\n", graph[i].value, graph[i].color, graph[i].d, graph[i].f);
    }

    return 0;
}

for each u ∈ G.V - {s}
              u.color = white
s.color = gray
s.d = 0
Q = ∅
Q.enqueue(s)
while Q ≠ ∅
	      u = Q.dequeue()
         for each v ∈ G.Adj[u]
	           if v.color == white
	                  v.color = gray
	                  v.d = u.d + 1
	                  v.pred = u
	                  Q.enqueue(v)
	         u.color = black

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

#define MAX_NODES 5

// Structure to represent a node in the graph
typedef struct Node {
    int value;
    int color; // 0: white, 1: gray, 2: black
    int d;     // Distance from source
    struct Node* pred; // Predecessor in BFS traversal
    struct Node* next; // Linked list of adjacent nodes
} Node;

// Queue structure
typedef struct Queue {
    Node* items[MAX_NODES];
    int front;
    int rear;
} Queue;

void enqueue(Queue* q, Node* node) {
    q->items[q->rear++] = node;
}

Node* dequeue(Queue* q) {
    return q->items[q->front++];
}

// Breadth-First Search function
void BFS(Node* graph[], int numNodes, Node* source) {
    Queue q;
    q.front = 0;
    q.rear = 0;

    // Initialize the queue and source node
    enqueue(&q, source);
    source->color = 1; // Gray
    source->d = 0;
    source->pred = NULL;

    while (q.front != q.rear) {
        Node* u = dequeue(&q);
        Node* v = u->next;

        while (v != NULL) {
            if (v->color == 0) { // White
                v->color = 1; // Gray
                v->d = u->d + 1;
                v->pred = u;
                enqueue(&q, v);
            }
            v = v->next;
        }

        u->color = 2; // Black
    }
}

int main() {
    // Create nodes
    Node* nodes[MAX_NODES];
    for (int i = 0; i < MAX_NODES; i++) {
        nodes[i] = (Node*)malloc(sizeof(Node));
        nodes[i]->value = i;
        nodes[i]->color = 0; // White
        nodes[i]->d = -1;    // Distance uninitialized
        nodes[i]->pred = NULL;
        nodes[i]->next = NULL;
    }

    // Add edges (Modify this part to match your graph)
    nodes[0]->next = nodes[1];
    nodes[1]->next = nodes[2];
    nodes[2]->next = nodes[3];
    nodes[3]->next = nodes[4];

    // Perform BFS
    BFS(nodes, MAX_NODES, nodes[0]);

    // Print results
    for (int i = 0; i < MAX_NODES; i++) {
        printf("Node %d: Color: %d, Distance: %d\n", nodes[i]->value, nodes[i]->color, nodes[i]->d);
    }

    // Free allocated memory
    for (int i = 0; i < MAX_NODES; i++) {
        free(nodes[i]);
    }

    return 0;
}