Skip to main content

Adjacency list representation of undirected graph in c

C program for Adjacency list representation of undirected graph. Here problem description and explanation.

// C program for
// Adjacency list representation of Un-Directed graph
#include <stdio.h>
#include <stdlib.h>

struct AjlistNode
{
    int id;
    // Vertices id
    struct AjlistNode *next;
};
struct Vertices
{
    int data;
    struct AjlistNode *next;
    struct AjlistNode *last;
};
struct Graph
{
    int size;
    struct Vertices*node;
};
//set node key value
void setData(struct Graph *g)
{
    if (g->node != NULL)
    {
        int index = 0;
        for (int index = 0; index < g->size; index++)
        {
            // Set vertic node data
            g->node[index].data = index; 
    
            // Set NULL Value
            g->node[index].next = NULL;
            g->node[index].next = NULL;
        }
    }
    else
    {
        printf("Vertic Node is Empty");
    }
}

// Return new graph
struct Graph *newGraph(int size)
{
    if (size < 1)
    {
        printf("\n Invalid graph size ");
        exit(0);
    }
    struct Graph *g = (struct Graph *) malloc(sizeof(struct Graph));
    g->size = size;
    g->node = (struct Vertices *) malloc(sizeof(struct Vertices) *size);
    setData(g);
    return g;
}

// Connect two nodes
void connect(struct Graph *g, int start, int last)
{
    // First create Adjacency node
    struct AjlistNode *edge = (struct AjlistNode *) malloc(sizeof(struct AjlistNode));
 
     
    if (edge != NULL)
    {
        edge->id = last;
        edge->next = NULL;


        if (g->node[start].next == NULL)
        {
            g->node[start].next = edge;
        }
        else
        {
            // Add edge at the end
            g->node[start].last->next = edge;
        }
        // Get last edge 
        g->node[start].last = edge;
    }
    else
    {
        printf("\n Memory overflow to create edge");
    }
}
// Add Edge from Two given Nodes
void addEdge(struct Graph *g, int start, int last)
{
    
    if (start < g->size && last < g->size)
    {
       connect(g,start,last);

       if(start==last)
       {
        //self loop
         return;
       }
       connect(g,last,start);
    }
    else
    {
        //not valid Vertices
        printf("Invalid Node Vertices %d  %d", start, last);
    }
}
//Display Adjacency list of vertex
void printGraph(struct Graph *g)
{
    if (g != NULL)
    {
        struct AjlistNode *temp = NULL;
        for (int index = 0; index < g->size; index++)
        {
            printf("\n Adjacency list of vertex %d  :", index);
            temp =  g->node[index].next;
            while (temp != NULL)
            {
                //temp->id is graph node vertices
                //in this case temp->id is same as 
                //node[temp->id].data
                printf("  %d",  g->node[temp->id].data);
                temp = temp->next;
            }
        }
    }
    else
    {
        printf("Empty Graph");
    }
}
int main()
{
    struct Graph *g = newGraph(5);

    // Connected two node with Edges
    addEdge(g,0,1);
    addEdge(g,0,2);
    addEdge(g,0,4);
    addEdge(g,1,2);
    addEdge(g,1,4);
    addEdge(g,2,3);
    addEdge(g,3,4);

    printGraph(g);
  
    return 0;
}

Output

 Adjacency list of vertex 0  :  1  2  4
 Adjacency list of vertex 1  :  0  2  4
 Adjacency list of vertex 2  :  0  1  3
 Adjacency list of vertex 3  :  2  4
 Adjacency list of vertex 4  :  0  1  3




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment