Scribd
Upload
45 views2 pages

DFS Program

The document contains a C program that implements Depth-First Search (DFS) for both a graph and a binary tree. It uses an adjacency matrix to represent the graph and includes functions for traversing the graph and tree in a pre-order manner. The main function demonstrates the DFS traversal for both structures and prints the results.

Uploaded by

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

DFS Program

The document contains a C program that implements Depth-First Search (DFS) for both a graph and a binary tree. It uses an adjacency matrix to represent the graph and includes functions for traversing the graph and tree in a pre-order manner. The main function demonstrates the DFS traversal for both structures and prints the results.

Uploaded by

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

#include <stdio.

h>
#include <stdbool.h>
#include <stdlib.h> // Added this line for malloc
// Graph DFS Implementation
#define MAX_VERTICES 8
// Adjacency Matrix Representation
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 1, 1, 0, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 0, 1, 0, 0},
{0, 1, 0, 0, 0, 0, 1, 0},
{0, 1, 0, 0, 0, 0, 1, 0},
{0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 0, 0, 1, 0}
};
bool visited[MAX_VERTICES] = {false};
// Graph DFS Function
void graphDFS(int vertex) {
// Mark current vertex as visited
visited[vertex] = true;
printf("%d ", vertex);

// Explore all adjacent vertices


for (int i = 0; i < MAX_VERTICES; i++) {
if (graph[vertex][i] == 1 && !visited[i]) {
graphDFS(i);
}
}
}

// Tree DFS Implementation


struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

// Create a new tree node


struct TreeNode* createNode(int data) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Tree DFS (Pre-order Traversal)


void treeDFS(struct TreeNode* root) {
if (root == NULL) return;

// Visit root
printf("%d ", root->data);

// Traverse left subtree


treeDFS(root->left);

// Traverse right subtree


treeDFS(root->right);
}

int main() {
// Graph DFS Demonstration
printf("Graph DFS Traversal: ");
graphDFS(0); // Start DFS from vertex 0
printf("\n");

// Reset visited array for multiple traversals


for (int i = 0; i < MAX_VERTICES; i++) {
visited[i] = false;
}

// Tree DFS Demonstration


// Create a sample tree
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);

printf("Tree DFS (Pre-order) Traversal: ");


treeDFS(root);
printf("\n");

return 0;
}

You might also like