DSA Unit 4

Graphs

What is a Graph?

A Graph is a non-linear data structure consisting of nodes and edges. Think of it as a map:

• Vertices (V): The "places" (cities, routers, people)
• Edges (E): The "connections" (roads, cables, relationships)

Mathematically, a graph is G = (V, E)

Key Terminology

• Undirected Graph: Connections go both ways (two-way street)
• Directed Graph (Digraph): Connections have direction (one-way street)
• Weighted Graph: Edges have a "cost" (distance, time, bandwidth)
• Degree: Number of edges connected to a vertex

Data Structure Definitions

#define MAX 25

struct node {
    int data;
};

struct arc {
    int adj;
    int weight;
};

struct graph {
    struct node nodes[MAX];
    struct arc arcs[MAX][MAX];
};

struct graph g;

Adjacency Matrix - Read Function

void read_ad_matr(int graph[MAX][MAX], int n) {
    int i, j;
    printf("Enter the adjacency matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
}

DFS Traversal

void dfs(int u, int visited[], int graph[MAX][MAX], int n) {
    visited[u] = 1;

    for (int v = 0; v < n; v++) {
        if (graph[u][v] && !visited[v]) {
            dfs(v, visited, graph, n);
        }
    }
}

BFS Traversal

void bfs(int s, int visited[], int n, int graph[MAX][MAX]) {
    int f = 0, r = -1;
    int q[MAX];
    int v;

    q[++r] = s;
    visited[s] = 1;

    while (f <= r) {
        s = q[f++];

        for (v = 0; v < n; v++) {
            if (graph[s][v] == 1) {
                if (visited[v] == 0) {
                    visited[v] = 1;
                    q[++r] = v;
                }
            }
        }
    }
}

Check Connectivity

This function checks for Strong Connectivity in directed graphs by testing if all nodes can be reached from every other node.

int isConnected(int n, int graph[MAX][MAX]) {
    int visited[MAX];
    int i, u;

    for (u = 0; u < n; u++) {

        for (i = 0; i < n; i++) {
            visited[i] = 0;
        }

        dfs(u, visited, graph, n);

        for (i = 0; i < n; i++) {
            if (!visited[i]) {
                return 0;
            }
        }
    }
    return 1;
}

Adjacency List Operations

The following functions use cursor-based implementation where next and point are integer indices.

Join Two Nodes (Add Edge)

void join(int p, int q, int wt) {
    int r, r2;

    r = node[p].point;
    r2 = -1;

    while(r >= 0 && node[r].point != q) {
        r2 = r;
        r = node[r].next;
    }

    if(r >= 0) {
        node[r].info = wt;
        return;
    }

    r = getnode();
    node[r].point = q;
    node[r].next = -1;
    node[r].info = wt;

    if (r2 < 0) {
        node[p].point = r;
    } else {
        node[r2].next = r;
    }
}

Remove an Edge

void remv(int p, int q) {
    int r, r2;
    r2 = -1;
    r = node[p].point;

    while(r >= 0 && node[r].point != q) {
        r2 = r;
        r = node[r].next;
    }

    if(r >= 0) {
        if (r2 < 0) {
            node[p].point = node[r].next;
        } else {
            node[r2].next = node[r].next;
        }
        freenode(r);
        return;
    }
}

Check Adjacency

#define TRUE 1
#define FALSE 0

int adjacent(int p, int q) {
    int r;
    r = node[p].point;

    while(r >= 0) {
        if(node[r].point == q) {
            return(TRUE);
        } else {
            r = node[r].next;
        }
    }
    return(FALSE);
}

Find Node

int findnode(int graph, int x) {
    int p;
    p = graph;

    while(p >= 0) {
        if (node[p].info == x) {
            return(p);
        } else {
            p = node[p].next;
        }
    }
    return(-1);
}

Add Node

int addnode(int *graph, int x) {
    int p;
    p = getnode();
    node[p].info = x;
    node[p].point = -1;

    node[p].next = *graph;
    *graph = p;

    return(p);
}

BFS and DFS Comparison

Trie Trees

A Trie is a tree-like data structure used for efficient retrieval of strings. Each node represents a character, and paths from root to leaves form complete strings.

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

#define ALPHABET_SIZE 26

struct trienode {
    struct trienode *child[ALPHABET_SIZE];
    int endofword;
};

struct trienode *getnode() {
    struct trienode *pNode = (struct trienode *)malloc(sizeof(struct trienode));
    if (pNode) {
        pNode->endofword = 0;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            pNode->child[i] = NULL;
        }
    }
    return pNode;
}

void insert(struct trienode *root, char *key) {
    struct trienode *curr = root;
    int index;

    for (int i = 0; key[i] != '\0'; i++) {
        index = key[i] - 'a';

        if (!curr->child[index]) {
            curr->child[index] = getnode();
        }
        curr = curr->child[index];
    }
    curr->endofword = 1;
}

int search(struct trienode *root, char *key) {
    struct trienode *curr = root;
    int index;

    for (int i = 0; key[i] != '\0'; i++) {
        index = key[i] - 'a';
        if (!curr->child[index]) {
            return 0;
        }
        curr = curr->child[index];
    }
    return (curr != NULL && curr->endofword);
}

