Algorithms/Unweighted Graph Algorithms

From Wikibooks, open books for an open world
< Algorithms(Redirected from Algorithms/Chapter 9)
Jump to: navigation, search

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

Contents

[edit] Representation of Graph

[edit] Adjacency Matrix

[edit] Adjacency LIst

[edit] Comparsion

[edit] Depth First Search

[edit] Pseudocode

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

[edit] Properties

[edit] Classification of Edge

[edit] Tree Edge

[edit] Backward Edge

[edit] Forward Edge

[edit] Cross Edge

IT is good techniques from :Yogesh Jakhar

[edit] Breadth First Search

[edit] Pseudocode

[edit] Example

[edit] Correctness

[edit] Analysis

[edit] Classical Graph Problems

[edit] Topological Sort

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.

  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.

[edit] Strongly Connected Components

[edit] Articulation Vertex

[edit] Bridge

[edit] Diameter


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

Personal tools
Namespaces
Variants
Actions
Navigation
Community
Toolbox
Sister projects
Print/export