Algorithms/Unweighted Graph Algorithms
From Wikibooks, open books for an open world
< Algorithms(Redirected from Algorithms/Chapter 9)
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.
- 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.
