Open App

Class 8 Exam > Class 8 Notes > Depth First Traversal for a Graph

Depth First Traversal for a Graph - Class 8 PDF Download

Depth First Search or DFS for a Graph

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles (a node may be visited twice). To avoid processing a node more than once, use a boolean visited array.
Example:
Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Output: DFS from vertex 1 : 1 2 0 3
Explanation:
DFS Diagram:

Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Output: DFS from vertex 2 : 2 0 1 3
Explanation:
DFS Diagram:

Approach:

Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path.

Algorithm:

Create a recursive function that takes the index of the node and a visited array.

Mark the current node as visited and print the node.
Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.

Implementation:

Below are implementations of simple Depth First Traversal. The C++ implementation uses an adjacency list representation of graphs. STL’s list container is used to store lists of adjacent nodes.

C++

// C++ program to print DFS traversal from
// a given vertex in a given graph
#include <bits/stdc++.h>
using namespace std;

// Graph class represents a directed graph
// using adjacency list representation
class Graph {
public:
map<int, bool> visited;
map<int, list<int> > adj;

// function to add an edge to graph
void addEdge(int v, int w);

// DFS traversal of the vertices
// reachable from v
void DFS(int v);
};

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

void Graph::DFS(int v)
{
// Mark the current node as visited and
// print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices adjacent
// to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFS(*i);
}

// Driver code
int main()
{
// Create a graph given in the above diagram
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

cout << "Following is Depth First Traversal"
" (starting from vertex 2) \n";
g.DFS(2);

return 0;
}

// improved by Vishnudev C

Java

// Java program to print DFS
// mtraversal from a given
// graph
import java.io.*;
import java.util.*;

// This class represents a
// directed graph using adjacency
// list representation
class Graph {
private int V; // No. of vertices

// Array of lists for
// Adjacency List Representation
private LinkedList<Integer> adj[];

// Constructor
@SuppressWarnings("unchecked") Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}

// Function to add an edge into the graph
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v's list.
}

// A function used by DFS
void DFSUtil(int v, boolean visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v + " ");

// Recur for all the vertices adjacent to this
// vertex
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}

// The function to do DFS traversal.
// It uses recursive
// DFSUtil()
void DFS(int v)
{
// Mark all the vertices as
// not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];

// Call the recursive helper
// function to print DFS
// traversal
DFSUtil(v, visited);
}

// Driver Code
public static void main(String args[])
{
Graph g = new Graph(4);

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

System.out.println(
"Following is Depth First Traversal "
+ "(starting from vertex 2)");

g.DFS(2);
}
}
// This code is contributed by Aakash Hasija

Python3

# Python3 program to print DFS traversal
# from a given graph
from collections import defaultdict

# This class represents a directed graph using
# adjacency list representation

class Graph:

# Constructor
def __init__(self):

# default dictionary to store graph
self.graph = defaultdict(list)

# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)

# A function used by DFS
def DFSUtil(self, v, visited):

# Mark the current node as visited
# and print it
visited.add(v)
print(v, end=' ')

# Recur for all the vertices
# adjacent to this vertex
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)

# The function to do DFS traversal. It uses
# recursive DFSUtil()
def DFS(self, v):

# Create a set to store visited vertices
visited = set()

# Call the recursive helper function
# to print DFS traversal
self.DFSUtil(v, visited)

# Driver code

# Create a graph given
# in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)

print("Following is DFS from (starting from vertex 2)")
g.DFS(2)

# This code is contributed by Neelam Yadav

C#

// C# program to print DFS traversal
// from a given graph
using System;
using System.Collections.Generic;

// This class represents a directed graph
// using adjacency list representation
class Graph {
private int V; // No. of vertices

// Array of lists for
// Adjacency List Representation
private List<int>[] adj;

// Constructor
Graph(int v)
{
V = v;
adj = new List<int>[ v ];
for (int i = 0; i < v; ++i)
adj[i] = new List<int>();
}

// Function to Add an edge into the graph
void AddEdge(int v, int w)
{
adj[v].Add(w); // Add w to v's list.
}

// A function used by DFS
void DFSUtil(int v, bool[] visited)
{
// Mark the current node as visited
// and print it
visited[v] = true;
Console.Write(v + " ");

// Recur for all the vertices
// adjacent to this vertex
List<int> vList = adj[v];
foreach(var n in vList)
{
if (!visited[n])
DFSUtil(n, visited);
}
}

// The function to do DFS traversal.
// It uses recursive DFSUtil()
void DFS(int v)
{
// Mark all the vertices as not visited
// (set as false by default in c#)
bool[] visited = new bool[V];

// Call the recursive helper function
// to print DFS traversal
DFSUtil(v, visited);
}

// Driver Code
public static void Main(String[] args)
{
Graph g = new Graph(4);

g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 2);
g.AddEdge(2, 0);
g.AddEdge(2, 3);
g.AddEdge(3, 3);

Console.WriteLine(
"Following is Depth First Traversal "
+ "(starting from vertex 2)");

g.DFS(2);
Console.ReadKey();
}
}

// This code is contributed by techno2mahi

Javascript

<script>

// Javascript program to print DFS
// traversal from a given
// graph

// This class represents a
// directed graph using adjacency
// list representation
class Graph
{

// Constructor
constructor(v)
{
this.V = v;
this.adj = new Array(v);
for(let i = 0; i < v; i++)
this.adj[i] = [];
}

// Function to add an edge into the graph
addEdge(v, w)
{

// Add w to v's list.
this.adj[v].push(w);
}

// A function used by DFS
DFSUtil(v, visited)
{

// Mark the current node as visited and print it
visited[v] = true;
document.write(v + " ");

// Recur for all the vertices adjacent to this
// vertex
for(let i of this.adj[v].values())
{
let n = i
if (!visited[n])
this.DFSUtil(n, visited);
}
}

// The function to do DFS traversal.
// It uses recursive
// DFSUtil()
DFS(v)
{

// Mark all the vertices as
// not visited(set as
// false by default in java)
let visited = new Array(this.V);
for(let i = 0; i < this.V; i++)
visited[i] = false;

// Call the recursive helper
// function to print DFS
// traversal
this.DFSUtil(v, visited);
}
}

// Driver Code
g = new Graph(4);

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

document.write("Following is Depth First Traversal " +
"(starting from vertex 2)<br>");

g.DFS(2);

// This code is contributed by avanitrachhadiya2155

</script>

Output:

Following is Depth First Traversal (starting from vertex 2) 2 0 1 3

Complexity Analysis:

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity: O(V), since an extra visited array of size V is required.

Handling A Disconnected Graph:

Solution:
This will happen by handling a corner case.
The above code traverses only the vertices reachable from a given source vertex. All the vertices may not be reachable from a given vertex, as in a Disconnected graph. To do a complete DFS traversal of such graphs, run DFS from all unvisited nodes after a DFS.
The recursive function remains the same.
Algorithm:
(i) Create a recursive function that takes the index of the node and a visited array.
(ii) Mark the current node as visited and print the node.
(iii) Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.
(iv) Run a loop from 0 to the number of vertices and check if the node is unvisited in the previous DFS, call the recursive function with the current node.

Implementation:

C++

// C++ program to print DFS
// traversal for a given given
// graph
#include <bits/stdc++.h>
using namespace std;

class Graph {

// A function used by DFS
void DFSUtil(int v);

public:
map<int, bool> visited;
map<int, list<int> > adj;
// function to add an edge to graph
void addEdge(int v, int w);

// prints DFS traversal of the complete graph
void DFS();
};

void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}

void Graph::DFSUtil(int v)
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices adjacent to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i);
}

// The function to do DFS traversal. It uses recursive
// DFSUtil()
void Graph::DFS()
{
// Call the recursive helper function to print DFS
// traversal starting from all vertices one by one
for (auto i : adj)
if (visited[i.first] == false)
DFSUtil(i.first);
}

// Driver Code
int main()
{
// Create a graph given in the above diagram
Graph g;
g.addEdge(0, 1);
g.addEdge(0, 9);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(9, 3);

cout << "Following is Depth First Traversal \n";
g.DFS();

return 0;
}
// improved by Vishnudev C

Java

// Java program to print DFS
// traversal from a given given
// graph
import java.io.*;
import java.util.*;

// This class represents a
// directed graph using adjacency
// list representation
class Graph {
private int V; // No. of vertices

// Array of lists for
// Adjacency List Representation
private LinkedList<Integer> adj[];

// Constructor
@SuppressWarnings("unchecked") Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}

// Function to add an edge into the graph
void addEdge(int v, int w)
{
adj[v].add(w); // Add w to v's list.
}

// A function used by DFS
void DFSUtil(int v, boolean visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
System.out.print(v + " ");

// Recur for all the vertices adjacent to this
// vertex
Iterator<Integer> i = adj[v].listIterator();
while (i.hasNext()) {
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}

// The function to do DFS traversal. It uses recursive
// DFSUtil()
void DFS()
{
// Mark all the vertices as not visited(set as
// false by default in java)
boolean visited[] = new boolean[V];

// Call the recursive helper function to print DFS
// traversal starting from all vertices one by one
for (int i = 0; i < V; ++i)
if (visited[i] == false)
DFSUtil(i, visited);
}

// Driver Code
public static void main(String args[])
{
Graph g = new Graph(4);

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

System.out.println(
"Following is Depth First Traversal");

g.DFS();
}
}
// This code is contributed by Aakash Hasija

