Remarks: All the graphs here are without self loops and parallel edges, and anti
ID: 3715180 • Letter: R
Question
Remarks: All the graphs here are without self loops and parallel edges, and anti-parallel edges. When we speak of a flow network, we mean there are capacities c(e) ? 0 on the edges, the graph G is directed with a source s and a destination t. In all the algorithms, always explain their correctness and analyze their complexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit.
• Question 3: Given an undirected graph, give an algorithm that for every v returns the number of connected componnents in G ? v.
Explanation / Answer
dfs(node u) for each node v connected to u : if v is not visited : visited[v] = true dfs(v) for each node u: if u is not visited : visited[u] = true connected_component += 1 dfs(u)