Question 2 – MCS-209: Data Structures and Algorithms Lab

Question: Write an algorithm and a program in ‘C’ language to insert and delete edges in an adjacency list representation of an undirected graph. Make assumptions, if necessary.

Answer:

Assumptions

1. The graph is undirected.
2. Vertices are numbered from 0 to (V–1).
3. No multiple edges between the same pair of vertices.
4. Adjacency list is implemented using linked lists.
5. Maximum number of vertices is fixed.

---

Algorithm

Algorithm to Insert an Edge (u, v)

1. Check if u and v are valid vertices.
2. Create a new node with value v and insert it at the beginning of adjacency list of u.
3. Create a new node with value u and insert it at the beginning of adjacency list of v.
4. End.

---

Algorithm to Delete an Edge (u, v)

1. Check if u and v are valid vertices.
2. Traverse adjacency list of u and remove the node containing v.
3. Traverse adjacency list of v and remove the node containing u.
4. End.

C Program

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

#define MAX 10

/* Structure for adjacency list node */
struct Node {
    int vertex;
    struct Node* next;
};

/* Adjacency list */
struct Node* adjList[MAX];

/* Function to create a new node */
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

/* Insert edge in undirected graph */
void insertEdge(int u, int v) {
    struct Node* newNode;

    newNode = createNode(v);
    newNode->next = adjList[u];
    adjList[u] = newNode;

    newNode = createNode(u);
    newNode->next = adjList[v];
    adjList[v] = newNode;
}

/* Delete edge in undirected graph */
void deleteEdge(int u, int v) {
    struct Node *temp, *prev;

    /* Delete v from u's list */
    temp = adjList[u];
    prev = NULL;
    while (temp != NULL && temp->vertex != v) {
        prev = temp;
        temp = temp->next;
    }
    if (temp != NULL) {
        if (prev == NULL)
            adjList[u] = temp->next;
        else
            prev->next = temp->next;
        free(temp);
    }

    /* Delete u from v's list */
    temp = adjList[v];
    prev = NULL;
    while (temp != NULL && temp->vertex != u) {
        prev = temp;
        temp = temp->next;
    }
    if (temp != NULL) {
        if (prev == NULL)
            adjList[v] = temp->next;
        else
            prev->next = temp->next;
        free(temp);
    }
}

/* Display the graph */
void display(int V) {
    for (int i = 0; i < V; i++) {
        struct Node* temp = adjList[i];
        printf("Vertex %d: ", i);
        while (temp != NULL) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int V = 5;

    for (int i = 0; i < V; i++)
        adjList[i] = NULL;

    insertEdge(0, 1);
    insertEdge(0, 4);
    insertEdge(1, 2);
    insertEdge(1, 3);

    printf("Graph after insertion:\n");
    display(V);

    deleteEdge(1, 3);

    printf("\nGraph after deletion of edge (1,3):\n");
    display(V);

    return 0;
}

Output (Sample)

Graph after insertion:
Vertex 0: 4 -> 1 -> NULL
Vertex 1: 3 -> 2 -> 0 -> NULL
Vertex 2: 1 -> NULL
Vertex 3: 1 -> NULL
Vertex 4: 0 -> NULL

Graph after deletion of edge (1,3):
Vertex 0: 4 -> 1 -> NULL
Vertex 1: 2 -> 0 -> NULL
Vertex 2: 1 -> NULL
Vertex 3: NULL
Vertex 4: 0 -> NULL