Graphs

Undirected Graphs

vertices, edges

adjacency matrix O(V^2), adjacency list  O(V+E)

explore(G,v):

i/p G = (V,E), v belongs to V

o/p visited(u) set to true for all nodes reachable from v

visited(v) = true;

previsit(v)

for all edges(v,u) in E

     if not visited(u): explore (u)

postvisit(v)

explore visits all nodes reachable from v. To explore all G we need to restart explore where v is not yet visited.

dfs(G):

for all v belongs to V

   visited(v) = false

for all v belongs to V

  if not visited(v): explore (G,v)

 

dfs can be used to check connectivity and assign ccnum for each connected component.

previsit & postvisit orderings:

previsit(v):

pre[v] = clock

clock = clock+1

postvisit(v):

post[v]= clock

clock = clock+1

for any 2 nodes u,v in undirected graphs either pre[u], post[u] & pre[v], post[v] are disjoint or contained with in one another.

for undirected graphs you have tree edges or back edges.

Directed Graphs

parent, child & ancestors, descendants.

forward edge, backward edges, cross edges, (and also the original tree edges).  How to determine the edges from th pre, post numbers? Applyingthe below ordering doesn’t seem to work – what am i missing?

[u   [v    ]v  ]u   Tree/fw edges

[v   [u    ]u  ]v  backward edges

[v   ]v    [u   ]u  cross edge

DAG (Drected Acyclic Gaph):  A DG has a cycle if and only if dfs reveals a backward edge.

If a graph is a DAG we can liniearize (topological sort) the vertices. there can be multiple linearizations. DAG can be linearized in the decreasing order of post numbers. sink has lowest post number, source has highest post number.

Every DAG has atleast one source and atleast one sink. to linearize find the source, delete it & repeat on the remaining graph.

For DG Connectivity is defined as “there is a path between any 2 vertices” of the connected component. A DG is a DAG of it’s connected components.

Kosaraju’s algorithm for determining the connected components of a DG:

1) Invert the Grapgh G -> GR

2) Run CC analysis on node based on the post order from 1

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s