Algorithms/Unweighted Graph Algorithms

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

Representation of Graph

Adjacency Matrix

Adjacency LIst

Comparsion

Depth First Search

Pseudocode

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

Properties

Classification of Edge

Tree Edge

Backward Edge

Forward Edge

Cross Edge

IT is good techniques from :Yogesh Jakhar

Breadth First Search

Pseudocode

Example

Correctness

Analysis

Usage

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

Topological Sort

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.

1. Find any vertex with no incoming edges and list it.
2. Remove it along with its edges. (The edges should all be outgoing.)
3. Repeat step 1 until there are no more vertices.

Strongly Connected Components

Articulation Vertex

Bridge

Diameter

---

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