Adjacency List Representation of Graph

Adjacency List Representation of Graph in C Programming

The adjacency list representation of a graph is a way to store a graph in memory using a collection of lists or arrays. It is one of the most common and efficient ways to represent sparse graphs (graphs with relatively few edges compared to the number of vertices).

Concept of Adjacency List Representation

In the adjacency list representation:

Each vertex in the graph is associated with a list (or array) that contains all the vertices adjacent to it.

For a directed graph, the list for a vertex contains only the vertices to which it has outgoing edges.

For an undirected graph, the list for a vertex contains all the vertices connected to it by an edge.

This representation is space-efficient for sparse graphs because it only stores the edges that exist, unlike the adjacency matrix.

Example

Consider the following undirected graph:

Vertices: 1, 2, 3, 4
Edges: (1, 2), (1, 3), (2, 4), (3, 4)
The adjacency list representation of this graph would be:

1 -> [2, 3]
2 -> [1, 4]
3 -> [1, 4]
4 -> [2, 3]

For a directed graph, the adjacency list would only include the vertices to which there are outgoing edges. For example, if the graph is directed as follows:

Edges: (1, 2), (1, 3), (2, 4), (3, 4)
The adjacency list representation would be:

1 -> [2, 3]
2 -> [4]
3 -> [4]
4 -> []

Assignment 4. Set A a) SPPU:

Write a C program that accepts the vertices and edges of graph (undirected graph) . Create adjacency list and display the adjacency list.

#include <stdio.h>
#include <stdlib.h>

// Structure for a node in the adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Structure for the graph
struct Graph {
    int numVertices;
    struct Node** adjLists;
};

// Function to create a new node
struct Node* createNode(int v) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    // Create an array of adjacency lists
    graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));

    // Initialize each adjacency list as empty
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // For undirected graphs, add edge from dest to src as well
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// Function to display the adjacency list
void displayGraph(struct Graph* graph) {
    printf("Adjacency List Representation of the Graph:\n");
    for (int v = 0; v < graph->numVertices; v++) {
        struct Node* temp = graph->adjLists[v];
        printf("Vertex %d: ", v);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int vertices, edges;
    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    // Create a graph with the given number of vertices
    struct Graph* graph = createGraph(vertices);

    printf("Enter the number of edges: ");
    scanf("%d", &edges);

    // Add edges to the graph
    for (int i = 0; i < edges; i++) {
        int src, dest;
        printf("Enter edge %d (source destination): ", i + 1);
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    // Display the adjacency list
    displayGraph(graph);

    return 0;
}

Assignment 4. Set A b) SPPU:

Write a C program that accepts the vertices and edges of a graph. create adjacency list. implement functions to print indegree, outdegree and total degree of all vertices of graph.

Finding Degree, In-degree, and Out-degree of a Graph

1. Graph Representation

A graph consists of a set of vertices and a set of edges .
Graphs can be directed or undirected:
- Undirected Graph: Edges have no direction. An edge is the same as
- Directed Graph (Digraph): Edges have a direction. An edge is different from

2. Degree of a Vertex

The degree of a vertex in a graph is the number of edges incident to it.
In undirected graphs:
- Degree of a vertex , denoted as , is the number of edges connected to .
- Example: If $v$ is connected to 3 edges,
In directed graphs:
- Degree is split into in-degree and out-degree.

3. In-degree of a Vertex

The in-degree of a vertex in a directed graph is the number of edges coming into .
Denoted as
Example: If there are 2 edges pointing to ,

4. Out-degree of a Vertex

The out-degree of a vertex $v$ in a directed graph is the number of edges going out of $v$ .
Denoted as
Example: If has 3 edges leaving it,

5. Total Degree of a Vertex

In a directed graph, the total degree of a vertex $v$ is the sum of its in-degree and out-degree:
In an undirected graph, the total degree is simply the degree of the vertex.

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an adjacency list node
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// Structure to represent an adjacency list
struct AdjList {
    struct AdjListNode* head;
};

// Structure to represent a graph
struct Graph {
    int V;
    struct AdjList* array;
};

// Function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph with V vertices
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;

    // Create an array of adjacency lists. Size of array will be V
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));

    // Initialize each adjacency list as empty by making head as NULL
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;

    return graph;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
    // Add an edge from src to dest
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}

// Function to print the out-degree of all vertices
void printOutDegree(struct Graph* graph) {
    printf("Out-degree of all vertices:\n");
    for (int i = 0; i < graph->V; i++) {
        int outDegree = 0;
        struct AdjListNode* temp = graph->array[i].head;
        while (temp) {
            outDegree++;
            temp = temp->next;
        }
        printf("Vertex %d: %d\n", i, outDegree);
    }
}

// Function to print the in-degree of all vertices
void printInDegree(struct Graph* graph) {
    printf("In-degree of all vertices:\n");
    int* inDegree = (int*)calloc(graph->V, sizeof(int));

    for (int i = 0; i < graph->V; i++) {
        struct AdjListNode* temp = graph->array[i].head;
        while (temp) {
            inDegree[temp->dest]++;
            temp = temp->next;
        }
    }

    for (int i = 0; i < graph->V; i++) {
        printf("Vertex %d: %d\n", i, inDegree[i]);
    }

    free(inDegree);
}

