Graph Representation using Linked List in C

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.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - Queue Program in C

» Next - C Program to Search an Element in a Binary Search Tree

Related Posts:

Recommended Articles: