Algorithms/Unweighted Graph Algorithms
- 1 Representation of Graph
- 2 Depth First Search
- 3 Breadth First Search
- 4 Classical Graph Problems
Representation of Graph
Depth First Search
dfs(vertex w) if w has already been marked visited return mark w as visited for each adjacent vertex v dfs(v)
Classification of Edge
IT is good techniques from :Yogesh Jakhar
Breadth First Search
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
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
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.
- Find any vertex with no incoming edges and list it.
- Remove it along with its edges. (The edges should all be outgoing.)
- 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