MOVE37 About Blog Project Links

Graph AlgorithmsTM

Graph AlgorithmsTM

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

Graph Terminology

Vertices(V): Objects in a graph. Also known as node.

Edges(E): A set of pairs of vertices. In a weighted graph, each edge is assigned a weight. A graph is directed if the edges can be traversed in one direction only.

Graph: A pair of sets (V, E).

Path: A walk is a sequence of edges, where each successive pair of edges shares one vertex. A walk if it visits each vertex at most once. The length of a path is the number of edges in it.

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. Multi-graphs are Non-simple graphs.

Neighbor: If there is an edge connects vertices {u, v}, u and v are neighbors. A graph is regular if the degree of every node is a constant d. A graph is complete if the degree of every node is n−1, i.e., the graph contains all possible edges between the nodes.

Degree: How many neighbors a node has.

Cycle: A path that starts and ends at the same vertex, and has at least one edge. Forests: Graph without cycle for undirected acyclic graph.

Spanning Tree: A subgraph of graph G that is a tree and contains every vertex of G. A graph has a spanning tree if and only if it is connected.

Directed Graph: Assuming we have a directed edge u -> v, then Predecessor: u is a predecessor of v Successor: v is a successor of u In-degree: The number of predecessor for a node Out-Degree: The number of successor for a node Strongly Connected: There is a directed path from any vertex to any other Acyclic: The graph does not has any cycle.

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 neighbors 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: