Introduction to DFS

Welcome to DFS Experiment!

Video introduction to DFS experiment should be displayed here..!

Estimated Time

1 hour

Prerequisites of the Experiment

  • Basic knowledge of
  • And above all, a curiosity to learn and explore..!

Overview of the Experiment

The experiment features a series of modules with video lectures, hands-on practice exercises and quizzes to self analyze.

Learning Objectives of the Experiment

In this experiment, you will be able to do the following:

  • Understand the basics of graphs and their representations.
  • Understand the working Depth First Traversal Algorithm for searching nodes.
  • Given a graph, understand the progression of the Depth First Traversal Algorithm and search for particular nodes.
  • Demonstrate the knowledge of time complexity of the Depth First Search Traversal algorithm.

Pre-test of the Experiment

Estimated Time

10 minutes

Introduction to Pre-test of the Experiment

Pretest includes questions on

  • Arrays
  • Lists
Read the questions below and select the correct options from the ones given. Some questions may have multiple correct answers.

Pre-test Quiz of the Experiment

Q1. Which of the following statements are correct about an array?

(A) The array int num[26]; can store 26 elements.

(B) The expression num[1] designates the very first element in the array.

(C) It is necessary to initialize the array at the time of declaration.

(D) The declaration num[SIZE] is allowed if SIZE is a macro.

Size shows the number of elements in array.

Q2. An array elements are always stored in ________ memory locations.

(A) Sequential

(B) Random

(C) Sequential and Random

(D) None of the above

Explanation of question 2 for the right answer.

Q3. What is right way to Initialize array?

(A) int num[6] = { 21, 41, 2, 15, 4, 5 };

(B) int n{} = { 21, 41, 2, 15, 4, 5 };

(C) int n{6} = { 21, 41, 2 };

(D) int n(6) = { 21, 41, 2, 15, 4, 5 };

This is the general syntax of initializing array.

Q4. Linked list is generally considered as an example of _________ type of memory allocation.

(A) Static

(B) Dynamic

(C) Compile Time

(D) None of the above

Linked List elements are stored at random places in memory.

Q5.Generally collection of Nodes is called as__

(A) Heap

(B) Stack

(C) Linked List

(D) Pointer

Linked List consists of collection of nodes.

Graph Basics

Estimated Time

15 minutes

Introduction to Graphs

Welcome to this module on graphs! Take a look at what you will go through the module.

  • What are graphs?
  • Graph as Data Structure
  • Types of Graphs
  • A quiz to check your understanding of concepts of graphs

Basics of Graphs

Graphs Basics

Graphs basics video should be displayed here..!

Definition

A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph. More formally a Graph can be defined as, A Graph consists of a finite set of vertices(or nodes) and set of Edges which connect a pair of nodes.

Graphs Example

Graphs example video should be displayed here..!

Pictorial Representation of a Simple Graph

Pictorial Representation of a Simple Graph should be displayed here..!

Types of Graphs

There are mainly two types of graphs
1.Undirected Graph
2.Directed Graph

Pictorial Representation of Undirected Graph

Pictorial Representation of a Undirected Graph should be displayed here..!

Pictorial Representation of Directed Graph

Pictorial Representation of a Directed Graph should be displayed here..!

Pictorial Representation of Graph Real World Example

Pictorial Representation of a Simple Graph should be displayed here..!

Quiz on Graphs

Q1. Which of the following is true?

(A) A graph may contain no edges and many vertices

(B) A graph may contain many edges and no vertices

(C) A graph may contain no edges and no vertices

(D) None of the mentioned

Graphs consist of many edges and vertices.

Q2. Which of the following is true about graphs?

(A) Each node can only store integers

(B) Consecutive nodes need to be stored sequentially in memory

(C) Both of the above

(D) None of the above

Consecutive nodes need not be stored sequentially in memory.

Depth First Traversal

Estimated Time

25 minutes

Introduction to Depth First Traversal

Welcome to this module on DFS..! Take a look at what you will go through in this module.

  • What is DFS and when is it used?
  • Practice DFS Algorithm
  • Interactive DFS Exercise
  • A quiz to check your understanding of DFS

Basics of DFS

Basics of DFS

Basics of DFS video should be displayed here..!

Definition

Depth-first search (DFS) 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.

DFS Example

DFS example video should be displayed here..!

Important Points about DFS

Pictorial Representation of a DFS Algorithm should be displayed here..!

Pictorial Representation of DFS Applications

Pictorial Representation of a DFS Applications should be displayed here..!

Topological Sorting - Definition

Pictorial Representation of a Topological Sorting should be displayed here..!

Topological Sorting - Real Life

Pictorial Representation of a Topological Sorting - Real Life should be displayed here..!

Pictorial Representation of Connected Components

Pictorial Representation of a Connected Components should be displayed here..!

DFS Demo Video

DFS demo video should be displayed here..!

Depth First Traversal Demo - Trees

Interactive Artefact

A random graph is shown on screen.
Student can click any node of the graph.
Once a node is clicked, the visual representation of DFS starts from that node
Student can change the graph by clicking generate graph button.
Student can click on different nodes and master the DFS algorithm.

Depth First Traversal Demo - Graphs

Interactive Artefact

A random graph is shown on screen.
Student can click any node of the graph.
Once a node is clicked, the visual representation of DFS starts from that node
Student can change the graph by clicking generate graph button.
Student can click on different nodes and master the DFS algorithm.

Practice Depth First Traversal

Interactive Artefact

Student is given a graph
Student will be given hints for steps for DFS.
Steps can be like:
1)Pick 0 as the root node.
2)Pick any of the children of the root node.
3)Repeat above process, if there's no children of node, then go to last parent and pick the child which is not visited.

Student has to perform DFS step-wise
After finishing DFS on graph, he can click generate random graph and practice again.

Check your understanding of Depth First Traversal

Interactive Module

Student is given a graph and starting node as the question.
Student needs to click the nodes of graph as they appear in DFS algorithm
Nodes follow a particular color scheme to differentiate between white,grey and black nodes.

Quiz on Depth First Traveral

Q1. Time Complexity of DFS is? (V – number of vertices, E – number of edges)

(A) O(V + E)

(B) O(V)

(C) O(E)

(D) None of the mentioned

The algorithms goes through each vertex and each edge, that's why complexity is O(V + E).

Q2. The Depth First Search traversal of a graph will result into?

(A) Linked List

(B) Tree

(C) Graph with back edges

(D) None of the mentioned

Algorithm generates a tree.

Post Test

Estimated Time

10 minutes

Introduction to Post test of the Experiment

Post test includes questions on entire experiment concepts. Read the questions given below and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Post-test Quiz of the Experiment

Q1. What can be the applications of Depth First Search?

(A) For generating topological sort of a graph

(B) For generating Strongly Connected Components of a directed graph

(C) Detecting cycles in the graph

(D) All of the mentioned

All of the above are applications of DFS.

Q2. In Depth First Search, how many times a node is visited?

(A) Once

(B) Twice

(C) Equivalent to number of indegree of the node

(D) None of the mentioned

DFS covers each node only once.

Q3. While running DFS on a directed graph, if from vertex u we visit a finished vertex v, then the edge(u,v)is a cross-edge

(A) True

(B) False

If v is neither an ancestor nor descendant of u, then edge (u, v) is a cross edge.

Q4. All Graphs have unique representation on paper.

(A) True

(B) False

A graph can have many representations on paper.

Further Readings/References

Explore Depth First Traversal