Python3

'''Python program to print DFS traversal for complete graph'''
from collections import defaultdict

# this class represents a directed graph using adjacency list representation

class Graph:
# Constructor
def __init__(self):
# default dictionary to store graph
self.graph = defaultdict(list)

# Function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
# A function used by DFS

def DFSUtil(self, v, visited):
# Mark the current node as visited and print it
visited.add(v)
print(v,end=" ")

# recur for all the vertices adjacent to this vertex
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFSUtil(neighbour, visited)
# The function to do DFS traversal. It uses recursive DFSUtil

def DFS(self):
# create a set to store all visited vertices
visited = set()
# call the recursive helper function to print DFS traversal starting from all
# vertices one by one
for vertex in self.graph:
if vertex not in visited:
self.DFSUtil(vertex, visited)
# Driver code
# create a graph given in the above diagram

print("Following is Depth First Traversal \n")
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
g.DFS()

# Improved by Dheeraj Kumar

C#

// C# program to print DFS
// traversal from a given given
// graph
using System;
using System.Collections.Generic;

// This class represents a
// directed graph using adjacency
// list representation
public class Graph {
private int V; // No. of vertices

// Array of lists for
// Adjacency List Representation
private List<int>[] adj;

// Constructor
Graph(int v)
{
V = v;
adj = new List<int>[ v ];
for (int i = 0; i < v; ++i)
adj[i] = new List<int>();
}

// Function to add an edge into the graph
void addEdge(int v, int w)
{
adj[v].Add(w); // Add w to v's list.
}

// A function used by DFS
void DFSUtil(int v, bool[] visited)
{
// Mark the current
// node as visited and print it
visited[v] = true;
Console.Write(v + " ");

// Recur for all the
// vertices adjacent to this
// vertex
foreach(int i in adj[v])
{
int n = i;
if (!visited[n])
DFSUtil(n, visited);
}
}

// The function to do
// DFS traversal. It uses recursive
// DFSUtil()
void DFS()
{
// Mark all the vertices as not visited(set as
// false by default in java)
bool[] visited = new bool[V];

// Call the recursive helper
// function to print DFS
// traversal starting from
// all vertices one by one
for (int i = 0; i < V; ++i)
if (visited[i] == false)
DFSUtil(i, visited);
}

// Driver code
public static void Main(String[] args)
{
Graph g = new Graph(4);

g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);

Console.WriteLine(
"Following is Depth First Traversal");

g.DFS();
}
}

// This code is contributed by PrinciRaj1992

Javascript

<script>
// JavaScript program to print DFS
// traversal from a given given
// graph

// This class represents a
// directed graph using adjacency
// list representation
class Graph
{

// Constructor
constructor(v) {
this.V = v;
this.adj = new Array(v).fill([]);
}

// Function to Add an edge into the graph
AddEdge(v, w) {
this.adj[v].push(w); // Add w to v's list.
}

// A function used by DFS
DFSUtil(v, visited)
{

// Mark the current
// node as visited and print it
visited[v] = true;
document.write(v + " ");

// Recur for all the
// vertices adjacent to this
// vertex
for (const n of this.adj[v]) {
if (!visited[n]) this.DFSUtil(n, visited);
}
}

// The function to do
// DFS traversal. It uses recursive
// DFSUtil()
DFS()
{

// Mark all the vertices as not visited(set as
var visited = new Array(this.V).fill(false);

// Call the recursive helper
// function to print DFS
// traversal starting from
// all vertices one by one
for (var i = 0; i < this.V; ++i)
if (visited[i] == false) this.DFSUtil(i, visited);
}
}

// Driver Code
var g = new Graph(4);

g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 2);
g.AddEdge(2, 0);
g.AddEdge(2, 3);
g.AddEdge(3, 3);

document.write("Following is Depth First Traversal<br>");

g.DFS();

// This code is contributed by rdtank.
</script>

Output:

Following is Depth First Traversal 0 1 2 3 9

Complexity Analysis:

Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity: O(V), since an extra visited array of size V is required.

The document Depth First Traversal for a Graph - Class 8 is a part of Class 8 category.

All you need of Class 8 at this link: Class 8

Top Courses for Class 8

View all

Related Exams

Class 8

About this Document

Oct 28, 2024 Last updated

