Assignment 4: Graph Applications
Set A
a) Write a C program for the implementation of Topological sorting.
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 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;
int* visited;
};
// Structure for the stack
struct Stack {
int data[MAX_VERTICES];
int top;
};
// 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;
graph->adjLists = (struct Node**)malloc(vertices * sizeof(struct Node*));
graph->visited = (int*)malloc(vertices * sizeof(int));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Function to add an edge to the graph
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
// Function to initialize the stack
void initializeStack(struct Stack* stack) {
stack->top = -1;
}
// Function to push a vertex onto the stack
void push(struct Stack* stack, int vertex) {
if (stack->top == MAX_VERTICES - 1) {
printf("Stack overflow!\n");
return;
}
stack->data[++stack->top] = vertex;
}
// Function to pop a vertex from the stack
int pop(struct Stack* stack) {
if (stack->top == -1) {
printf("Stack underflow!\n");
return -1;
}
return stack->data[stack->top--];
}
// Recursive function for topological sort
void topologicalSortUtil(struct Graph* graph, int vertex, struct Stack* stack) {
graph->visited[vertex] = 1; // Mark the current vertex as visited
// Traverse all adjacent vertices
struct Node* temp = graph->adjLists[vertex];
while (temp != NULL) {
int adjVertex = temp->vertex;
if (!graph->visited[adjVertex]) {
topologicalSortUtil(graph, adjVertex, stack);
}
temp = temp->next;
}
// Push the current vertex onto the stack
push(stack, vertex);
}
// Function to perform topological sort
void topologicalSort(struct Graph* graph) {
struct Stack stack;
initializeStack(&stack);
// Perform DFS for all unvisited vertices
for (int i = 0; i < graph->numVertices; i++) {
if (!graph->visited[i]) {
topologicalSortUtil(graph, i, &stack);
}
}
// Print the topological order (vertices popped from the stack)
printf("Topological Order: ");
while (stack.top != -1) {
printf("%d ", pop(&stack));
}
printf("\n");
}
int main() {
int vertices, edges;
printf("Enter the number of vertices: ");
scanf("%d", &vertices);
printf("Enter the number of edges: ");
scanf("%d", &edges);
struct Graph* graph = createGraph(vertices);
printf("Enter the edges (source destination):\n");
for (int i = 0; i < edges; i++) {
int src, dest;
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
topologicalSort(graph);
return 0;
}
b) Write a C program for the Implementation of Prim’s Minimum spanning tree algorithm.
#include<stdio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
{
printf("\nEnter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
visited[1]=1;
printf("\n");
while(ne < n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j]< min)
{
if(visited[i]!=0)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
if(visited[u]==0 || visited[v]==0)
{
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
}
cost[a][b]=cost[b][a]=999;
}
}
}
}
printf("\n Minimun cost=%d\n\n",mincost);
}
Set B
a) Write a C program for the Implementation of Kruskal’s Minimum spanning tree algorithm
//Kruskal's algorithm
#include<stdio.h>
#include<stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
{
printf("\n\tImplementation of Kruskal's algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
}
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
for(i=1,min=999;i<=n;i++)
{
for(j=1;j <= n;j++)
{
if(cost[i][j] < min)
{
min=cost[i][j];
a=u=i;
b=v=j;
}
}
}
u=find(u);
v=find(v);
if(uni(u,v))
{
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
}
cost[a][b]=cost[b][a]=999;
}
printf("\n\tMinimum cost = %d\n",mincost);
}
int find(int i)
{
while(parent[i])
i=parent[i];
return i;
}
int uni(int i,int j)
{
if(i!=j)
{
parent[j]=i;
return 1;
}
return 0;
}
Set B
a) Write a C program for the implementation of Dijkstra’s shortest path algorithm for finding shortest path from a given source vertex using adjacency cost matrix.
#include<stdio.h>
#include<conio.h>
#define INFINITY 9999
#define MAX 10
void dijikstra(int G[MAX][MAX], int n, int startnode);
void main(){
int G[MAX][MAX], i, j, n, u;
clrscr();
printf("\nEnter the no. of vertices:: ");
scanf("%d", &n);
printf("\nEnter the adjacency matrix::\n");
for(i=0;i < n;i++)
for(j=0;j < n;j++)
scanf("%d", &G[i][j]);
printf("\nEnter the starting node:: ");
scanf("%d", &u);
dijikstra(G,n,u);
getch();
}
void dijikstra(int G[MAX][MAX], int n, int startnode)
{
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i,j;
for(i=0;i < n;i++)
for(j=0;j < n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i< n;i++)
{
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=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];
pred[i]=nextnode;
}
count++;
}
for(i=0;i < n;i++)
if(i!=startnode)
{
printf("\nDistance of %d = %d", i, distance[i]);
printf("\nPath = %d", i);
j=i;
do
{
j=pred[j];
printf(" <-%d", j);
}
while(j!=startnode);
}
}
b)Write a C program for the implementation of Floyd Warshall’s algorithm for finding all pairs
shortest path using adjacency cost matrix.
#include<stdio.h>
int i, j, k,n,dist[10][10];
void floydWarshell ()
{
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
int main()
{
int i,j;
printf("enter no of vertices :");
scanf("%d",&n);
printf("\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
printf("dist[%d][%d]:",i,j);
scanf("%d",&dist[i][j]);
}
floydWarshell();
printf (" \n\n shortest distances between every pair of vertices \n");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
printf ("%d\t", dist[i][j]);
printf("\n");
}
return 0;
}
No comments:
Post a Comment