Graph Theory

Question 1

What is a tree?

Answer 1

An undirected graph with no cycles

Question 2

What is a rooted tree?

Answer 2

Tree with a designated root node where every edge either points away from or towards the root node

Question 3

what is an adjacency list?

Answer 3

a way to represent a graph as a map from nodes to lists of edges

Question 4

write generic dis for a graph

Answer 4

function dis(at):
if visited[at]: return true
visited[at] = true

neighbors = graph[at]
for next in neighbors: dfs(next)

# Start DFS at node zero
start_node = 0
dfs(start_node)