Swiftorial Logo
Home
Swift Lessons
Matchups
CodeSnaps
Tutorials
Career
Resources

Graph Algorithms Tutorial

1. Introduction to Graphs

A graph is a collection of nodes (or vertices) and edges that connect pairs of nodes. Graphs are used to model pairwise relations between objects. In computer science, they are widely used in various applications such as social networks, transportation networks, and more.

2. Types of Graphs

Graphs can be classified into several types:

  • Directed Graphs: Edges have a direction, indicating the relationship goes from one vertex to another.
  • Undirected Graphs: Edges do not have a direction; the relationship is bidirectional.
  • Weighted Graphs: Edges have weights, representing cost, distance, or time.
  • Unweighted Graphs: All edges are considered equal.
  • Cyclic Graphs: Graphs that contain at least one cycle.
  • Acyclic Graphs: Graphs that do not contain cycles.

3. Basic Graph Representations

There are two common ways to represent graphs:

  • Adjacency Matrix: A 2D array where the element at row i and column j indicates the presence or weight of an edge between vertex i and vertex j.
  • Adjacency List: An array of lists where each list corresponds to a vertex and contains the nodes adjacent to that vertex.

Example of Adjacency List:

Graph: A -- B, A -- C, B -- D

A: [B, C]
B: [A, D]
C: [A]
D: [B]

4. Graph Traversal Algorithms

Graph traversal is a technique for visiting all the nodes in a graph. The two most common traversal algorithms are:

4.1 Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (either explicitly or via recursion).

DFS Example:

Graph: A -- B, A -- C, B -- D

Traversal Order (starting from A):

A → B → D → C

4.2 Breadth-First Search (BFS)

BFS explores all the neighbor nodes at the present depth prior to moving on to nodes at the next depth level. It uses a queue.

BFS Example:

Graph: A -- B, A -- C, B -- D

Traversal Order (starting from A):

A → B → C → D

5. Shortest Path Algorithms

Finding the shortest path in a graph is a common problem. The most famous algorithms for solving this problem include:

5.1 Dijkstra's Algorithm

This algorithm finds the shortest path from a starting node to all other nodes in a weighted graph with non-negative weights.

Dijkstra's Algorithm Example:

Graph: A (1) -- B (2), A (4) -- C (1), B (1) -- C (2)

Shortest path from A to C:

A → C (Cost: 1)

5.2 Bellman-Ford Algorithm

Unlike Dijkstra's, Bellman-Ford can handle graphs with negative weights. It computes the shortest paths from a single source vertex to all other vertices.

6. Minimum Spanning Tree (MST) Algorithms

An MST of a graph is a subset of edges that connects all vertices with the minimum total edge weight. Common algorithms include:

6.1 Prim's Algorithm

Prim’s algorithm builds the MST by adding edges one at a time, choosing the smallest edge that connects a vertex in the MST to a vertex outside the MST.

6.2 Kruskal's Algorithm

Kruskal’s algorithm adds edges in increasing order of weight, ensuring no cycles are formed until all vertices are connected.

7. Conclusion

Graph algorithms are fundamental in computer science and have numerous applications in various fields. Mastering these algorithms will enhance your problem-solving skills and enable you to tackle complex real-world problems effectively.