Graphs
Vertices, edges, adjacency lists, BFS and DFS intuition.
What you will learn
- Represent a graph as adjacency list
- Run BFS for shortest unweighted path
- Know when graphs model real systems
python
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": [],
"D": [],
}
def bfs(start):
seen = {start}
q = deque([start])
while q:
node = q.popleft()
print(node)
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
q.append(nxt)Try it yourself
Add a target to BFS and return the path when found.