Зміст курсу

Breadth First Search

1. What is BFS

How to Search Graph Class Implementation

2. Practice

Breadth First Traverse Check if is One Component Shortest Path in Graph Restoring Shortest Path Find All Connected Components Is a Tree

3. Improve Your Code

Congratulations Components Methods BFT and BFS

4. Solving the Problems using BFS

Coloring Pixels Shortest Clear Path

Is a Tree

BFS check if graph is a tree

And the last one required method is a bit simpler. Tree graph is a one-component acyclic graph, so you have to check first, if it is acyclic.

Acyclic

During BFS, you check vertices on different levels, until you find the end vertex. When traversing a tree, each time you check vertices that haven’t been visited yet. The cycle is detected when you check neighbors for the current node and at least one of them is visited - at this point you can approve that at least one cycle is detected.

Connectivity

After that, if the cycle is detected, return False, because one condition is already unsatisfied.

If cycle is not found, you should check the connectivity, and you can do it either:

Call hasOneComponentFunction()
Check the visited array directly

The second approach is much faster, and you don’t have to traverse again, like with calling hasOneComponent(). Return if all vertices are visited.

Завдання

Implement isTree() method step by step.

Завдання

Implement isTree() method step by step.

Перейдіть на комп'ютер для реальної практикиПродовжуйте з того місця, де ви зупинились, використовуючи один з наведених нижче варіантів

Все було зрозуміло?

Секція 2. Розділ 6

Is a Tree

BFS check if graph is a tree

And the last one required method is a bit simpler. Tree graph is a one-component acyclic graph, so you have to check first, if it is acyclic.

Acyclic

Connectivity

After that, if the cycle is detected, return False, because one condition is already unsatisfied.

If cycle is not found, you should check the connectivity, and you can do it either:

Call hasOneComponentFunction()
Check the visited array directly

The second approach is much faster, and you don’t have to traverse again, like with calling hasOneComponent(). Return if all vertices are visited.

Завдання

Implement isTree() method step by step.

Завдання

Implement isTree() method step by step.

Все було зрозуміло?

Секція 2. Розділ 6

Is a Tree

BFS check if graph is a tree

And the last one required method is a bit simpler. Tree graph is a one-component acyclic graph, so you have to check first, if it is acyclic.

Acyclic

Connectivity

After that, if the cycle is detected, return False, because one condition is already unsatisfied.

If cycle is not found, you should check the connectivity, and you can do it either:

Call hasOneComponentFunction()
Check the visited array directly

The second approach is much faster, and you don’t have to traverse again, like with calling hasOneComponent(). Return if all vertices are visited.

Завдання

Implement isTree() method step by step.

Завдання

Implement isTree() method step by step.

Все було зрозуміло?

BFS check if graph is a tree

And the last one required method is a bit simpler. Tree graph is a one-component acyclic graph, so you have to check first, if it is acyclic.

Acyclic

Connectivity

After that, if the cycle is detected, return False, because one condition is already unsatisfied.

If cycle is not found, you should check the connectivity, and you can do it either:

Call hasOneComponentFunction()
Check the visited array directly

The second approach is much faster, and you don’t have to traverse again, like with calling hasOneComponent(). Return if all vertices are visited.

Завдання

Implement isTree() method step by step.

Секція 2. Розділ 6