int isEmpty(struct trienode* root) {
    for (int i = 0; i < ALPHABET_SIZE; i++)
        if (root->child[i])
            return 0;
    return 1;
}

struct trienode* delete_node(struct trienode* root, char* key, int depth) {
    if (!root)
        return NULL;

    if (depth == strlen(key)) {
        if (root->endofword)
            root->endofword = 0;

        if (isEmpty(root)) {
            free(root);
            root = NULL;
        }
        return root;
    }

    int index = key[depth] - 'a';
    root->child[index] = delete_node(root->child[index], key, depth + 1);

    if (isEmpty(root) && root->endofword == 0) {
        free(root);
        root = NULL;
    }

    return root;
}

char word_buffer[50];
int length = 0;

void display(struct trienode *curr) {
    if (!curr) return;

    if (curr->endofword == 1) {
        word_buffer[length] = '\0';
        printf("%s\n", word_buffer);
    }

    for (int i = 0; i < ALPHABET_SIZE; i++) {
        if (curr->child[i] != NULL) {
            word_buffer[length++] = i + 'a';
            display(curr->child[i]);
            length--;
        }
    }
}

Hashing

Separate Chaining

Separate chaining uses linked lists to handle collisions. Each array index points to a linked list of elements that hash to that index.

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

#define SIZE 7

typedef struct element {
    int rNo;
    char name[30];
    struct element *next;
} NODE;

void initTable(NODE* ht[SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        ht[i] = NULL;
    }
}

void insert(NODE* ht[SIZE], int rNo, char* name) {
    int index = rNo % SIZE;

    NODE* newNode = (NODE*)malloc(sizeof(NODE));
    newNode->rNo = rNo;
    strcpy(newNode->name, name);

    newNode->next = ht[index];

    ht[index] = newNode;

    printf("Inserted (%d, %s) at index %d\n", rNo, name, index);
}

int delete(NODE* ht[SIZE], int rNo) {
    int index = rNo % SIZE;
    NODE *p = ht[index];
    NODE *q = NULL;

    while (p != NULL && p->rNo != rNo) {
        q = p;
        p = p->next;
    }

    if (p != NULL) {
        if (q == NULL) {
            ht[index] = p->next;
        }
        else {
            q->next = p->next;
        }
        free(p);
        return 1;
    }
    return 0;
}

int search(NODE* ht[SIZE], int rNo, char* foundName) {
    int index = rNo % SIZE;
    NODE *p = ht[index];

    while (p != NULL) {
        if (p->rNo == rNo) {
            strcpy(foundName, p->name);
            return 1;
        }
        p = p->next;
    }
    return 0;
}

void display(NODE* ht[SIZE]) {
    printf("\n--- Hash Table Contents ---\n");
    for (int i = 0; i < SIZE; i++) {
        printf("[%d]: ", i);
        NODE *p = ht[i];
        if (p == NULL) {
            printf("NULL");
        }
        while (p != NULL) {
            printf("%d (%s) -> ", p->rNo, p->name);
            p = p->next;
        }
        printf("\n");
    }
    printf("---------------------------\n");
}

Linear Probing

Linear probing uses the formula: h(key) = ((h(key) + i) % tablesize)

When a collision occurs, we linearly search for the next available slot.

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

#define SIZE 7

typedef struct {
    int rNo;
    char name[30];
    int mark;
} NODE;

void initTable(NODE ht[], int *n) {
    for (int i = 0; i < SIZE; i++) {
        ht[i].mark = -1;
    }
    *n = 0;
}

int insertRecord(NODE ht[], int rNo, char name[], int *n) {
    if (SIZE == *n) {
        printf("Hash Table is Full!\n");
        return 0;
    }

    int index = rNo % SIZE;

    while (ht[index].mark != -1) {
        if(ht[index].rNo == rNo) {
            printf("Duplicate key %d not allowed.\n", rNo);
            return 0;
        }
        index = (index + 1) % SIZE;
    }

    ht[index].rNo = rNo;
    strcpy(ht[index].name, name);
    ht[index].mark = 1;
    (*n)++;

    printf("Inserted %d at index %d\n", rNo, index);
    return 1;
}

int deleteRecord(NODE ht[], int rNo, int *n) {
    if (*n == 0) return 0;

    int index = rNo % SIZE;
    int i = 0;

    while (i < SIZE && ht[index].mark != -1) {
        if (ht[index].rNo == rNo) {
            ht[index].mark = -1;
            (*n)--;
            return 1;
        }
        index = (index + 1) % SIZE;
        i++;
    }
    return 0;
}

int searchRecord(NODE ht[], int rNo, int *n) {
    if (*n == 0) return 0;

    int index = rNo % SIZE;
    int i = 0;

    while (i < SIZE && ht[index].mark != -1) {
        if (ht[index].rNo == rNo) {
            return 1;
        }
        index = (index + 1) % SIZE;
        i++;
    }
    return 0;
}

void display(NODE ht[]) {
    printf("\n--- Hash Table Status ---\n");
    for (int i = 0; i < SIZE; i++) {
        if (ht[i].mark == 1)
            printf("[%d]: %d (%s)\n", i, ht[i].rNo, ht[i].name);
        else
            printf("[%d]: -- Empty --\n", i);
    }
    printf("-------------------------\n");
}