# Algorithms/Unweighted Graph Algorithms

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

## Contents

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