Graph Algorithms

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

Consider the following algorithm someAlgo that takes an undirected graph G as input. someAlgo (G) 1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex in G at...

Let $$G$$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements...

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P: Always finds a negative weighted cycle, if one exist s. Q: Finds whether any...

Let G = (V, E) be a directed graph with n vertices. A path from v i to v j in G is sequence of vertices (v i , v i +1, ……., v j ) such that (v k , v k +1) ∈ E for all k in i throug...