This is a C Program to generates graph using Linked List Method. In this representation, the n rows of the adjacency matrix are represented as n linked lists. There is one list for each vertex in G. The nodes in list i represent the vertices that are adjacent from vertex i. Each node has at least two fields : vertex and next.
Here is source code of the C Program to Represent Graph Using Linked List. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
#include <stdio.h>
#include <stdlib.h>
#define new_node (struct node*)malloc(sizeof(struct node))
struct node {
int vertex;
struct node *next;
};
void main() {
int option;
do {
printf(
"\n A Program to represent a Graph by using an Linked List \n ");
printf("\n 1. Directed Graph ");
printf("\n 2. Un-Directed Graph ");
printf("\n 3. Exit ");
printf("\n\n Select a proper option : ");
scanf("%d", &option);
switch (option) {
case 1:
dir_graph();
break;
case 2:
undir_graph();
break;
case 3:
exit(0);
}
} while (1);
}
int dir_graph() {
struct node *adj_list[10], *p;
int n;
int in_deg, out_deg, i, j;
printf("\n How Many Vertices ? : ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
adj_list[i] = NULL;
read_graph(adj_list, n);
printf("\n Vertex \t In_Degree \t Out_Degree \t Total_Degree ");
for (i = 1; i <= n; i++) {
in_deg = out_deg = 0;
p = adj_list[i];
while (p != NULL) {
out_deg++;
p = p -> next;
}
for (j = 1; j <= n; j++) {
p = adj_list[j];
while (p != NULL) {
if (p -> vertex == i)
in_deg++;
p = p -> next;
}
}
printf("\n\n %5d\t\t\t%d\t\t%d\t\t%d\n\n", i, in_deg, out_deg,
in_deg + out_deg);
}
return;
}
int undir_graph() {
struct node *adj_list[10], *p;
int deg, i, j, n;
printf("\n How Many Vertices ? : ");
scanf("%d", &n);
for (i = 1; i <= n; i++)
adj_list[i] = NULL;
read_graph(adj_list, n);
printf("\n Vertex \t Degree ");
for (i = 1; i <= n; i++) {
deg = 0;
p = adj_list[i];
while (p != NULL) {
deg++;
p = p -> next;
}
printf("\n\n %5d \t\t %d\n\n", i, deg);
}
return;
}
int read_graph(struct node *adj_list[10], int n) {
int i, j;
char reply;
struct node *p, *c;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
if (i == j)
continue;
printf("\n Vertices %d & %d are Adjacent ? (Y/N) :", i, j);
scanf("%c", &reply);
if (reply == 'y' || reply == 'Y') {
c = new_node;
c -> vertex = j;
c -> next = NULL;
if (adj_list[i] == NULL)
adj_list[i] = c;
else {
p = adj_list[i];
while (p -> next != NULL)
p = p -> next;
p -> next = c;
}
}
}
}
return;
}
Output:
$ gcc GraphUsingLinkedLIst.c $ ./a.out A Program to represent a Graph by using an Liniked Matrix method 1. Directed Graph 2. Un-Directed Graph 3. Exit Select a proper option : How Many Vertices ? : Vertices 1 & 2 are Adjacent ? (Y/N) : N Vertices 1 & 3 are Adjacent ? (Y/N) : Y Vertices 1 & 4 are Adjacent ? (Y/N) : Y Vertices 2 & 1 are Adjacent ? (Y/N) : Y Vertices 2 & 3 are Adjacent ? (Y/N) : Y Vertices 2 & 4 are Adjacent ? (Y/N) : N Vertices 3 & 1 are Adjacent ? (Y/N) : Y Vertices 3 & 2 are Adjacent ? (Y/N) : Y Vertices 3 & 4 are Adjacent ? (Y/N) : Y Vertices 4 & 1 are Adjacent ? (Y/N) : Y Vertices 4 & 2 are Adjacent ? (Y/N) : N Vertices 4 & 3 are Adjacent ? (Y/N) : Y Vertex In_Degree Out_Degree Total_Degree 1 2 0 2 2 1 2 3 3 0 1 1 4 1 1 2 A Program to represent a Graph by using an Adjacency Matrix method 1. Directed Graph 2. Un-Directed Graph 3. Exit
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Related Posts:
- Check Programming Books
- Check Computer Science Books
- Check Data Structure Books
- Practice Programming MCQs
- Apply for Computer Science Internship