Assignment 3: Graph Implementations
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. Create and display adjacency list also print indegree, outdegree and total degree of all vertex of graph.
#include <stdio.h>
#include <stdlib.h>
// Structure for a node in the adjacency list
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// Structure for the adjacency list
struct AdjList {
struct AdjListNode* head;
};
// Create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// Function to add a directed edge from src to dest
void addEdge(struct AdjList* array, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = array[src].head;
array[src].head = newNode;
}
int main() {
int vertices, edges, src, dest;
printf("Enter the number of vertices: ");
scanf("%d", &vertices);
// Initialize adjacency list
struct AdjList* array = (struct AdjList*)malloc(vertices * sizeof(struct AdjList));
for (int i = 0; i < vertices; i++) array[i].head = NULL;
printf("Enter the number of edges: ");
scanf("%d", &edges);
for (int i = 0; i < edges; i++) {
printf("Enter edge %d (source destination): ", i + 1);
scanf("%d %d", &src, &dest);
if (src >= 0 && src < vertices && dest >= 0 && dest < vertices) {
addEdge(array, src, dest);
} else {
printf("Invalid vertices! Try again.\n");
i--;
}
}
// Display Adjacency List
printf("\n--- Adjacency List ---\n");
for (int i = 0; i < vertices; i++) {
struct AdjListNode* temp = array[i].head;
printf("Vertex %d: ", i);
while (temp) {
printf("-> %d ", temp->dest);
temp = temp->next;
}
printf("NULL\n");
}
// Calculate and print degrees
printf("\nVertex\tInDegree\tOutDegree\tTotal Degree\n");
for (int i = 0; i < vertices; i++) {
int inDeg = 0, outDeg = 0;
// Outdegree is the count of nodes in the current vertex's list
struct AdjListNode* temp = array[i].head;
while (temp) {
outDeg++;
temp = temp->next;
}
// Indegree is how many times vertex 'i' appears in ALL lists
for (int j = 0; j < vertices; j++) {
struct AdjListNode* check = array[j].head;
while (check) {
if (check->dest == i) inDeg++;
check = check->next;
}
}
printf("%d\t%d\t\t%d\t\t%d\n", i, inDeg, outDeg, inDeg + outDeg);
}
return 0;
}
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) and Depth First Search (DFS) traversal.
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
int adj[MAX][MAX];
int visited[MAX];
int n; // Number of vertices
// BFS Implementation using a Queue
void BFS(int startNode) {
int queue[MAX], front = 0, rear = 0;
int i, current;
for (i = 0; i < n; i++) visited[i] = 0; // Reset visited array
printf("BFS Traversal: ");
visited[startNode] = 1;
queue[rear++] = startNode;
while (front < rear) {
current = queue[front++];
printf("%d ", current);
for (i = 0; i < n; i++) {
if (adj[current][i] == 1 && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
printf("\n");
}
// DFS Implementation using Recursion
void DFS(int current) {
printf("%d ", current);
visited[current] = 1;
for (int i = 0; i < n; i++) {
if (adj[current][i] == 1 && !visited[i]) {
DFS(i);
}
}
}
int main() {
int edges, i, src, dest, startNode;
printf("Enter number of vertices: ");
scanf("%d", &n);
// Initialize matrix with 0
for (i = 0; i < n; i++)
for (int j = 0; j < n; j++)
adj[i][j] = 0;
printf("Enter number of edges: ");
scanf("%d", &edges);
for (i = 0; i < edges; i++) {
printf("Enter edge %d (source destination): ", i + 1);
scanf("%d %d", &src, &dest);
if (src < n && dest < n)
adj[src][dest] = 1; // For undirected graph, add adj[dest][src] = 1;
else
printf("Invalid vertex index!\n");
}
printf("\nEnter starting vertex for traversals: ");
scanf("%d", &startNode);
BFS(startNode);
// Reset visited for DFS
for (i = 0; i < n; i++) visited[i] = 0;
printf("DFS Traversal: ");
DFS(startNode);
printf("\n");
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 Breadth First Search (BFS) and Depth First Search (DFS) traversal.
#include <stdio.h>
#include <stdlib.h>
// Node structure for Adjacency List
struct Node {
int vertex;
struct Node* next;
};
// Graph structure
struct Graph {
int numVertices;
struct Node** adjLists;
int* visited;
};
// Create a new node
struct Node* createNode(int v) {
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create 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));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Add edge (Directed)
void addEdge(struct Graph* graph, int src, int dest) {
struct Node* newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
}
// DFS Traversal
void DFS(struct Graph* graph, int vertex) {
graph->visited[vertex] = 1;
printf("%d ", vertex);
struct Node* temp = graph->adjLists[vertex];
while (temp) {
int connectedVertex = temp->vertex;
if (graph->visited[connectedVertex] == 0) {
DFS(graph, connectedVertex);
}
temp = temp->next;
}
}
// BFS Traversal
void BFS(struct Graph* graph, int startNode) {
for (int i = 0; i < graph->numVertices; i++) graph->visited[i] = 0; // Reset
int queue[20], front = 0, rear = 0;
graph->visited[startNode] = 1;
queue[rear++] = startNode;
printf("\nBFS Traversal: ");
while (front < rear) {
int currentVertex = queue[front++];
printf("%d ", currentVertex);
struct Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
graph->visited[adjVertex] = 1;
queue[rear++] = adjVertex;
}
temp = temp->next;
}
}
}
int main() {
int vertices, edges, src, dest, start;
printf("Enter number of vertices: ");
scanf("%d", &vertices);
struct Graph* graph = createGraph(vertices);
printf("Enter number of edges: ");
scanf("%d", &edges);
for (int i = 0; i < edges; i++) {
printf("Enter edge (source destination): ");
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
printf("Enter starting vertex: ");
scanf("%d", &start);
printf("DFS Traversal: ");
DFS(graph, start);
BFS(graph, start);
printf("\n");
return 0;
}
No comments:
Post a Comment