11 Graphs

Question 1

Dense Graphs

Answer 1

If E is around V^2

Question 2

Sparse Graphs

Answer 2

If E is Around V

Question 3

How must storage does Adjacency lists take?

Answer 3

O(V+E)

Question 4

Two Approaches to Graph Tranversal

Answer 4

Breadth-first
Depth-first Traversal

Question 5

Breadth-First Search

Answer 5

Find shortest paths in graph

Question 6

Depth-First Search

Answer 6

Discover various structural properties of graph

Question 7

Total Running Time of DFS

Answer 7

Big Theta (V+E)

Question 8

Forest

Answer 8

An acyclic graph G that may be disconnected.

Question 9

Tree Edge

Answer 9

Found by exploring (u, v).

Question 10

Back Edge

Answer 10

Where u is a descendant of v

Question 11

Forward Edge

Answer 11

Where v is a descendant of u.

Question 12

Cross Edge

Answer 12

Any other edge. Can go between vertices in same depth-first tree or in different depth-first trees.

Question 13

In DFS of an undirected graph, we get:

Answer 13

Only tree and back edges. No forward or cross edges.

Question 14

A graph is acyclic if :

Answer 14

a DFS yeilds no back edges.

Question 15

How to find whether a graph has a cycle or not?

Answer 15

Run DFS

Question 16

Directed Acyclic Graph

Answer 16

DAG

A directed graph with no directed cycles.

Question 17

Topological Sort

Answer 17

Linear ordering of all vertices in graph G such that vertex u comes before vertex v.

Question 18

Time complexity of topological Sort

Answer 18

Big Theta (V+E)

Question 19

A topological sort can be performed on any graph that is :

Answer 19

Directed and Acyclic

Question 20

An undirected graph is said to be connected if:

Answer 20

there is a path between every pair of vertices.

Question 21

A directed graph is strongly connected if

Answer 21

there is a directed path between every pair of vertices.

Question 22

Kosaraju’s Algorithm

Answer 22

Uses DFS to find the strongly-connected components of a directed graph.

Time: Big Theta(V+E)