{"id":2313,"date":"2025-12-13T18:31:09","date_gmt":"2025-12-13T18:31:09","guid":{"rendered":"https:\/\/www.ignoubcamca.com\/forum\/?p=2313"},"modified":"2025-12-21T16:49:11","modified_gmt":"2025-12-21T16:49:11","slug":"write-an-algorithm-and-program-in-c-language-to-merge-two-sorted-linked-lists-the-resultant-linked-list-should-be-sortedmcs-209-q-2-data-structures-and-algorithms-lab","status":"publish","type":"post","link":"https:\/\/www.ignoubcamca.com\/forum\/write-an-algorithm-and-program-in-c-language-to-merge-two-sorted-linked-lists-the-resultant-linked-list-should-be-sortedmcs-209-q-2-data-structures-and-algorithms-lab\/","title":{"rendered":"Write an algorithm and program in \u2018C\u2019 language to merge two sorted linked lists. The resultant linked list should be sorted [MCS-209 Q-2]"},"content":{"rendered":"\n

Question:<\/strong> Write an algorithm and a program in \u2018C\u2019 language to insert and delete edges in an adjacency list representation of an undirected graph. Make assumptions, if necessary.<\/p>\n\n\n\n

Answer:<\/strong><\/p>\n\n\n\n

Assumptions<\/h3>\n\n\n\n
    \n
  1. The graph is undirected<\/strong>.<\/li>\n\n\n\n
  2. Vertices are numbered from 0 to (V\u20131)<\/strong>.<\/li>\n\n\n\n
  3. No multiple edges between the same pair of vertices.<\/li>\n\n\n\n
  4. Adjacency list is implemented using linked lists<\/strong>.<\/li>\n\n\n\n
  5. Maximum number of vertices is fixed. <\/li>\n<\/ol>\n\n\n\n\n\n\n\n
    \n\n\n\n

    Algorithm<\/h3>\n\n\n\n

    Algorithm to Insert an Edge (u, v)<\/code><\/h3>\n\n\n\n
      \n
    1. Check if u<\/code> and v<\/code> are valid vertices.<\/li>\n\n\n\n
    2. Create a new node with value v<\/code> and insert it at the beginning of adjacency list of u<\/code>.<\/li>\n\n\n\n
    3. Create a new node with value u<\/code> and insert it at the beginning of adjacency list of v<\/code>.<\/li>\n\n\n\n
    4. End.<\/li>\n<\/ol>\n\n\n\n
      \n\n\n\n

      Algorithm to Delete an Edge (u, v)<\/code><\/h3>\n\n\n\n
        \n
      1. Check if u<\/code> and v<\/code> are valid vertices.<\/li>\n\n\n\n
      2. Traverse adjacency list of u<\/code> and remove the node containing v<\/code>.<\/li>\n\n\n\n
      3. Traverse adjacency list of v<\/code> and remove the node containing u<\/code>.<\/li>\n\n\n\n
      4. End.<\/li>\n<\/ol>\n\n\n\n

        C Program<\/strong><\/p>\n\n\n\n

        #include <stdio.h>\n#include <stdlib.h>\n\n#define MAX 10\n\n\/* Structure for adjacency list node *\/\nstruct Node {\n    int vertex;\n    struct Node* next;\n};\n\n\/* Adjacency list *\/\nstruct Node* adjList[MAX];\n\n\/* Function to create a new node *\/\nstruct Node* createNode(int v) {\n    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));\n    newNode->vertex = v;\n    newNode->next = NULL;\n    return newNode;\n}\n\n\/* Insert edge in undirected graph *\/\nvoid insertEdge(int u, int v) {\n    struct Node* newNode;\n\n    newNode = createNode(v);\n    newNode->next = adjList[u];\n    adjList[u] = newNode;\n\n    newNode = createNode(u);\n    newNode->next = adjList[v];\n    adjList[v] = newNode;\n}\n\n\/* Delete edge in undirected graph *\/\nvoid deleteEdge(int u, int v) {\n    struct Node *temp, *prev;\n\n    \/* Delete v from u's list *\/\n    temp = adjList[u];\n    prev = NULL;\n    while (temp != NULL && temp->vertex != v) {\n        prev = temp;\n        temp = temp->next;\n    }\n    if (temp != NULL) {\n        if (prev == NULL)\n            adjList[u] = temp->next;\n        else\n            prev->next = temp->next;\n        free(temp);\n    }\n\n    \/* Delete u from v's list *\/\n    temp = adjList[v];\n    prev = NULL;\n    while (temp != NULL && temp->vertex != u) {\n        prev = temp;\n        temp = temp->next;\n    }\n    if (temp != NULL) {\n        if (prev == NULL)\n            adjList[v] = temp->next;\n        else\n            prev->next = temp->next;\n        free(temp);\n    }\n}\n\n\/* Display the graph *\/\nvoid display(int V) {\n    for (int i = 0; i < V; i++) {\n        struct Node* temp = adjList[i];\n        printf(\"Vertex %d: \", i);\n        while (temp != NULL) {\n            printf(\"%d -> \", temp->vertex);\n            temp = temp->next;\n        }\n        printf(\"NULL\\n\");\n    }\n}\n\nint main() {\n    int V = 5;\n\n    for (int i = 0; i < V; i++)\n        adjList[i] = NULL;\n\n    insertEdge(0, 1);\n    insertEdge(0, 4);\n    insertEdge(1, 2);\n    insertEdge(1, 3);\n\n    printf(\"Graph after insertion:\\n\");\n    display(V);\n\n    deleteEdge(1, 3);\n\n    printf(\"\\nGraph after deletion of edge (1,3):\\n\");\n    display(V);\n\n    return 0;\n}\n<\/code><\/pre>\n\n\n\n
        Output (Sample)<\/p>\n\n\n\n
        Graph after insertion:\nVertex 0: 4 -> 1 -> NULL\nVertex 1: 3 -> 2 -> 0 -> NULL\nVertex 2: 1 -> NULL\nVertex 3: 1 -> NULL\nVertex 4: 0 -> NULL\n\nGraph after deletion of edge (1,3):\nVertex 0: 4 -> 1 -> NULL\nVertex 1: 2 -> 0 -> NULL\nVertex 2: 1 -> NULL\nVertex 3: NULL\nVertex 4: 0 -> NULL\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
        Question: Write an algorithm and a program in \u2018C\u2019 language to insert and delete edges in an adjacency list representation of an undirected graph. Make assumptions, if necessary. Answer: Assumptions<\/p>\n","protected":false},"author":1,"featured_media":2351,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[29,30],"tags":[],"class_list":["post-2313","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-bca-assignment","category-january-2026"],"_links":{"self":[{"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/posts\/2313","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/comments?post=2313"}],"version-history":[{"count":4,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/posts\/2313\/revisions"}],"predecessor-version":[{"id":2358,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/posts\/2313\/revisions\/2358"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/media\/2351"}],"wp:attachment":[{"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/media?parent=2313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/categories?post=2313"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.ignoubcamca.com\/forum\/wp-json\/wp\/v2\/tags?post=2313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}