11 Graphs Flashcards

1
Q

Dense Graphs

A

If E is around V^2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Sparse Graphs

A

If E is Around V

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How must storage does Adjacency lists take?

A

O(V+E)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Two Approaches to Graph Tranversal

A

Breadth-first
Depth-first Traversal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Breadth-First Search

A

Find shortest paths in graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Depth-First Search

A

Discover various structural properties of graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Total Running Time of DFS

A

Big Theta (V+E)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Forest

A

An acyclic graph G that may be disconnected.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Tree Edge

A

Found by exploring (u, v).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Back Edge

A

Where u is a descendant of v

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Forward Edge

A

Where v is a descendant of u.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Cross Edge

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

In DFS of an undirected graph, we get:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

A graph is acyclic if :

A

a DFS yeilds no back edges.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

Run DFS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Directed Acyclic Graph

A

DAG

A directed graph with no directed cycles.

17
Q

Topological Sort

A

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

18
Q

Time complexity of topological Sort

A

Big Theta (V+E)

19
Q

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

A

Directed and Acyclic

20
Q

An undirected graph is said to be connected if:

A

there is a path between every pair of vertices.

21
Q

A directed graph is strongly connected if

A

there is a directed path between every pair of vertices.

22
Q

Kosaraju’s Algorithm

A

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

Time: Big Theta(V+E)