🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
A graph consists of a set of nodes and edges connecting these nodes. One of the common ways to represent a graph in memory is by using an adjacency list. An adjacency list representation of a graph is an array of linked lists. The index of the array represents a vertex, and each element in its linked list represents the other vertices that form an edge with the vertex.
2. Program Overview
This program will:
1. Define a structure for the node of an adjacency list.
2. Initialize an adjacency list for a given number of vertices.
3. Provide functionalities to add an edge and display the list.
3. Code Program
#include <stdio.h>
#include <stdlib.h>
// Define structure for a node in adjacency list
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// Function to create a new node
Node* createNode(int v) {
Node* newNode = malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Number of vertices in the graph
int numVertices;
Node** adjacencyList;
// Function to initialize the adjacency list
void initializeGraph(int vertices) {
numVertices = vertices;
adjacencyList = malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; i++) {
adjacencyList[i] = NULL;
}
}
// Function to add edge
void addEdge(int src, int dest) {
Node* newNode = createNode(dest);
newNode->next = adjacencyList[src];
adjacencyList[src] = newNode;
// As it's an undirected graph, add edge from dest to src
newNode = createNode(src);
newNode->next = adjacencyList[dest];
adjacencyList[dest] = newNode;
}
// Function to print the adjacency list
void printGraph() {
for (int v = 0; v < numVertices; v++) {
Node* temp = adjacencyList[v];
printf("Vertex %d:", v);
while (temp) {
printf(" -> %d", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
int main() {
initializeGraph(5);
addEdge(0, 1);
addEdge(0, 4);
addEdge(1, 3);
addEdge(1, 4);
addEdge(2, 3);
printGraph();
return 0;
}
Output:
Vertex 0: -> 4 -> 1 Vertex 1: -> 4 -> 3 -> 0 Vertex 2: -> 3 Vertex 3: -> 2 -> 1 Vertex 4: -> 1 -> 0
4. Step By Step Explanation
1. We begin by defining a structure Node for our adjacency list. This node holds the vertex number and a pointer to the next node.
2. The createNode function is used to initialize a new node with the given vertex value.
3. We maintain a global pointer, adjacencyList, which points to the array of linked lists for each vertex.
4. The initializeGraph function sets up the initial empty list for all vertices.
5. The addEdge function adds a vertex to the list of another vertex, thus indicating an edge between them. Since we are dealing with an undirected graph, we add connections in both directions.
6. printGraph prints out the adjacency list, allowing us to visually verify our graph structure.
7. The main function demonstrates initializing a graph, adding some edges, and then printing the resulting adjacency list.
This representation is space-efficient for sparse graphs but can become less efficient as the graph becomes denser.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment