# Discussion on Graphs

Discover more aspects regarding graphs.

## We'll cover the following

## Additional notes

The running times of the depth-first-search and breadth-first-search algorithms are somewhat overstated by the following theorems we explained before:

- When given as input a
`Graph`

,`g`

, that is implemented using the`AdjacencyLists`

data structure, the`bfs(g, r)`

algorithm runs in $O(n + m)$ time. - When given as input a
`Graph`

,`g`

, that is implemented using the`AdjacencyLists`

data structure, the`dfs(g,r)`

and`dfs2(g,r)`

algorithms each run in $O(n + m)$ time.

Define $n_r$ as the number of vertices, $i$, of $G$, for which there exists a path from $r$ to $i$. Define $m_r$ as the number of edges that have these vertices as their sources. Then the following theorem is a more precise statement of the running times of the breadth-first-search and depth-first-search algorithms.

**Theorem:** When given as input a `Graph`

, `g`

, that is implemented using the `AdjacencyLists`

data structure, the `bfs(g,r)`

, `dfs(g,r)`

and `dfs2(g,r)`

algorithms each run in $O(n_r + m_r)$ time.

Breadth-first-search seems to have been discovered independently by

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy