Consider a directed graph G = (N,E). Breadth-first search and depth-first search both have a runtime...

 

Transcribed Image Text:

Consider a directed graph G = (N,E). Breadth-first search and depth-first search both have a runtime complexity of ~|N|+|E| if we represent the graph with an adjacency list. P1.1. What is the runtime complexity of breadth-first search and depth-first search when we use the matrix representation? Explain your answer. P1.2. Consider the ordered edge list representation that represents a graph by an ordered array A that holds |ε| edges. The order of edges is as follows: edge (n₁, m₁) € A comes before (n2, m2) € A if id(n₁) < id(n₂) or if id(n₁) =id(n₁) Aid(m₁) ≤ id(m2). What is the runtime complexity of breadth-first search and depth-first search when we use the ordered edge list representation? Explain your answer. Consider a directed graph G = (N,E). Breadth-first search and depth-first search both have a runtime complexity of ~|N|+|E| if we represent the graph with an adjacency list. P1.1. What is the runtime complexity of breadth-first search and depth-first search when we use the matrix representation? Explain your answer. P1.2. Consider the ordered edge list representation that represents a graph by an ordered array A that holds |ε| edges. The order of edges is as follows: edge (n₁, m₁) € A comes before (n2, m2) € A if id(n₁) < id(n₂) or if id(n₁) =id(n₁) Aid(m₁) ≤ id(m2). What is the runtime complexity of breadth-first search and depth-first search when we use the ordered edge list representation? Explain your answer.