Data Structures and Algorithms B
  • Introduction
  • Stable Marrage
  • Huffman Codes
    • ABL
    • Implementation
  • Graph Algorithms
    • Connect Component
    • Bipartiteness
    • Strongly Connected Components
      • Implementation
    • Topological Sort
      • Implementation 1
      • Implementation 2
    • Dijkstra’s Shortest Path
    • Minimum Spanning Tree
      • Prims
        • Implementation 1
      • Kruskels
        • Implementation 1
      • Traveling Salesman Problem
    • k-Clustering
    • Dynamic Programming with Trees
      • Implementation 1
      • Implementation 2
    • Disjoint Sets
      • Implementation
    • Eularian Cycle
      • Implementation
    • Hamiltonian Path
      • Implementation
  • Divide and Conquer
    • Merge Sort
    • Integer Multiplication
    • Closest Pair
    • Master Method
  • Dynamic Programming
    • Interval Scheduling
    • Knapsack Problem
  • Network Flow
    • Maximum Network Flow
    • Improvements
    • Image Segmentation
  • String Algorithms
    • Z Algorithm
    • Boyer-Moore
    • Knuth-Morris-Pratt
    • Suffix Trees
      • Naive Implementation
      • Ukkonens Algorithm
        • Implementation
      • Applications
        • Longest Common Substring
        • Longest Palindromic Substring
        • Longest Repeated Substring
  • Randomized Algorithms
    • Bloom Filters
      • Implementation
Powered by GitBook
On this page
  • Constraints
  • Algorithm

Was this helpful?

  1. Graph Algorithms

Topological Sort

PreviousImplementationNextImplementation 1

Last updated 5 years ago

Was this helpful?

  • A topological ordering of a graph is an ordering of all the vertecies in a graph such that if node A -> B, then A will come before B in the ordering.

  • We can think of the edges as B depends on A. So in order to get to node B, we must get through node A.

  • If a graph is a DAG, it has topological ordering, and if a graph has topological ordering, it is also a DAG.

Constraints

  • A graph must be a DAG (directed acyclic graph) for topological sorting to be possible.

    • Why:

      • If non-directed, then A <--> B for all nodes, so there is no ordering possible.

      • Acyclic because if a cycle does exist, then then that means there exist at least one cycle in the graph where all the nodes depend on each other (which do we chose first?).

Algorithm

  1. Select node S that has no incoming edges, and push into some set.

  2. Remove node S from graph (and its connections)

  3. See 1.

5
a->b
a->c
a->d
a->e
b->d
c->d
c->e
d->e