Assignment 4: Graph as Adjacency List
Set A
a) Write a C program that accepts the vertices and edges of a graph. Create adjacency list and display the adjacency list.
//read graph as adjacency list and print it.
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int vertex;
struct node *next;
}node;
//heads of linked list
node *ll[20];
int n;
//create adjacency list
void read_graph();
//insert an edge (vi,vj) in te adjacency list
void insert(int,int);
//print adjacency list
void printlist();
void main()
{
read_graph();
printf("\nAdjacency List is:\n");
printlist();
printf("\n");
}
void read_graph()
{
int i,vi,vj,no_of_edges;
printf("\nEnter number of vertices:");
scanf("%d",&n);//n=6
//initialise ll[] with a null
ll[0]=NULL;
//read edges and insert them in G[]
printf("\nEnter number of edges:");
scanf("%d",&no_of_edges);
for(i=0;i<no_of_edges;i++)
{
printf("Enter an edge(initial_vertex end_vertex):");
scanf("%d%d",&vi,&vj);
insert(vi,vj);
}
}
void insert(int vi,int vj)
{
node *p,*q;
q=(node*)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;
//insert the node in the linked list number vi
if(ll[vi]==NULL)
ll[vi]=q;
else
{
//go to end of the linked list
p=ll[vi];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}//insert()
void printlist()
{
struct node *p;
int i;
for (i = 0; i < n ; i++ )
{
printf("\n%d=",i);
p=ll[i];
while(p!=NULL)
{
printf("%d->",p->vertex);
p=p->next;
}
printf("NULL\n");
} // for
}
b) Write a C program that accepts the vertices and edges of a graph. Create adjacency list. Implement functions to print indegree, outdegree and total degree of all vertex of graph.
//read graph as adjacency list and find out indegree,outdegree
//and total degree of each node in graph.
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
struct node *next;
int vertex;
}node;
//heads of linked list
node *ll[20];
int n;
//create adjacency list
void read_graph();
//insert an edge (vi,vj) in the adjacency list
void insert(int,int);
void degree();
void main()
{
int i,v;
read_graph();
degree(n);
printf("\n\n");
}
void read_graph()
{
int i,vi,vj,no_of_edges;
printf("\nEnter number of vertices:");
scanf("%d",&n);
//initialise ll[] with a null
ll[0]=NULL;
//read edges and insert them in G[]
printf("\nEnter number of edges:");
scanf("%d",&no_of_edges);
for(i=0;i<no_of_edges;i++)
{
printf("Enter an edge(u v):");
scanf("%d%d",&vi,&vj);
insert(vi,vj);
}
}
void insert(int vi,int vj)
{
node *p,*q;
//acquire memory for the new node
q=(node*)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;
//insert the node in the linked list number vi
if(ll[vi]==NULL)
ll[vi]=q;
else
{
//go to end of the linked list
p=ll[vi];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}
void degree(int n)
{
int i,indegree[10],outdegree[10];
struct node *p;
for(i=0;i<10;i++)indegree[i]=0;
for(i=0;i<10;i++)outdegree[i]=0;
for (i = 0; i < n ; i++ )
{
p=ll[i];
while(p!=NULL)
{
indegree[p->vertex]+=1;
outdegree[i]+=1;
p=p->next;
}
} // for
for(i=0;i<n;i++)
printf("\nIndegree, Outdegree and Total Degree of vertex %d is %d, %d, %d",i,indegree[i],outdegree[i],indegree[i]+outdegree[i]);
}
Set B
a) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency list. Implement function to traverse the graph using Breadth First Search (BFS) traversal.
// Adjacency list BFS
#include <stdio.h>
#include <stdlib.h>
#define SIZE 40
struct queue {
int items[SIZE];
int front;
int rear;
};
struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);
struct node {
int vertex;
struct node* next;
};
struct node* createNode(int);
struct Graph {
int numVertices;
struct node** adjLists;
int* visited;
};
// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();
graph->visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
struct node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
enqueue(q, adjVertex);
}
temp = temp->next;
}
}
}
// Creating a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Creating a graph
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));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// Create a queue
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}
// Check if the queue is empty
int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}
// Adding elements into queue
void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}
// Removing elements from queue
int dequeue(struct queue* q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
printf("Resetting queue ");
q->front = q->rear = -1;
}
}
return item;
}
// Print the queue
void printQueue(struct queue* q) {
int i = q->front;
if (isEmpty(q)) {
printf("Queue is empty");
} else {
printf("\nQueue contains \n");
for (i = q->front; i < q->rear + 1; i++) {
printf("%d ", q->items[i]);
}
}
}
int main() {
struct Graph* graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 0);
addEdge(graph, 2, 3);
addEdge(graph, 3, 3);
//addEdge(graph, 3, 4);
bfs(graph, 2);
return 0;
}
b) Write a C program that accepts the vertices and edges of a graph and store it as an adjacency list. Implement function to traverse the graph using Depth First Search (DFS) traversal.
//adjacency list DFS
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
struct node *next;
int vertex;
}node;
node *ll[20];
//heads of linked list
int visited[20];
int n;
void read_graph();
//create adjacency list
void insert(int,int);
//insert an edge (vi,vj) in te adjacency list
void DFS(int);
void main()
{
int i,v;
read_graph();
//initialised visited to 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)
{
node *p;
printf("%d ",i);
p=ll[i];
visited[i]=1;
while(p!=NULL)
{
i=p->vertex;
if(!visited[i])
DFS(i);
p=p->next;
}
}
void read_graph()
{
int i,vi,vj,no_of_edges;
printf("\nEnter number of vertices:");
scanf("%d",&n);
//initialise G[] with a null
ll[0]=NULL;
//read edges and insert them in G[]
printf("\nEnter number of edges:");
scanf("%d",&no_of_edges);
for(i=0;i<no_of_edges;i++)
{
printf("Enter an edge(u,v):");
scanf("%d%d",&vi,&vj);
insert(vi,vj);
}
}
void insert(int vi,int vj)
{
node *p,*q;
//acquire memory for the new node
q=(node*)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;
//insert the node in the linked list number vi
if(ll[vi]==NULL)
ll[vi]=q;
else
{
//go to end of the linked list
p=ll[vi];
while(p->next!=NULL)
p=p->next;
p->next=q;
}
}
No comments:
Post a Comment