7.1.2 Breadth first search (BFS) | COMP.CS.300 Tietorakenteet ja algoritmit 1 / Data Structures and Algorithms 1

You cannot submit this assignment

You need to sign in and enrol to submit exercises.

Breadth first search (BFS)

* Question 1 2 points

Suppose a BFS algorithm starts from node \(s\). Suppose \(x\) is some other node and a path from \(s\) to \(x\) exists. Why does the BFS algorithm assign different colors to \(x\)?

To indicate the number of adjacent nodes to \(x\).

To monitor whether the path from \(s\) to \(x\) has been discovered and whether \(x\) has been completely processed.

To ensure that when BFS is finished no two adjacent nodes have the same color.

To ensure that in the queue used by BFS, no two nodes have the same color.

* Question 2 2 points

Suppose a directed graph has 4 nodes \(s\), \(a\), \(b\) and \(c\). Suppose in addition the graph has all possible edges except 2: the edge from \(s\) to \(a\) and the edge from \(a\) to \(b\). What are the distances from \(s\) to each of the other nodes?

from \(s\) to \(a\) 2, from \(s\) to \(b\) 2, from \(s\) to \(c\) 1

from \(s\) to \(a\) 1, from \(s\) to \(b\) 2, from \(s\) to \(c\) 1

from \(s\) to \(a\) 2, from \(s\) to \(b\) 1, from \(s\) to \(c\) 2

from \(s\) to \(a\) 2, from \(s\) to \(b\) 1, from \(s\) to \(c\) 1

Earned points

0 / 4

Exercise info

Assignment category: _theory
Your submissions: 0 / 3
Deadline: Sunday, 24 November 2024, 23:59
Total number of submitters: 40