## Representation of GraphEdit

## Depth First SearchEdit

### PseudocodeEdit

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

### PropertiesEdit

### Classification of EdgeEdit

#### Tree EdgeEdit

#### Backward EdgeEdit

#### Forward EdgeEdit

#### Cross EdgeEdit

IT is good techniques from :Yogesh Jakhar

## Breadth First SearchEdit

### PseudocodeEdit

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

### ExampleEdit

### CorrectnessEdit

### AnalysisEdit

### UsageEdit

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 ProblemsEdit

### Topological SortEdit

A topological sort is an ordering of vertices in a directed acyclic graph such that if there is a path from v_{i} to v_{j}, then v_{j} appears after v_{i} 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