Document Description: Depth First Traversal for a Graph for Class 8 2024 is part of Class 8 preparation. The notes and questions for Depth First Traversal for a Graph have been prepared according to the Class 8 exam syllabus. Information about Depth First Traversal for a Graph covers topics like Depth First Search or DFS for a Graph, Implementation:  and Depth First Traversal for a Graph Example, for Class 8 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Depth First Traversal for a Graph.

Introduction of Depth First Traversal for a Graph in English is available as part of our Class 8 preparation & Depth First Traversal for a Graph in Hindi for Class 8 courses. Download more important topics, notes, lectures and mock test series for Class 8 Exam by signing up for free. Class 8: Depth First Traversal for a Graph - Class 8

Description

Full syllabus notes, lecture & questions for Depth First Traversal for a Graph - Class 8 - Class 8 | Plus excerises question with solution to help you revise complete syllabus | Best notes, free PDF download

Information about Depth First Traversal for a Graph

In this doc you can find the meaning of Depth First Traversal for a Graph defined & explained in the simplest way possible. Besides explaining types of Depth First Traversal for a Graph theory, EduRev gives you an ample number of questions to practice Depth First Traversal for a Graph tests, examples and also practice Class 8 tests.

Download as PDF

Explore Courses for Class 8 exam

Top Courses for Class 8

Explore Courses

Signup for Free!

Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.

Start learning for Free

10M+ students study on EduRev

Extra Questions

Summary

Depth First Traversal for a Graph - Class 8

mock tests for examination

Viva Questions

ppt

Objective type Questions

MCQs

video lectures

shortcuts and tricks

Sample Paper

Depth First Traversal for a Graph - Class 8

Important questions

past year papers

Exam

Previous Year Questions with Solutions

Depth First Traversal for a Graph - Class 8

practice quizzes

Free

pdf

Semester Notes

study material

;

Additional Information about Depth First Traversal for a Graph for Class 8 Preparation

Depth First Traversal for a Graph Free PDF Download

The Depth First Traversal for a Graph is an invaluable resource that delves deep into the core of the Class 8 exam. These study notes are curated by experts and cover all the essential topics and concepts, making your preparation more efficient and effective. With the help of these notes, you can grasp complex subjects quickly, revise important points easily, and reinforce your understanding of key concepts. The study notes are presented in a concise and easy-to-understand manner, allowing you to optimize your learning process. Whether you're looking for best-recommended books, sample papers, study material, or toppers' notes, this PDF has got you covered. Download the Depth First Traversal for a Graph now and kickstart your journey towards success in the Class 8 exam.

Importance of Depth First Traversal for a Graph

The importance of Depth First Traversal for a Graph cannot be overstated, especially for Class 8 aspirants. This document holds the key to success in the Class 8 exam. It offers a detailed understanding of the concept, providing invaluable insights into the topic. By knowing the concepts well in advance, students can plan their preparation effectively. Utilize this indispensable guide for a well-rounded preparation and achieve your desired results.

Depth First Traversal for a Graph Notes

Depth First Traversal for a Graph Notes offer in-depth insights into the specific topic to help you master it with ease. This comprehensive document covers all aspects related to Depth First Traversal for a Graph. It includes detailed information about the exam syllabus, recommended books, and study materials for a well-rounded preparation. Practice papers and question papers enable you to assess your progress effectively. Additionally, the paper analysis provides valuable tips for tackling the exam strategically. Access to Toppers' notes gives you an edge in understanding complex concepts. Whether you're a beginner or aiming for advanced proficiency, Depth First Traversal for a Graph Notes on EduRev are your ultimate resource for success.

Depth First Traversal for a Graph Class 8 Questions

The "Depth First Traversal for a Graph Class 8 Questions" guide is a valuable resource for all aspiring students preparing for the Class 8 exam. It focuses on providing a wide range of practice questions to help students gauge their understanding of the exam topics. These questions cover the entire syllabus, ensuring comprehensive preparation. The guide includes previous years' question papers for students to familiarize themselves with the exam's format and difficulty level. Additionally, it offers subject-specific question banks, allowing students to focus on weak areas and improve their performance.

Study Depth First Traversal for a Graph on the App

Students of Class 8 can study Depth First Traversal for a Graph alongwith tests & analysis from the EduRev app, which will help them while preparing for their exam. Apart from the Depth First Traversal for a Graph, students can also utilize the EduRev App for other study materials such as previous year question papers, syllabus, important questions, etc. The EduRev App will make your learning easier as you can access it from anywhere you want. The content of Depth First Traversal for a Graph is prepared as per the latest Class 8 syllabus.

Education Revolution

Signup to see your scores go up within 7 days!

Access 1000+ FREE Docs, Videos and Tests

Continue with Google

Takes less than 10 seconds to signup