Adjacency List Code
Adjacency List is one of the best way of representing a graph through computer code. In this code, connection in between two adjacent nodes is represented in the adjacency list. This adjacency list is represented using Linked List and one linked list is created for each node’s adjacent node connection and representation.
Adjacency list code is a more efficient way to represent graphs than adjacency matrix code, especially for large graphs. This is because it requires only O(E) space, where E is the number of edges in the graph.
For Such more codes click here and for video tutorial click here.
//Adjacency List using Linked List
// -
// November 15, 2016
// Create Adjacency List using Linked List
#include<stdio.h>
#include<stdlib.h>
// #include<conio.h>
typedef struct Link {
int val;
struct Link * next;
}
lnk;
typedef struct Graph {
lnk * node;
struct Graph * link;
}
gr;
gr * create(int);
void displist(gr * );
void dispnode(lnk * );
lnk * createnode(int, int);
void main() {
int i, j, m, n;
lnk * temp;
gr * list = NULL, * ptr, * tempo;
printf("Enter the total number node : ");
scanf("%d", & m);
list = create(m);
printf("Adjacency List is : \n");
displist(list);
}
gr * create(int g) {
gr * head = NULL, * temp, * ptr;
int i;
for (i = 0; i < g; i++) {
printf("\n===========================================\n");
temp = (gr * ) malloc(sizeof(gr));
temp -> node = createnode(i, g);
temp -> link = NULL;
if (temp -> node != NULL) {
if (head == NULL)
head = temp;
else
ptr -> link = temp;
ptr = temp;
}
}
return head;
}
lnk * createnode(int p, int m) {
lnk * head = NULL, * temp, * ptr;
int i;
char ch;
for (i = 0; i < m; i++) {
printf("%d is connected with %d ?:", p + 1, i + 1);
fflush(stdin);
scanf(" %c", &ch);
if (ch == 'y' || ch == 'Y') {
temp = (lnk * ) malloc(sizeof(lnk));
temp -> val = i + 1;
temp -> next = NULL;
if (head == NULL)
head = temp;
else
ptr -> next = temp;
ptr = temp;
}
}
return head;
}
void displist(gr * head) {
lnk * adjnode;
int i = 1;
while (head != NULL) {
printf(" %d is connected with : ", i++);
adjnode = head -> node;
dispnode(adjnode);
printf("\n=================================\n");
head = head -> link;
}
}
void dispnode(lnk * head) {
while (head != NULL) {
printf("%d => ", head -> val);
head = head -> next;
}
printf("END");
}
