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

1 hour

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

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.

10 minutes

Pretest includes questions on

- Arrays
- Lists

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.

15 minutes

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

Graphs basics video should be displayed here..!

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 video should be displayed here..!

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

There are mainly two types of graphs

1.Undirected Graph

2.Directed Graph

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

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

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

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.

25 minutes

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 video should be displayed here..!

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 video should be displayed here..!

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

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

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

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

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

DFS demo video should be displayed here..!

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.

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.

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.

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.

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.

10 minutes

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.

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.

(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.

You can explore more about DFS through following resources: