Scribd
Upload
3 views3 pages

Graph Representation and Traversal in C

The document contains two C programs for graph representation and traversal. The first program implements a graph using an adjacency list and performs Depth First Search (DFS), while the second program uses an adjacency matrix to represent the graph and calculates the indegree of each vertex. Both programs allow user input for vertices and edges.

Uploaded by

kgxsumitsalunke
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
3 views3 pages

Graph Representation and Traversal in C

The document contains two C programs for graph representation and traversal. The first program implements a graph using an adjacency list and performs Depth First Search (DFS), while the second program uses an adjacency matrix to represent the graph and calculates the indegree of each vertex. Both programs allow user input for vertices and edges.

Uploaded by

kgxsumitsalunke
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd

Q1

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

#define MAX 100

typedef struct Node {


int vertex;
struct Node* next;
} Node;
Node* adjList[MAX];
int visited[MAX];
int vertices;
Node* createNode(int v) {
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

void addEdge(int src, int dest) {


// Add dest to src's list
Node* newNode = createNode(dest);
newNode->next = adjList[src];
adjList[src] = newNode;

void DFS(int vertex) {


visited[vertex] = 1;
printf("%d ", vertex);

Node* temp = adjList[vertex];


while (temp != NULL) {
int adjVertex = temp->vertex;
if (!visited[adjVertex]) {
DFS(adjVertex);
}
temp = temp->next;
}
}

void displayGraph() {
printf("\nAdjacency List:\n");
for (int i = 0; i < vertices; i++) {
Node* temp = adjList[i];
printf("%d: ", i);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("NULL\n");
}
}

int main() {
int edges, src, dest, start;

printf("Enter number of vertices: ");


scanf("%d", &vertices);

for (int i = 0; i < vertices; i++) {


adjList[i] = NULL;
visited[i] = 0;
}

printf("Enter number of edges: ");


scanf("%d", &edges);

printf("Enter edges (source destination):\n");


for (int i = 0; i < edges; i++) {
scanf("%d %d", &src, &dest);
addEdge(src, dest);
}

displayGraph();

printf("Enter starting vertex for DFS: ");


scanf("%d", &start);

printf("DFS Traversal starting from vertex %d: ", start);


DFS(start);
printf("\n");

return 0;
}

Q2

#include <stdio.h>

#define MAX 100

int graph[MAX][MAX];
int indegree[MAX];
int n;

void inputGraph() {
int edges, src, dest;

printf("Enter the number of vertices: ");


scanf("%d", &n);
for (int i = 0; i < n; i++) {
indegree[i] = 0;
for (int j = 0; j < n; j++) {
graph[i][j] = 0;
}
}

printf("Enter the number of edges: ");


scanf("%d", &edges);

printf("Enter the edges (source destination):\n");


for (int i = 0; i < edges; i++) {
scanf("%d %d", &src, &dest);
graph[src][dest] = 1;
}
}
void displayMatrix() {
printf("\nAdjacency Matrix:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
}
void calculateIndegree() {
for (int j = 0; j < n; j++) { // loop through columns
for (int i = 0; i < n; i++) {
if (graph[i][j] == 1)
indegree[j]++;
}
}

printf("\nIndegree of each vertex:\n");


for (int i = 0; i < n; i++) {
printf("Vertex %d: %d\n", i, indegree[i]);
}
}

int main() {
inputGraph();
displayMatrix();
calculateIndegree();

return 0;
}

You might also like