Assignment 3: Graph as Adjacency Matrix
Set A
a) Write a C program that accepts the vertices and edges of a graph and stores it as an adjacency matrix. Display the adjacency matrix.
//Read a graph as adjacency matrix and and print it
#include<stdio.h>
int mat[10][10];
void display();
int main()
{
int i, j,n;
char reply;
printf("How many vertices:");
scanf("%d",&n);
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0 ; j < n ; j++ )
{
printf("\n Is there edge between %d & %d ? (Y/N) :",i+1,j+1);
scanf(" %c", &reply);
if ( reply == 'y' || reply == 'Y' )
mat[i][j] = 1;
else
mat[i][j] = 0;
}
}
display(n);
return 0;
}
void display(int size)
{
int i,j;
printf("\n--------------------------------------------------------------------\n");
printf("\nAdjecency Matrix is:\n\n");
for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
printf("%d\t",mat[i][j]);
}
printf("\n");
}
}
b) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency matrix. Implement functions to print indegree, outdegree and total degree of all vertices of graph.
//Read a graph as adjacency matrix and and print it and find
//out indegree,outdegree and total degree of each node
#include<stdio.h>
int mat[10][10];
void display(int);
void degree(int);
int main()
{
int i, j,n;
char reply;
printf("How many vertices:");
scanf("%d",&n);
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0 ; j < n ; j++ )
{
printf("\n Is there edge between %d & %d ? (Y/N) :",i+1,j+1);
scanf(" %c", &reply);
if ( reply == 'y' || reply == 'Y' )
mat[i][j] = 1;
else
mat[i][j] = 0;
}
}
display(n);
degree(n);
return 0;
}
void display(int size)
{
int i,j;
printf("\n--------------------------------------------------------------------\n");
printf("\nAdjecency Matrix is:\n\n");
for(i=0;i<size;i++)
{
for(j=0;j<size;j++)
{
printf("%d\t",mat[i][j]);
}
printf("\n");
}
}
void degree(int n)
{
int i,j,indegree=0,outdegree=0;
for (i = 0; i < n ; i++ )
{
for(j=0;j<n;j++)
{
if (mat[i][j]==1)
outdegree++;
if (mat[j][i]==1)
indegree++;
}
printf("\nIndegree, Outdegree and Total Degree of vertex %d is %d, %d, %d",i+1,indegree,outdegree,indegree+outdegree);
indegree=0;
outdegree=0;
} // for
printf("\n\n");
}
Set B
a) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency matrix. Implement function to traverse the graph using Breadth First Search (BFS) traversal.
//adjacency matrix BFS
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
#define initial 1
#define waiting 2
#define visited 3
int n;
int mat[MAX][MAX];
int state[MAX];
void accept();
void BF_Traversal();
void BFS(int v);
int queue[MAX], front = -1,rear = -1;
void insert_queue(int vertex);
int delete_queue();
int isEmpty_queue();
int main()
{
accept();
BF_Traversal();
return 0;
}
void accept()
{
int i, j;
char reply;
printf("How many vertices:");
scanf("%d",&n);
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0 ; j < n ; j++ )
{
printf("\n Is there edge between %d & %d ? (Y/N/y/n) :",i,j);
scanf(" %c", &reply);
if ( reply == 'y' || reply == 'Y' )
mat[i][j] = 1;
else
mat[i][j] = 0;
}
}
}
void BF_Traversal()
{
int v;
for(v=0; v<n; v++)
state[v] = initial;
printf("\nEnter Start Vertex for BFS: ");
scanf("%d", &v);
printf("\nBFS Traversal is: ");
BFS(v);
printf("\n\n");
}
void BFS(int v)
{
int i;
insert_queue(v);
state[v] = waiting;
while(!isEmpty_queue())
{
v = delete_queue( );
printf("%d ",v);
state[v] = visited;
for(i=0; i<n; i++)
{
if(mat[v][i] == 1 && state[i] == initial)
{
insert_queue(i);
state[i] = waiting;
}
}
}
printf("\n");
}
void insert_queue(int vertex)
{
if(front == -1)
front = 0;
rear = rear+1;
queue[rear] = vertex ;
}
int isEmpty_queue()
{
if(front == -1 || front > rear)
return 1;
else
return 0;
}
int delete_queue()
{
int delete_item;
delete_item = queue[front];
front = front+1;
return delete_item;
}
b) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency matrix. Implement function to traverse the graph using Depth First Search (DFS) traversal.
//adjacency matrix DFS
#include<stdio.h>
void DFS(int);
int mat[10][10],visited[10],n;
void main()
{
int i,j,v;
char reply;
printf("How many vertices:");
scanf("%d",&n);
for ( i = 0 ; i < n ; i++ )
{
for ( j = 0 ; j < n ; j++ )
{
printf("\nIs there edge between %d & %d ? (Y/N/y/n) :",i,j);
scanf(" %c", &reply);
if ( reply == 'y' || reply == 'Y' )
mat[i][j] = 1;
else
mat[i][j] = 0;
}
}
for(i=0;i<n;i++)
visited[i]=0;
printf("\nEnter the start vertex: ");
scanf("%d",&v);
printf("\nDFS Traversal is:");
DFS(v);
printf("\n\n");
}
void DFS(int i)
{
int j;
printf("%d ",i);
visited[i]=1;
for(j=0;j<n;j++)
if(!visited[j] && mat[i][j]==1)
DFS(j);
}
No comments:
Post a Comment