CHPT 22 Elementary graph algorithms

Representing the graph

Adjacent list

It consists of an array of vertices. In each entry u, adj[u] stores all the vertices v that has an edge u,v connected. The asymptotic space is O(E + V) but counter-intuitively, we need more space to store undirected graph than directed because for directed graph, an edge (u, v) will only be stored in adj[u]. But for an undirected graph, we need to store v in adj[u] and u in adj[v].

Adjacency matrix

A |V| * |V| matrix such that A_{ij} = 1 if (i,j) \in E. It is symmetric so for undirected graph we can only store the upper trangule. We can also store weighted graph. A_{ij} = w for (i,j) \in E whose weight is w. For unconnected vertices, the weights between would be inf.(or 0 or NULL)

BFS

A graph traversal algo that explores the shallow vertices first. And the simple path from s to v forms a shortest path. The algorithm explores all vertices with distance k first before exploring vertices with distance k + 1

We can see that this algo use a queue (FIFO) to imitate the exploring the shallowest point first algo.

Grey nodes are nodes that haven’t explored all its adjacent vertices. The while loop from line 10 to 18 will run as long as there are grey nodes.

Exercise

single bit store color

Show that using a single bit to store each vertex color suffices by arguing that the
BFS procedure would produce the same result if lines 5 and 14 were removed.

u, the predecessor needs to become black once all its adjacent nodes are discovered(greyed). The for loop at line 12 did exactly that.

2 coloring problem

n nodes, r pair, give an algo that in O(n + r) time to decide if we can have pair color1 with color 2.

Even level of BFS is group 1 and odd level of BFS is group 2.

Diameter of a tree.

The diameter of a tree T is the largest of all shortest-path distances in the tree. Gave an algo that finds it.

Run BFS from a any node v . It will find the node that’s furthest from it. Then run BFS again from the furthest node, the largest distance will be the diameter.

DFS

Explores edges out of the most recently discovered vertex that still has unexplored edges leaving it.

This algo uses recursion.

Classification of edges

 classes of edges
Its from here!

Exercise

iterative DFS

DFS tree has only outgoing edge

Explain how a vertex u of a directed graph can end up in a depth-first tree containing only u, even though u has both incoming and outgoing edges in G.

DFS for connected component

Show that we can use a depth-first search of an undirected graph G to identify the
connected components of G, and that the depth-first forest contains as many trees
as G has connected components. More precisely, show how to modify depth-first
search so that it assigns to each vertex v an integer label v.cc between 1 and k,
where k is the number of connected components of G, such that u:cc = c:cc if
and only if u and c are in the same connected component.

Topological sort(on a dag)

DAG is directed acyclic graph.
A topoligical sort on a dag in a linear order of all its vertices such that if G contains an edge(u,v) then u appears before v in the ordering.
We can think of it as a ordering such that all directed edge go from left to right.

**It is often used for scheduling ** where each directed edge (u,v) means u a prerequisite for v.

Algo

Call DFS(G) to compute the finish times for each vertex v.
As they finish insert them into the front of a linkedlist.
return the linked list.

Why it works.

lemma 1: a directed graph is acyclic if and only if a DFS of G yields bo back edges.
An edge (u,v) is a back edge if v is an ancestor of u.

First we want to show 1 if no back edge -> no cycle
Then we want to show 2. if no cycle -> no back edge
Using contra positive we know 1 is equivalent to if cycle -> G has back edge and 2 is equivalent to if back-edge -> has cycle
if DFS has back edge (u,v):
v is an ancestor of u, means there is a path from v to u. The back edge will form a cycle.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax