Scribd
Upload
5 views3 pages

Graph Algorithms in C: DFS & Dijkstra

The document contains two C programs: the first implements a graph using adjacency lists and performs a Depth First Search (DFS) starting from a specified vertex, while the second implements Dijkstra's algorithm to find the shortest paths from a starting vertex in a weighted graph represented by an adjacency matrix. Both programs include necessary functions for creating graphs, adding edges, and traversing or calculating distances. The first program outputs the DFS traversal order, and the second outputs the shortest distances from the source vertex.

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
5 views3 pages

Graph Algorithms in C: DFS & Dijkstra

The document contains two C programs: the first implements a graph using adjacency lists and performs a Depth First Search (DFS) starting from a specified vertex, while the second implements Dijkstra's algorithm to find the shortest paths from a starting vertex in a weighted graph represented by an adjacency matrix. Both programs include necessary functions for creating graphs, adding edges, and traversing or calculating distances. The first program outputs the DFS traversal order, and the second outputs the shortest distances from the source vertex.

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


struct Node {
int vertex;
struct Node* next;
};
struct Graph {
int numVertices;
struct Node** adjLists;
int* visited;
};
struct Node* createNode(int vertex) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = vertex;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;

graph->adjLists = malloc(vertices * sizeof(struct Node*));


graph->visited = malloc(vertices * sizeof(int));

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


graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}

return graph;
}
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
void DFS(struct Graph* graph, int vertex) {
struct Node* adjList = graph->adjLists[vertex];
struct Node* temp = adjList;

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

while (temp != NULL) {


int connectedVertex = temp->vertex;

if (graph->visited[connectedVertex] == 0) {
DFS(graph, connectedVertex);
}
temp = temp->next;
}
}
int main() {
int vertices = 6;

struct Graph* graph = createGraph(vertices);

addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 5);

printf("Depth First Search starting from vertex 0:\n");


DFS(graph, 0);

return 0;
}

Q2

#include <stdio.h>
#define INFINITY 9999
#define MAX 10

void dijkstra(int cost[MAX][MAX], int n, int start) {


int distance[MAX], visited[MAX], count, minDistance, nextNode, i, j;
for (i = 0; i < n; i++) {
distance[i] = cost[start][i];
visited[i] = 0;
}

distance[start] = 0;
visited[start] = 1;
count = 1;
while (count < n - 1) {
minDistance = INFINITY;
for (i = 0; i < n; i++) {
if (distance[i] < minDistance && !visited[i]) {
minDistance = distance[i];
nextNode = i;
}
}

visited[nextNode] = 1;
for (i = 0; i < n; i++) {
if (!visited[i]) {
if (minDistance + cost[nextNode][i] < distance[i]) {
distance[i] = minDistance + cost[nextNode][i];
}
}
}

count++;
}
printf("\nShortest distances from source %d:\n", start);
for (i = 0; i < n; i++) {
printf("To vertex %d: %d\n", i, distance[i]);
}
}
int main() {
int cost[MAX][MAX], i, j, n, start;

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


scanf("%d", &n);

printf("Enter the cost adjacency matrix (use %d for no direct edge):\n",


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

printf("Enter the starting vertex (0 to %d): ", n - 1);


scanf("%d", &start);

dijkstra(cost, n, start);

return 0;
}

You might also like