Breadth First Search

Question 1

Graph

Answer 1

Models connections. Composed of nodes and edges

Question 2

Shortest-path-problem

Answer 2

Solved by breadth first search algorithm

Question 3

Questions breadth first search can answer

Answer 3

Is there a path from Node A to Node B

What is the shortest path between two nodes

Question 4

Breadth-first-search algorithm

Answer 4

Uses a queue to search first degree connection, then 2nd degree connections then 3rd degree etc.

Keep a list of nodes you have already checked to avoid an infinite loop.

Add connections of nodes to end of queue

Question 5

Queue

Answer 5

Data structure like a line. The first in line is the first to leave
Enqueue
Dequeue

Question 6

Enqueue

Answer 6

Like push()
Add to end of queue

Question 7

Dequeue

Answer 7

Remove from start of queue

Like pop()

Question 8

Queue vs stack

Answer 8

Stacks are LIFO - stack of books
Queues are FIFO - line of people

Question 9

Implementation of graph

Answer 9

A hash of nodes to their 1st degree connections

Question 10

Directed vs undirected graphs

Answer 10

Directed graphs are 1 way

Question 11

Breadth first search runtime

Answer 11

O(Vertices+ edges)

Question 12

Topological sort

Answer 12

A graph where if node A depends on node B, it will appear later in the list

Question 13

Tree

Answer 13

A type of graph where edges don’t point back to nodes