Graph Algorithms

  • In this section, we discuss algorithms involving graphs.

  • We will look at several such algorithms:

    Graph Traversal

    Visit each vertex in a graph once.

    Shortest path

    find the shortest path between two vertices.

    Travelling salesman

    Find a path that contains a permutation of every node in the graph with minimized total cost.

    Minimum spanning tree (MST)

    Construct a spanning tree connecting all the vertices in a graph minimizing the cost.

  • And here are some more graph-processing problems:

    s-t Path

    Is there a path between vertices s and t?

    Shortest s-t Path

    What is the shortest path between vertices s and t?


    Does the graph contain any cycles?

    Euler Tour

    Is there a cycle that uses every edge exactly once?

    Hamilton Tour

    Is there a cycle that uses every vertex exactly once?


    Is the graph connected, i.e. is there a path between all vertex pairs?


    Is there a vertex whose removal disconnects the graph?


    Can you draw the graph on a piece of paper with no crossing edges?


    Are two graphs isomorphic (the same graph in disguise).

results matching ""

    No results matching ""