MOVE37 About Blog Project Links

Graph AlgorithmsTM

Graph AlgorithmsTM

  1. Graph Terminology
  2. Representation
  3. Graph Traveral and Their Applications
  4. Shortest Path

Graph Terminology

*Simple Graph: Loops are edges from a vertex to itself. Parallel Edges are multiple edges with the same endpoints. Simple graphs are Graphs without loops and parallel edges. Multigraphs are Non-simple graphs.

Graph Representation

A graph can be represented using either an adjacency matrix or an adjacency list. An adjacency matrix is good for checking and updating the connectivity between 2 vertices. An adjacency list is helpful for saving space when the graph is sparse.

In Python, we usually use a dict to store a graph, with vertex as key and a list of nerighbors as values. If the edges has weight, we can use a tuple of (neighbor, weight) to represent it.

Graph Traveral and Their Applications

Shortest Path

Syntax Bellman–Ford Dijkstra Floyd–Warshall
Source Type Single Source Single Source Multi Source
Cycle Fail on Negative Cycle    
Negative Edge Can detect Negative Edge Fail on Negative Edge  

Share this: