[go: up one dir, main page]
Scribd
Upload
4 views9 pages

Ds Exp 9

The document contains three C programs that demonstrate graph representation and traversal techniques. Program 9A initializes an adjacency matrix and adds edges, printing the matrix representation of the graph. Program 9B implements a breadth-first search (BFS) on a graph using an adjacency matrix, while Program 9C performs a depth-first search (DFS) based on user input for the adjacency matrix.

Uploaded by

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

Ds Exp 9

The document contains three C programs that demonstrate graph representation and traversal techniques. Program 9A initializes an adjacency matrix and adds edges, printing the matrix representation of the graph. Program 9B implements a breadth-first search (BFS) on a graph using an adjacency matrix, while Program 9C performs a depth-first search (DFS) based on user input for the adjacency matrix.

Uploaded by

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

PROGRAM: 9A

#include<stdio.h>
#define V 5
void init(int arr[][V])
{
int i,j;
for(i = 0; i < V; i++)
for(j = 0; j < V; j++)
arr[i][j] = 0;
}
void addEdge(int arr[][V],int src, int dest)
{
arr[src][dest] = 1;
}
void printAdjMatrix(int arr[][V])
{
int i, j;
for(i = 0; i < V; i++)
{
for(j = 0; j < V; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int adjMatrix[V][V];
init(adjMatrix);
addEdge(adjMatrix,0,1);
addEdge(adjMatrix,0,2);
addEdge(adjMatrix,0,3);
addEdge(adjMatrix,1,3);
addEdge(adjMatrix,1,4);
addEdge(adjMatrix,2,3);
addEdge(adjMatrix,3,4);
printAdjMatrix(adjMatrix);
return 0;
}
OUTPUT:
01110
00011
00010
00001
00000
PROGRAM:9B
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
struct Vertex
{
char label;
bool visited;
};
int queue[MAX];
int rear = -1;
int front = 0;
int queueItemCount = 0;
struct Vertex* lstVertices[MAX];
int adjMatrix[MAX][MAX];
int vertexCount = 0;
void insert(int data)
{
queue[++rear] = data;
queueItemCount++;
}
int removeData()
{
queueItemCount--;
return queue[front++];
}
bool isQueueEmpty()
{
return queueItemCount == 0;
}
void addVertex(char label)
{
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}
void addEdge(int start,int end)
{
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
void displayVertex(int vertexIndex)
{
printf("%c ",lstVertices[vertexIndex]->label);
}
int getAdjUnvisitedVertex(int vertexIndex)
{
int i;
for(i = 0; i<vertexCount; i++)
{
if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false)
return i;
}
return -1;
}
void breadthFirstSearch()
{
int i;
lstVertices[0]->visited = true;
displayVertex(0);
insert(0);
int unvisitedVertex;
while(!isQueueEmpty())
{
int tempVertex = removeData();
while((unvisitedVertex = getAdjUnvisitedVertex(tempVertex)) != -1)
{
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
insert(unvisitedVertex);
}
}
for(i = 0;i<vertexCount;i++)
{
lstVertices[i]->visited = false;
}
}
int main()
{
int i, j;
for(i = 0; i<MAX; i++)
{
for(j = 0; j<MAX; j++)
adjMatrix[i][j] = 0;
}
addVertex('S');
addVertex('A');
addVertex('B');
addVertex('C');
addVertex('D');
addEdge(0, 1);
addEdge(0, 2);
addEdge(0, 3);
addEdge(1, 4);
addEdge(2, 4);
addEdge(3, 4);
printf("\nBreadth First Search: ");
breadthFirstSearch();
return 0;
}
OUTPUT:
Breadth First Search: S A B C D
PROGRAM:9C
#include<stdio.h>
void DFS(int);
int G[10][10],visited[10],n;
void main()
{
int i,j;
printf("Enter number of vertices:");
scanf("%d",&n);
printf("\nEnter adjecency matrix of the graph:");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);
for(i=0;i<n;i++)
visited[i]=0;
DFS(0);
}
void DFS(int i)
{
int j;
printf("\n%d",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}
OUTPUT:
Enter number of vertices:8
Enter adjecency matrix of the graph:0 1 1 1 1 0 0 0
10000100
10000100
10000010
10000010
01100001
00011001
00000110

0
1
5
2
7
6
3
4

You might also like