Graphs-Book Notes

Question 1

Adjacency Matrix Time?

Defn?

Sparse or Dense?

Answer 1

Edge Check O(1)

Space O(n^2)

Represents graph in n x n matrix, whose (i,j) entry is 1 - if there is an edge, 0 - otherwise.

Undirected graphs, the matrix is symmetric (as it can be traversed in either direction) Used on dense graph

Question 2

Adjacency List Time?

Defn?

Sparse or Dense?

Answer 2

Checking for edge: O(|E| + |V|)

Space: O(E)

Consists of linked list of vertices, each vertex has a list of the vertices which u has an outgoing edge.

Used on sparse graph

Question 3

Depth First Search

Time?

Algo?

Answer 3

Time: O(|E| + |V|) Linear Time

dfs (G):

NOTE: This top level handles the disconnected graph base by making sure to kick off a new explore to traverse any vertex not covered by the recursion below.

for all v in V

visited(v) = false

for all v in V

if not visited(v)

explore(v)

explore(G,V)

Input G = (V, E) is a graph;

Output: visited u is true for all nodes u reachable from v

visited(v) = true

previsit(v)

for each edge (v,u) in E:

if not visited (u)

explore(u)

postvisit(v)

Question 4

A graph is connected if?

Answer 4

There is a path between any pair of vertices.

Question 5

What a connected components?

Answer 5

A subgraph that that every vertex is connected internally, but has no edges that connect out to the remaining vertices.

Question 6

What are pre and post visit for

Algo?

Defn?

Uses?

Answer 6

previsit(v)

pre[v] = clock

clock = clock + 1

postvisit(v)

post[v] = clock

clock = clock + 1

Previsit keeps track of when a node is first discovered in the tree, post visit is the time when all of it’s child nodes have finished being discovered.

Question 7

Types of edges in DFS for Directed Graph

Tree Edge

Forward Edge

Back Edge

Cross Edge

Answer 7

Tree - Main edges that are part of forest (traversal)

Forward edges - edges that lead from a node to a non child descendant

Back Edges - edges that lead to an ancestor

Cross Edges - not a descendant or ancestor, lead to peer that was already explored.

———————– (Probably not needed)

Can be determined by pre/post number.

Tree/Forward U[V[]V ]U

Back V[U[]U ]V

Cross: V[]V U[]U

Question 8

Cycle/Acyclic

How and Time To discover?

Answer 8

A Cycle can be discovered with a depth first search in linear time if it encoutnerd a back edge.

Question 9

What is a topological sort of a graph (linearize)

Time?

How is it done?

Answer 9

Time: Linear

A topological sort of a graph allows it to be ordered in a way that each edge goes from an earlier vertex to a later one. (E.g.) Gives order of precidence so that constraints (pre conditions) of a vertex are all satistfied.

Perform tasks in decreating order of their post number.

Sink: Node with smallest post order

Source: Node with highest post order.

Question 10

Strongly Connected Components

Answer 10

Two nodes u and v in a directed graph are connected if there is a path from u to v and a path from v to u.

vertexes that share this property can be parition into a disjoint set, where each disjoint set is a “strongly connected componet” From any node in the set you can get to any other node in the set.

Merging “Strongly Connected Components” into a meta-node will leave a dag. Every directed graph is a dag of it’s strongly connected components.

Question 11

Strongly Connected Component Algorithm

Time:

Algo:

Answer 11

Time: Linear O(|E| + |V|)

Algo:

1. Reverse the graph and run DFS with pre/post numbers.
2. Select numbers from Highest post number to least, this gives us Source nodes for the Reverse Graph, which are actually sink nodes for the regular graph which is what we want.
3. Do a BFS from the first node in the list and remove everything it connects to. That is the first strongly connected component. Then repeat with the next highest number remaining in the list.

Question 12

Breadth First Search

Time:

Def:

Answer 12

Time: O(|V| + |E|) Linear.

Initially the queue Q consists only of s, the one node at distance 0. And for each subsequent distance d = 1, 2, 3, . . . , there is a point in time at which Q contains all the nodes at distance d and nothing else. As these nodes are processed (ejected off the front of the queue), their as-yet-unseen neighbors are injected into the end of the queue.

Question 13

Dijkstra’s Algorithm

Time

Defn

Answer 13

Based on Priority Queue (min heap/Binary)

O( (|V| + |E|) log|V|)

Dijkstra is a version of BFS, but uses a priority queue to prioritize node traversal basedon edge length.

Note: As each node is traversed it keeps a back pointer to it’s predecessor, this way the path back to the shortest can simply traverse back the pointers.

NOTE: NO NEGATIVE VALUES ALLOWED!

Question 14

Algorithms capable of finding shortest paths with negative weights.

Reminder: Negative weight cycles can be detected in some cases using these algorithms.

Answer 14

Bellman Ford = O(|V| * |E|)

Question 15

Minimum Spanning Tree

Def

Time

Answer 15

Take a graph and find the minimum weighted, acyclic tree, that keeps all nodes connected without introducing cycles.

2 Algorithms: Kruskal and Primm.

Question 16

Kruskal’s algorithm

time

def

Answer 16

O(|E| Log |V|).

Start with an empty graph and repeatedly add the next lightest edge that doesn’t produce a cycle.

(Based on Cut Property)

union by rank - starts with disjointed sets and does find and combine in log(n) time.

Question 17

Cut Property

Answer 17

In building a minimum spanning tree, if we connect two minimum spanning trees using the lightest edge between the two of them, the result is a new minimum spanning tree.

Question 18

Prim’s Algorithm

Time

Def

Answer 18

O(m log n)

Each iteration the smallest edge on the frontier is added to the tree, provided it doesn’t create a cycle.

(Almost identical to dijkstra, except dijkstra uses the full path length to the node as it’s key in the priority queue. Prim, only uses the weight of the indiviual edge on the frontier when it is added to the priority queue.)

Question 19

Max Flow - Min Cut

Time

Def

Answer 19

Time: O(C * |E| )