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
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