// Function to print the total degree of all vertices
void printTotalDegree(struct Graph* graph) {
    printf("Total degree of all vertices:\n");
    int* inDegree = (int*)calloc(graph->V, sizeof(int));

    // Calculate in-degree
    for (int i = 0; i < graph->V; i++) {
        struct AdjListNode* temp = graph->array[i].head;
        while (temp) {
            inDegree[temp->dest]++;
            temp = temp->next;
        }
    }

    // Calculate total degree (in-degree + out-degree)
    for (int i = 0; i < graph->V; i++) {
        int outDegree = 0;
        struct AdjListNode* temp = graph->array[i].head;
        while (temp) {
            outDegree++;
            temp = temp->next;
        }
        printf("Vertex %d: %d\n", i, inDegree[i] + outDegree);
    }

    free(inDegree);
}

// Main function
int main() {
    int V, E;
    printf("Enter the number of vertices: ");
    scanf("%d", &V);
    printf("Enter the number of edges: ");
    scanf("%d", &E);

    struct Graph* graph = createGraph(V);

    printf("Enter the edges (source destination):\n");
    for (int i = 0; i < E; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    printOutDegree(graph);
    printInDegree(graph);
    printTotalDegree(graph);

    return 0;
}

Assignment 4. Set B (a) SPPU:

Write a C program that accepts the vertices and edges of a graph and store it as an adjacency list. Implement function to traverse the graph using Breadth First Search (BFS) traversal.

#include <stdio.h>

#include <stdlib.h>
#include <stdbool.h>

// Structure for adjacency list node
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// Structure for adjacency list
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// Structure for graph
typedef struct Graph {
    int numVertices;
    AdjList* array;
} Graph;

// Queue structure for BFS
typedef struct QueueNode {
    int data;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode *front, *rear;
} Queue;

// Function to create a new adjacency list node
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph of given number of vertices
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    
    // Create an array of adjacency lists
    graph->array = (AdjList*)malloc(numVertices * sizeof(AdjList));
    
    // Initialize each adjacency list as empty
    for (int i = 0; i < numVertices; ++i) {
        graph->array[i].head = NULL;
    }
    
    return graph;
}

// Function to add an edge to an undirected graph
void addEdge(Graph* graph, int src, int dest) {
    // Add an edge from src to dest
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
    
    // Since graph is undirected, add an edge from dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Function to print the adjacency list representation of graph
void printGraph(Graph* graph) {
    printf("\nAdjacency List Representation:\n");
    for (int v = 0; v < graph->numVertices; ++v) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("\nVertex %d: ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

// Queue operations for BFS
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, int data) {
    QueueNode* temp = (QueueNode*)malloc(sizeof(QueueNode));
    temp->data = data;
    temp->next = NULL;
    
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }
    
    q->rear->next = temp;
    q->rear = temp;
}

int dequeue(Queue* q) {
    if (q->front == NULL) {
        return -1;
    }
    
    QueueNode* temp = q->front;
    int item = temp->data;
    q->front = q->front->next;
    
    if (q->front == NULL) {
        q->rear = NULL;
    }
    
    free(temp);
    return item;
}

bool isEmpty(Queue* q) {
    return q->front == NULL;
}

// BFS traversal function
void BFS(Graph* graph, int startVertex) {
    // Create a visited array and initialize all vertices as not visited
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }
    
    // Create a queue for BFS
    Queue* q = createQueue();
    
    // Mark the current node as visited and enqueue it
    visited[startVertex] = true;
    enqueue(q, startVertex);
    
    printf("\nBFS Traversal starting from vertex %d:\n", startVertex);
    
    while (!isEmpty(q)) {
        // Dequeue a vertex from queue and print it
        int currentVertex = dequeue(q);
        printf("%d ", currentVertex);
        
        // Get all adjacent vertices of the dequeued vertex
        AdjListNode* temp = graph->array[currentVertex].head;
        while (temp != NULL) {
            int adjVertex = temp->dest;
            
            // If adjacent vertex is not visited, mark it visited and enqueue it
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                enqueue(q, adjVertex);
            }
            temp = temp->next;
        }
    }
    printf("\n");
    
    free(visited);
    free(q);
}

