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

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