Algorithms/Unweighted Graph Algorithms

From Wikibooks, open books for an open world
Jump to: navigation, search

Top, Chapters: 1, 2, 3, 4, 5, 6, 7, 8, 9, A

Representation of Graph[edit]

Adjacency Matrix[edit]

Adjacency LIst[edit]

Comparison[edit]

Depth First Search[edit]

Pseudocode[edit]

 dfs(vertex w)
   if w has already been marked visited
     return
   mark w as visited
   for each adjacent vertex v
     dfs(v)

Properties[edit]

Classification of Edge[edit]

Tree Edge[edit]

Backward Edge[edit]

Forward Edge[edit]

Cross Edge[edit]

IT is good techniques from :Yogesh Jakhar

Breadth First Search[edit]

Pseudocode[edit]

bfs ( x ):

 q insert x;
 while (q not empty )
    y = remove head  q
    visit y
    mark y
    for each z adjacent y 
      q add tail z

Example[edit]

Correctness[edit]

Analysis[edit]

Usage[edit]

A breadth first search can be used to explore a database schema, in an attempt to turn it into an xml schema. This is done by naming the root table, and then doing a referential breadth first search . The search is both done on the refering and referred ends, so if another table refers to to the current node being searched, than that table has a one-to-many relationship in the xml schema, otherwise it is many-to-one.

Classical Graph Problems[edit]

Topological Sort[edit]

A topological sort is an ordering of vertices in a directed acyclic graph such that if there is a path from vi to vj, then vj appears after vi in the ordering.

Given a graph G, a topological sort can be performed with the following steps.

  1. Find any vertex with no incoming edges and list it.
  2. Remove it along with its edges. (The edges should all be outgoing.)
  3. Repeat step 1 until there are no more vertices.

An alternative is to use depth first search reverse post-order. This means recursively insert a node after visiting is children in a list, and reverse the list. This works inductively because the deepest children have no chidren and will be inserted first. Then their parents, then the grandparents .

Topological sort is useful when calculating child properties that depend on the same property of parents, like distance from a start node. This allows finding the shortest path to a target node

Strongly Connected Components[edit]

Articulation Vertex[edit]

Bridge[edit]

Diameter[edit]


Top, Chapters: 1, 2, 3, 4, 5, 6, 7, 8, 9, A