int main() {
    int vertices, edges, src, dest;
    int startVertex;
    
    printf("Graph Traversal using BFS Algorithm (Adjacency List)\n");
    printf("===================================================\n\n");
    
    printf("Enter number of vertices: ");
    scanf("%d", &vertices);
    
    // Create graph
    Graph* graph = createGraph(vertices);
    
    printf("Enter number of edges: ");
    scanf("%d", &edges);
    
    printf("\nEnter edges (source destination):\n");
    for (int i = 0; i < edges; i++) {
        printf("Edge %d: ", i + 1);
        scanf("%d %d", &src, &dest);
        
        // Validate input
        if (src >= vertices || dest >= vertices || src < 0 || dest < 0) {
            printf("Invalid edge! Vertex numbers must be between 0 and %d\n", vertices - 1);
            i--; // Retry this edge
            continue;
        }
        
        addEdge(graph, src, dest);
    }
    
    // Print the adjacency list representation of the graph
    printGraph(graph);
    
    printf("\nEnter starting vertex for BFS (0 to %d): ", vertices - 1);
    scanf("%d", &startVertex);
    
    // Validate starting vertex
    if (startVertex < 0 || startVertex >= vertices) {
        printf("Invalid starting vertex!\n");
    } else {
        BFS(graph, startVertex);
    }
    
    // Free memory
    // Note: In a real program, you would need to properly free all allocated memory
    // including all nodes in the adjacency lists
    free(graph->array);
    free(graph);
    
    return 0;
}

Assignment 4. Set B (b) SPPU:

Write a C program that accepts the vertices and edges of a graph and store it as an adjacency list. Implement function to traverse the graph using Depth First Search (DFS) traversal.

#include <stdlib.h>
#include <stdbool.h>

// Structure for adjacency list node
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// Structure for adjacency list
typedef struct AdjList {
    AdjListNode* head;
} AdjList;

// Structure for graph
typedef struct Graph {
    int numVertices;
    AdjList* array;
} Graph;

// Function to create a new adjacency list node
AdjListNode* newAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// Function to create a graph of given number of vertices
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    if (!graph) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    
    graph->numVertices = numVertices;
    graph->array = (AdjList*)malloc(numVertices * sizeof(AdjList));
    if (!graph->array) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    
    // Initialize each adjacency list as empty
    for (int i = 0; i < numVertices; ++i) {
        graph->array[i].head = NULL;
    }
    
    return graph;
}

// Function to add an edge to an undirected graph
void addEdge(Graph* graph, int src, int dest) {
    // Validate input
    if (src >= graph->numVertices || dest >= graph->numVertices || src < 0 || dest < 0) {
        printf("Invalid edge: %d-%d\n", src, dest);
        return;
    }
    
    // Add edge from src to dest
    AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
    
    // Since graph is undirected, add edge from dest to src also
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// Function to print the adjacency list representation of graph
void printGraph(Graph* graph) {
    printf("\nAdjacency List Representation:\n");
    for (int v = 0; v < graph->numVertices; ++v) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("Vertex %d: ", v);
        while (pCrawl) {
            printf("-> %d", pCrawl->dest);
            pCrawl = pCrawl->next;
        }
        printf("\n");
    }
}

// Recursive DFS utility function
void DFSUtil(Graph* graph, int vertex, bool visited[]) {
    // Mark the current node as visited and print it
    visited[vertex] = true;
    printf("%d ", vertex);

    // Recur for all vertices adjacent to this vertex
    AdjListNode* temp = graph->array[vertex].head;
    while (temp != NULL) {
        int adjVertex = temp->dest;
        if (!visited[adjVertex]) {
            DFSUtil(graph, adjVertex, visited);
        }
        temp = temp->next;
    }
}

// DFS traversal function
void DFS(Graph* graph, int startVertex) {
    // Validate starting vertex
    if (startVertex < 0 || startVertex >= graph->numVertices) {
        printf("Invalid starting vertex!\n");
        return;
    }

    // Create a visited array and initialize all vertices as not visited
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    if (!visited) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }

    printf("\nDFS Traversal starting from vertex %d:\n", startVertex);
    DFSUtil(graph, startVertex, visited);
    printf("\n");

    free(visited);
}

// Function to free graph memory
void freeGraph(Graph* graph) {
    if (graph) {
        if (graph->array) {
            for (int v = 0; v < graph->numVertices; ++v) {
                AdjListNode* temp = graph->array[v].head;
                while (temp) {
                    AdjListNode* toDelete = temp;
                    temp = temp->next;
                    free(toDelete);
                }
            }
            free(graph->array);
        }
        free(graph);
    }
}

int main() {
    int vertices, edges, src, dest;
    int startVertex;
    
    printf("Graph Traversal using DFS Algorithm (Adjacency List)\n");
    printf("===================================================\n\n");
    
    printf("Enter number of vertices: ");
    scanf("%d", &vertices);
    
    // Create graph
    Graph* graph = createGraph(vertices);
    
    printf("Enter number of edges: ");
    scanf("%d", &edges);
    
    printf("\nEnter edges (source destination):\n");
    for (int i = 0; i < edges; i++) {
        printf("Edge %d: ", i + 1);
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }
    
    // Print the adjacency list representation of the graph
    printGraph(graph);
    
    printf("\nEnter starting vertex for DFS (0 to %d): ", vertices - 1);
    scanf("%d", &startVertex);
    
    // Perform DFS traversal
    DFS(graph, startVertex);
    
    // Free memory
    freeGraph(graph);
    
    return 0;
}