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
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.