Breadth-first Search

Question 1

What is graph?

Answer 1

A graph models a set of connections
Graphs are made up of nodes and edges. A node can be directly connected to many other nodes. Those nodes are called its neighbors.

Question 2

What is breadth-first algorithm?

Answer 2

It’s a graph search algorithm

Question 3

What is queue?

Answer 3

It’s a data structure that store items, have two action: enqueue and dequeue, it’s use the first in first out technique.

Question 4

What is the breadth first algorithm running time ?

Answer 4

Adding to queue => o(1)
Search => O(V+E) (V for number of vertices, E for number of edges).

Question 5

What is topological sort?

Answer 5

If task A depends on task B, task A shows up later in the list. This is called a topological sort, and it’s a way to make an ordered list out of a graph.

Question 6

What is tree?

Answer 6

is a special type of graph, where no edges ever point back.

Question 7

What is the difference between direct and undirect graph?

Answer 7

• A directed graph has arrows, and the relationship follows the direction of the arrow.
• Undirected graphs don’t have arrows, and the relationship goes both ways.