Name: Adwait Patil
Div: CS-C
Roll No-50
PRN-12310385
ADS assignment 9:
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// Graph using Adjacency Matrix
struct GraphMatrix {
int vertices;
int adj[MAX_VERTICES][MAX_VERTICES];
};
// Graph using Adjacency List
struct Node {
int vertex;
struct Node* next;
};
struct GraphList {
int vertices;
struct Node* adj[MAX_VERTICES];
};
// Function to create a graph using Adjacency Matrix
struct GraphMatrix* createGraphMatrix(int vertices) {
struct GraphMatrix* graph = (struct GraphMatrix*)malloc(sizeof(struct GraphMatrix));
graph->vertices = vertices;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adj[i][j] = 0; // Initialize with no edges
return graph;
// Function to add an edge in Adjacency Matrix
void addEdgeMatrix(struct GraphMatrix* graph, int src, int dest) {
graph->adj[src][dest] = 1; // Directed graph
graph->adj[dest][src] = 1; // Uncomment for undirected graph
// Function for DFS using Adjacency Matrix
void DFSMatrix(struct GraphMatrix* graph, int vertex, int visited[]) {
visited[vertex] = 1;
printf("%d ", vertex);
for (int i = 0; i < graph->vertices; i++) {
if (graph->adj[vertex][i] && !visited[i]) {
DFSMatrix(graph, i, visited);
}
// Function to create a graph using Adjacency List
struct GraphList* createGraphList(int vertices) {
struct GraphList* graph = (struct GraphList*)malloc(sizeof(struct GraphList));
graph->vertices = vertices;
for (int i = 0; i < vertices; i++) {
graph->adj[i] = NULL; // Initialize with no edges
return graph;
// Function to add an edge in Adjacency List
void addEdgeList(struct GraphList* graph, int src, int dest) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = dest;
newNode->next = graph->adj[src];
graph->adj[src] = newNode;
// Uncomment for undirected graph
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = src;
newNode->next = graph->adj[dest];
graph->adj[dest] = newNode;
// Function for DFS using Adjacency List
void DFSList(struct GraphList* graph, int vertex, int visited[]) {
visited[vertex] = 1;
printf("%d ", vertex);
struct Node* temp = graph->adj[vertex];
while (temp) {
if (!visited[temp->vertex]) {
DFSList(graph, temp->vertex, visited);
temp = temp->next;
// Function for BFS using Adjacency List
void BFSList(struct GraphList* graph, int start) {
int visited[MAX_VERTICES] = {0};
int queue[MAX_VERTICES], front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int current = queue[front++];
printf("%d ", current);
struct Node* temp = graph->adj[current];
while (temp) {
if (!visited[temp->vertex]) {
visited[temp->vertex] = 1;
queue[rear++] = temp->vertex;
temp = temp->next;
}
int main() {
int vertices = 5;
// Adjacency Matrix
struct GraphMatrix* graphMatrix = createGraphMatrix(vertices);
addEdgeMatrix(graphMatrix, 0, 1);
addEdgeMatrix(graphMatrix, 0, 4);
addEdgeMatrix(graphMatrix, 1, 2);
addEdgeMatrix(graphMatrix, 1, 3);
addEdgeMatrix(graphMatrix, 1, 4);
addEdgeMatrix(graphMatrix, 2, 3);
addEdgeMatrix(graphMatrix, 3, 4);
printf("DFS using Adjacency Matrix:\n");
int visitedMatrix[MAX_VERTICES] = {0};
DFSMatrix(graphMatrix, 0, visitedMatrix);
printf("\n");
// Adjacency List
struct GraphList* graphList = createGraphList(vertices);
addEdgeList(graphList, 0, 1);
addEdgeList(graphList, 0, 4);
addEdgeList(graphList, 1, 2);
addEdgeList(graphList, 1, 3);
addEdgeList(graphList, 1, 4);
addEdgeList(graphList, 2, 3);
addEdgeList(graphList, 3, 4);
printf("DFS using Adjacency List:\n");
int visitedList[MAX_VERTICES] = {0};
DFSList(graphList, 0, visitedList);
printf("\n");
printf("BFS using Adjacency List:\n");
BFSList(graphList, 0);
printf("\n");
return 0;
