Graph Algorithms

Graph Basics

Graphs are made up of nodes and edges, where nodes are connected by edges. Graphs can have either weighted edges, in which each edge has a certain length, or unweighted, in which case all edges have the same length. Edges are either directed, which means they can be traversed only in one direction, or undirected, which means that they can be traversed in both directions.

Trees

A tree is a special type of graph satisfying two constraints: it is acyclic, meaning there are no cycles, and the number of edges is one less than the number of nodes. Trees satisfy the property that for any two nodes A and B, there is exactly one way to travel between A and B.

Graph Representations

Graphs can be represented in three ways:

• Adjacency List most frequently used when nodes are large
• Adjacency Matrix when nodes are small
• Edge List

We use c++ pair<int, int> to store the destination node ID and weight.

When Graph nodes are small, we can use a 2D array to store the graph.

Graph Traversal Algorithms

Graph traversal is the process of visiting or checking each vertex in a graph. This is useful when we want to determine which vertices can be visited, whether there exists a path from one vertex to another, and so forth. There are two algorithms for graph traversal, namely depth-first search (DFS) and breadth-first search (BFS).

Breadth-first search visits nodes in order of distance away from the starting node; it first visits all nodes that are one edge away, then all nodes that are two edges away, and so on.