Video Explanation: Data structures: Introduction to graphs

Table of Contents:

Definition

Graph types

Graph Representations in Code

Graph Traversal Techniques

Graph Algorithms

Use Cases

Definition

A Graph is a collection of Nodes and Edges:

Nodes are points in a graph(also called vertices) such as cities, people, or numbers.

Edges are connections between nodes, such as roads, friendships.
- Can be directed (one-way) or undirected (two-way)
- Can be weighted (with costs) or unweighted

Graphs are used to model relationships and networks like:

Maps(cities connected by roads)

Social networks, where people are connected by friendships.

The internet (webpages linked together)

Note: A tree is a special type of undirected graph that is:

Connected: there is a path between every pair of nodes.

Acyclic: it contains no cycles.

Graph Types

Undirected Graph

- An undirected graph is a graph where edges have no direction, meaning each connection works both ways.
- Examples: a two-way street, or a friendship where if A is friends with B, then B is friends with A.

2. Directed Graph (Digraph)

- A directed graph is a graph where edges have direction, meaning each connection goes one way
- Examples: a one-way street, or a follow relationship where if A follows B, B does not necessarily follow A.
- A Directed Acyclic Graph (DAG) is a directed graph with no directed cycles. This means the edges have direction, and following those directions can never lead back to the same node.

3. Weighted Graph

- A weighted graph is a graph where each edge has a weight, usually representing distance, time, cost, or priority.
- Examples: A roadmap with travel time. A shipping route with price per delivery

Graph Representations in Code

Overview explanation: watch here

Adjacency List
- An adjacency list represents a graph as a map from each node to a list of its neighbors. Each key or index represents a node, and its value stores the nodes directly connected to it. (see video explanation)
- It is efficient for sparse graphs (few edges). Easy to traverse neighbors. Memory usage: O(V + E)

// Undirected Graph - Adjacency List
const adjacencyList = {
  A: ['B', 'D'],
  B: ['A', 'D', 'C'],
  C: ['B', 'E'],
  D: ['B', 'A'],
  E: ['C']
};

// Add edge (undirected)
function addEdgeList(graph, u, v) {
  if (!graph[u]) graph[u] = [];
  if (!graph[v]) graph[v] = [];

  graph[u].push(v);
  graph[v].push(u); // remove this line for directed graph
}

# Undirected Graph - Adjacency List
adjacency_list: dict[str, list[str]] = {
    "A": ["B", "D"],
    "B": ["A", "D", "C"],
    "C": ["B", "E"],
    "D": ["B", "A"],
    "E": ["C"],
}

# Add edge (undirected)
def add_edge_list(graph: dict[str, list[str]], u: str, v: str) -> None:
    if u not in graph:
        graph[u] = []
    if v not in graph:
        graph[v] = []

    graph[u].append(v)
    graph[v].append(u)  # remove this line for directed graph

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class GraphAdjacencyList {
    private final Map<String, List<String>> graph;

    public GraphAdjacencyList() {
        graph = new HashMap<>();
    }

    // Add edge (undirected)
    public void addEdgeList(String u, String v) {
        graph.putIfAbsent(u, new ArrayList<>());
        graph.putIfAbsent(v, new ArrayList<>());

        graph.get(u).add(v);
        graph.get(v).add(u); // remove this line for directed graph
    }

    public Map<String, List<String>> getGraph() {
        return graph;
    }
}

#include<string>
#include<unordered_map>
#include<vector>
using namespace std;

class GraphAdjacencyList {
private:
    unordered_map<string, vector<string>> graph;

public:
    // Add edge (undirected)
    void addEdgeList(const string& u, const string& v) {
        graph[u].push_back(v);
        graph[v].push_back(u); // remove this line for directed graph
    }

    const unordered_map<string, vector<string>>& getGraph() const {
        return graph;
    }
};

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_VERTICES100
#define MAX_NEIGHBORS100
#define MAX_NAME_LENGTH32

typedef struct {
    char name[MAX_NAME_LENGTH];
    char neighbors[MAX_NEIGHBORS][MAX_NAME_LENGTH];
    int neighborCount;
} Vertex;

typedef struct {
    Vertex vertices[MAX_VERTICES];
    int vertexCount;
} GraphAdjacencyList;

void initGraphAdjacencyList(GraphAdjacencyList* graph) {
    graph->vertexCount = 0;
}

int findVertexIndex(GraphAdjacencyList* graph, const char* name) {
    for (int i = 0; i < graph->vertexCount; i++) {
        if (strcmp(graph->vertices[i].name, name) == 0) {
            return i;
        }
    }
    return -1;
}

int addVertexIfMissing(GraphAdjacencyList* graph, const char* name) {
    int index = findVertexIndex(graph, name);
    if (index != -1) {
        return index;
    }

    if (graph->vertexCount >= MAX_VERTICES) {
        return -1;
    }

    index = graph->vertexCount;
    strncpy(graph->vertices[index].name, name, MAX_NAME_LENGTH - 1);
    graph->vertices[index].name[MAX_NAME_LENGTH - 1] = '\0';
    graph->vertices[index].neighborCount = 0;
    graph->vertexCount++;

    return index;
}

void addNeighbor(Vertex* vertex, const char* neighbor) {
    if (vertex->neighborCount >= MAX_NEIGHBORS) {
        return;
    }

    strncpy(vertex->neighbors[vertex->neighborCount], neighbor, MAX_NAME_LENGTH - 1);
    vertex->neighbors[vertex->neighborCount][MAX_NAME_LENGTH - 1] = '\0';
    vertex->neighborCount++;
}

// Add edge (undirected)
void addEdgeList(GraphAdjacencyList* graph, const char* u, const char* v) {
    int uIndex = addVertexIfMissing(graph, u);
    int vIndex = addVertexIfMissing(graph, v);

    if (uIndex == -1 || vIndex == -1) {
        return;
    }

    addNeighbor(&graph->vertices[uIndex], v);
    addNeighbor(&graph->vertices[vIndex], u); // remove this line for directed graph
}

// Undirected Graph - Adjacency List
type AdjacencyList = Record<string, string[]>;

const adjacencyList: AdjacencyList = {
  A: ['B', 'D'],
  B: ['A', 'D', 'C'],
  C: ['B', 'E'],
  D: ['B', 'A'],
  E: ['C']
};

// Add edge (undirected)
function addEdgeList(graph: AdjacencyList, u: string, v: string): void {
  if (!graph[u]) graph[u] = [];
  if (!graph[v]) graph[v] = [];

  graph[u].push(v);
  graph[v].push(u); // remove this line for directed graph
}

// Undirected Graph - Adjacency List
val adjacencyList = mutableMapOf(
    "A" to mutableListOf("B", "D"),
    "B" to mutableListOf("A", "D", "C"),
    "C" to mutableListOf("B", "E"),
    "D" to mutableListOf("B", "A"),
    "E" to mutableListOf("C")
)

// Add edge (undirected)
fun addEdgeList(graph: MutableMap<String, MutableList<String>>, u: String, v: String) {
    graph.putIfAbsent(u, mutableListOf())
    graph.putIfAbsent(v, mutableListOf())

    graph[u]?.add(v)
    graph[v]?.add(u) // remove this line for directed graph
}

// Undirected Graph - Adjacency List
var adjacencyList: [String: [String]] = [
    "A": ["B", "D"],
    "B": ["A", "D", "C"],
    "C": ["B", "E"],
    "D": ["B", "A"],
    "E": ["C"]
]

// Add edge (undirected)
func addEdgeList(_ graph: inout [String: [String]], _ u: String, _ v: String) {
    if graph[u] == nil {
        graph[u] = []
    }
    if graph[v] == nil {
        graph[v] = []
    }

    graph[u]?.append(v)
    graph[v]?.append(u) // remove this line for directed graph
}

using System.Collections.Generic;

// Undirected Graph - Adjacency List
var adjacencyList = new Dictionary<string, List<string>>
{
    ["A"] = new List<string> { "B", "D" },
    ["B"] = new List<string> { "A", "D", "C" },
    ["C"] = new List<string> { "B", "E" },
    ["D"] = new List<string> { "B", "A" },
    ["E"] = new List<string> { "C" }
};

// Add edge (undirected)
void AddEdgeList(Dictionary<string, List<string>> graph, string u, string v)
{
    if (!graph.ContainsKey(u)) graph[u] = new List<string>();
    if (!graph.ContainsKey(v)) graph[v] = new List<string>();

    graph[u].Add(v);
    graph[v].Add(u); // remove this line for directed graph
}

// Undirected Graph - Adjacency List
var adjacencyList = map[string][]string{
    "A": {"B", "D"},
    "B": {"A", "D", "C"},
    "C": {"B", "E"},
    "D": {"B", "A"},
    "E": {"C"},
}

// Add edge (undirected)
func addEdgeList(graph map[string][]string, u string, v string) {
    if _, exists := graph[u]; !exists {
        graph[u] = []string{}
    }
    if _, exists := graph[v]; !exists {
        graph[v] = []string{}
    }

    graph[u] = append(graph[u], v)
    graph[v] = append(graph[v], u) // remove this line for directed graph
}

2. Adjacency Matrix

An adjacency matrix uses a 2D array to represent a graph. If there’s an edge from node i to node j, then matrix[i][j] = 1 (or the weight of the edge); otherwise, it is usually 0, false, or Infinity, depending on how the graph is being represented. (see video explanation)
It is efficient for dense graphs. Constant-time edge existence check: O(1). Memory usage: O(V²)

// Directed Graph - Adjacency Matrix
const vertices = ['A', 'B', 'C', 'D', 'E'];
const indexMap = {
  A: 0,
  B: 1,
  C: 2,
  D: 3,
  E: 4
};

// Initialize 2D adjacency matrix with 0s
const adjacencyMatrix = Array.from(
  { length: vertices.length },
  () => Array(vertices.length).fill(0)
);

// Helper function to add a directed edge
function addEdgeMatrix(from, to) {
  const i = indexMap[from];
  const j = indexMap[to];

  if (i !== undefined && j !== undefined) {
    adjacencyMatrix[i][j] = 1; // use weights here if needed
  }
}

// Add edges based on diagram
addEdgeMatrix('A', 'B');
addEdgeMatrix('B', 'C');
addEdgeMatrix('B', 'D');
addEdgeMatrix('D', 'A');
addEdgeMatrix('E', 'C');

# Directed Graph - Adjacency Matrix
vertices = ["A", "B", "C", "D", "E"]
index_map = {
    "A": 0,
    "B": 1,
    "C": 2,
    "D": 3,
    "E": 4,
}

# Initialize 2D adjacency matrix with 0s
adjacency_matrix = [[0 for _ in vertices] for _ in vertices]

# Helper function to add a directed edge
def add_edge_matrix(from_node: str, to_node: str) -> None:
    i = index_map.get(from_node)
    j = index_map.get(to_node)

    if i is not None and j is not None:
        adjacency_matrix[i][j] = 1  # use weights here if needed


# Add edges based on diagram
add_edge_matrix("A", "B")
add_edge_matrix("B", "C")
add_edge_matrix("B", "D")
add_edge_matrix("D", "A")
add_edge_matrix("E", "C")

import java.util.HashMap;
import java.util.Map;

class GraphAdjacencyMatrix {
    private final String[] vertices = {"A", "B", "C", "D", "E"};
    private final Map<String, Integer> indexMap = new HashMap<>();
    private final int[][] adjacencyMatrix;

    public GraphAdjacencyMatrix() {
        for (int i = 0; i < vertices.length; i++) {
            indexMap.put(vertices[i], i);
        }

        // Initialize 2D adjacency matrix with 0s
        adjacencyMatrix = new int[vertices.length][vertices.length];
    }

    // Helper function to add a directed edge
    public void addEdgeMatrix(String from, String to) {
        Integer i = indexMap.get(from);
        Integer j = indexMap.get(to);

        if (i != null && j != null) {
            adjacencyMatrix[i][j] = 1; // use weights here if needed
        }
    }

    public int[][] getAdjacencyMatrix() {
        return adjacencyMatrix;
    }
}

#include<string>
#include<unordered_map>
#include<vector>
using namespace std;

class GraphAdjacencyMatrix {
private:
    vector<string> vertices = {"A", "B", "C", "D", "E"};
    unordered_map<string, int> indexMap;
    vector<vector<int>> adjacencyMatrix;

public:
    GraphAdjacencyMatrix() {
        for (int i = 0; i < static_cast<int>(vertices.size()); i++) {
            indexMap[vertices[i]] = i;
        }

        // Initialize 2D adjacency matrix with 0s
        adjacencyMatrix.assign(vertices.size(), vector<int>(vertices.size(), 0));
    }

    // Helper function to add a directed edge
    void addEdgeMatrix(const string& from, const string& to) {
        if (indexMap.find(from) == indexMap.end() || indexMap.find(to) == indexMap.end()) {
            return;
        }

        int i = indexMap[from];
        int j = indexMap[to];
        adjacencyMatrix[i][j] = 1; // use weights here if needed
    }

    const vector<vector<int>>& getAdjacencyMatrix() const {
        return adjacencyMatrix;
    }
};

#include<stdio.h>
#include<string.h>

#define MATRIX_SIZE5
#define MAX_NAME_LENGTH32

typedef struct {
    char vertices[MATRIX_SIZE][MAX_NAME_LENGTH];
    int adjacencyMatrix[MATRIX_SIZE][MATRIX_SIZE];
} GraphAdjacencyMatrix;

void initGraphAdjacencyMatrix(GraphAdjacencyMatrix* graph) {
    const char* names[MATRIX_SIZE] = {"A", "B", "C", "D", "E"};

    for (int i = 0; i < MATRIX_SIZE; i++) {
        strncpy(graph->vertices[i], names[i], MAX_NAME_LENGTH - 1);
        graph->vertices[i][MAX_NAME_LENGTH - 1] = '\0';

        for (int j = 0; j < MATRIX_SIZE; j++) {
            graph->adjacencyMatrix[i][j] = 0;
        }
    }
}

int findMatrixVertexIndex(GraphAdjacencyMatrix* graph, const char* name) {
    for (int i = 0; i < MATRIX_SIZE; i++) {
        if (strcmp(graph->vertices[i], name) == 0) {
            return i;
        }
    }
    return -1;
}

// Helper function to add a directed edge
void addEdgeMatrix(GraphAdjacencyMatrix* graph, const char* from, const char* to) {
    int i = findMatrixVertexIndex(graph, from);
    int j = findMatrixVertexIndex(graph, to);

    if (i != -1 && j != -1) {
        graph->adjacencyMatrix[i][j] = 1; // use weights here if needed
    }
}

// Directed Graph - Adjacency Matrix
const vertices: string[] = ['A', 'B', 'C', 'D', 'E'];
const indexMap: Record<string, number> = {
  A: 0,
  B: 1,
  C: 2,
  D: 3,
  E: 4
};

// Initialize 2D adjacency matrix with 0s
const adjacencyMatrix: number[][] = Array.from(
  { length: vertices.length },
  () => Array(vertices.length).fill(0)
);

// Helper function to add a directed edge
function addEdgeMatrix(from: string, to: string): void {
  const i = indexMap[from];
  const j = indexMap[to];

  if (i !== undefined && j !== undefined) {
    adjacencyMatrix[i][j] = 1; // use weights here if needed
  }
}

// Add edges based on diagram
addEdgeMatrix('A', 'B');
addEdgeMatrix('B', 'C');
addEdgeMatrix('B', 'D');
addEdgeMatrix('D', 'A');
addEdgeMatrix('E', 'C');

// Directed Graph - Adjacency Matrix
val vertices = listOf("A", "B", "C", "D", "E")

val indexMap = mapOf(
    "A" to 0,
    "B" to 1,
    "C" to 2,
    "D" to 3,
    "E" to 4
)

// Initialize 2D adjacency matrix with 0s
val adjacencyMatrix = Array(vertices.size) {
    IntArray(vertices.size)
}

// Helper function to add a directed edge
fun addEdgeMatrix(from: String, to: String) {
    val i = indexMap[from]
    val j = indexMap[to]

    if (i != null && j != null) {
        adjacencyMatrix[i][j] = 1 // use weights here if needed
    }
}

// Add edges based on diagram
addEdgeMatrix("A", "B")
addEdgeMatrix("B", "C")
addEdgeMatrix("B", "D")
addEdgeMatrix("D", "A")
addEdgeMatrix("E", "C")

// Directed Graph - Adjacency Matrix
let vertices = ["A", "B", "C", "D", "E"]
let indexMap: [String: Int] = [
    "A": 0,
    "B": 1,
    "C": 2,
    "D": 3,
    "E": 4
]

// Initialize 2D adjacency matrix with 0s
var adjacencyMatrix = Array(
    repeating: Array(repeating: 0, count: vertices.count),
    count: vertices.count
)

// Helper function to add a directed edge
func addEdgeMatrix(from: String, to: String) {
    guard let i = indexMap[from], let j = indexMap[to] else {
        return
    }

    adjacencyMatrix[i][j] = 1 // use weights here if needed
}

// Add edges based on diagram
addEdgeMatrix(from: "A", to: "B")
addEdgeMatrix(from: "B", to: "C")
addEdgeMatrix(from: "B", to: "D")
addEdgeMatrix(from: "D", to: "A")
addEdgeMatrix(from: "E", to: "C")

using System.Collections.Generic;

// Directed Graph - Adjacency Matrix
var vertices = new List<string> { "A", "B", "C", "D", "E" };

var indexMap = new Dictionary<string, int>
{
    ["A"] = 0,
    ["B"] = 1,
    ["C"] = 2,
    ["D"] = 3,
    ["E"] = 4
};

// Initialize 2D adjacency matrix with 0s
var adjacencyMatrix = new int[vertices.Count, vertices.Count];

// Helper function to add a directed edge
void AddEdgeMatrix(string from, string to)
{
    if (indexMap.TryGetValue(from, out int i) &&
        indexMap.TryGetValue(to, out int j))
    {
        adjacencyMatrix[i, j] = 1; // use weights here if needed
    }
}

// Add edges based on diagram
AddEdgeMatrix("A", "B");
AddEdgeMatrix("B", "C");
AddEdgeMatrix("B", "D");
AddEdgeMatrix("D", "A");
AddEdgeMatrix("E", "C");

// Directed Graph - Adjacency Matrix
var vertices = []string{"A", "B", "C", "D", "E"}
var indexMap = map[string]int{
    "A": 0,
    "B": 1,
    "C": 2,
    "D": 3,
    "E": 4,
}

// Initialize 2D adjacency matrix with 0s
func createAdjacencyMatrix(size int) [][]int {
    matrix := make([][]int, size)
    for i := range matrix {
        matrix[i] = make([]int, size)
    }
    return matrix
}

var adjacencyMatrix = createAdjacencyMatrix(len(vertices))

// Helper function to add a directed edge
func addEdgeMatrix(from string, to string) {
    i, fromExists := indexMap[from]
    j, toExists := indexMap[to]

    if fromExists && toExists {
        adjacencyMatrix[i][j] = 1 // use weights here if needed
    }
}

3. Edge List

An edge list represents a graph as a simple list of all its edges. Each edge is stored as a pair [u, v] (or triplet [u, v, weight] for weighted graphs), representing a connection from node u to node v.
Best for edge-centric algorithms like Kruskal’s Algorithm. It is memory-efficient, but checking whether a specific edge exists is slower than with an adjacency matrix. Memory usage: O(E)

// Weighted Directed Graph - Edge List
const edgeList = [
  ['A', 'B', 3],
  ['A', 'D', 2],
  ['B', 'D', 5],
  ['B', 'C', 1],
  ['E', 'C', 7]
];

// Add edge
function addEdgeEdgeList(list, u, v, w) {
  list.push([u, v, w]);
}

# Weighted Directed Graph - Edge List
edge_list: list[tuple[str, str, int]] = [
    ("A", "B", 3),
    ("A", "D", 2),
    ("B", "D", 5),
    ("B", "C", 1),
    ("E", "C", 7),
]

# Add edge
def add_edge_edge_list(edge_list: list[tuple[str, str, int]], u: str, v: str, w: int) -> None:
    edge_list.append((u, v, w))

import java.util.ArrayList;
import java.util.List;

class Edge {
    String from;
    String to;
    int weight;

    Edge(String from, String to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

class GraphEdgeList {
    private final List<Edge> edgeList;

    public GraphEdgeList() {
        edgeList = new ArrayList<>();
    }

    // Add edge
    public void addEdgeEdgeList(String u, String v, int w) {
        edgeList.add(new Edge(u, v, w));
    }

    public List<Edge> getEdgeList() {
        return edgeList;
    }
}

#include<string>
#include<vector>
using namespace std;

struct Edge {
    string from;
    string to;
    int weight;
};

class GraphEdgeList {
private:
    vector<Edge> edgeList;

public:
    // Add edge
    void addEdgeEdgeList(const string& u, const string& v, int w) {
        edgeList.push_back({u, v, w});
    }

    const vector<Edge>& getEdgeList() const {
        return edgeList;
    }
};

#include<stdio.h>
#include<string.h>

#define MAX_EDGES100
#define MAX_NAME_LENGTH32

typedef struct {
    char from[MAX_NAME_LENGTH];
    char to[MAX_NAME_LENGTH];
    int weight;
} Edge;

typedef struct {
    Edge edges[MAX_EDGES];
    int edgeCount;
} GraphEdgeList;

void initGraphEdgeList(GraphEdgeList* graph) {
    graph->edgeCount = 0;
}

// Add edge
void addEdgeEdgeList(GraphEdgeList* graph, const char* u, const char* v, int w) {
    if (graph->edgeCount >= MAX_EDGES) {
        return;
    }

    Edge* edge = &graph->edges[graph->edgeCount];
    strncpy(edge->from, u, MAX_NAME_LENGTH - 1);
    edge->from[MAX_NAME_LENGTH - 1] = '\0';

    strncpy(edge->to, v, MAX_NAME_LENGTH - 1);
    edge->to[MAX_NAME_LENGTH - 1] = '\0';

    edge->weight = w;
    graph->edgeCount++;

    // Add another edge from v to u only for undirected graph
}

// Weighted Directed Graph - Edge List
type Edge = [string, string, number];

const edgeList: Edge[] = [
  ['A', 'B', 3],
  ['A', 'D', 2],
  ['B', 'D', 5],
  ['B', 'C', 1],
  ['E', 'C', 7]
];

// Add edge
function addEdgeEdgeList(list: Edge[], u: string, v: string, w: number): void {
  list.push([u, v, w]);
}

// Weighted Directed Graph - Edge List
data class Edge(
    val from: String,
    val to: String,
    val weight: Int
)

val edgeList = mutableListOf(
    Edge("A", "B", 3),
    Edge("A", "D", 2),
    Edge("B", "D", 5),
    Edge("B", "C", 1),
    Edge("E", "C", 7)
)

// Add edge
fun addEdgeEdgeList(list: MutableList<Edge>, u: String, v: String, w: Int) {
    list.add(Edge(u, v, w))
    // list.add(Edge(v, u, w)) // only for undirected graph
}

// Weighted Directed Graph - Edge List
struct Edge {
    let from: String
    let to: String
    let weight: Int
}

var edgeList: [Edge] = [
    Edge(from: "A", to: "B", weight: 3),
    Edge(from: "A", to: "D", weight: 2),
    Edge(from: "B", to: "D", weight: 5),
    Edge(from: "B", to: "C", weight: 1),
    Edge(from: "E", to: "C", weight: 7)
]

// Add edge
func addEdgeEdgeList(_ list: inout [Edge], _ u: String, _ v: String, _ w: Int) {
    list.append(Edge(from: u, to: v, weight: w))
}

using System.Collections.Generic;

// Weighted Directed Graph - Edge List
public class Edge
{
    public string From { get; }
    public string To { get; }
    public int Weight { get; }

    public Edge(string from, string to, int weight)
    {
        From = from;
        To = to;
        Weight = weight;
    }
}

var edgeList = new List<Edge>
{
    new Edge("A", "B", 3),
    new Edge("A", "D", 2),
    new Edge("B", "D", 5),
    new Edge("B", "C", 1),
    new Edge("E", "C", 7)
};

// Add edge
void AddEdgeEdgeList(List<Edge> list, string u, string v, int w)
{
    list.Add(new Edge(u, v, w));
    // list.Add(new Edge(v, u, w)); // only for undirected graph
}

// Weighted Directed Graph - Edge List
type Edge struct {
    From   string
    To     string
    Weight int
}

var edgeList = []Edge{
    {From: "A", To: "B", Weight: 3},
    {From: "A", To: "D", Weight: 2},
    {From: "B", To: "D", Weight: 5},
    {From: "B", To: "C", Weight: 1},
    {From: "E", To: "C", Weight: 7},
}

// Add edge
func addEdgeEdgeList(list *[]Edge, u string, v string, w int) {
    *list = append(*list, Edge{From: u, To: v, Weight: w})
}

Representation Summary

Undirected - Unweighted Graph

Directed - Unweighted Graph

Undirected - Weighted Graph

Graph Traversal Techniques

Depth-First Search (DFS)
- DFS explores a graph by going as far down a path as possible, and only backtracks when it reaches a dead end. It dives into one branch deeply before trying the next one.
- Ideal for tasks like pathfinding, cycle detection
- Implemented using a stack (explicit or via recursion)
  - Start at a node.
  - Visit it and mark it as visited.
  - Recursively or iteratively explore one unvisited neighbor at a time.
  - Backtrack when no unvisited neighbors remain.

2. Breadth-First Search (BFS)

BFS explores the graph level-by-level, starting from a node and visiting all of its immediate neighbors before moving to the next level.

Use Cases:
- Finding the shortest path in unweighted graphs
- Level order traversal
- Social network friend suggestions (who's closest to you)

- Implemented using a queue
  - Start at a node.
  - Visit it and mark it as visited.
  - Add all its unvisited neighbors to a queue.
  - Continue processing the front of the queue until it’s empty.
  - ```
  // Starting from node A
  DFS: A → B → C → E → D   
  BFS: A → B → D → C → E
```

Graph Algorithms

Depth-First Search (DFS)

- Explores each path deeply before backtracking. Implemented using a stack (explicit or via recursion)

- Used in: cycle detection, finding connected components, and performing topological sort
Breadth-First Search (BFS)

- Explores nodes level-by-level, visiting all neighbors before going deeper. Implemented using a queue.

- Used in: Unweighted shortest path, graph coloring, connected components
Topological Sort

- A method for ordering nodes in a Directed Acyclic Graph (DAG) so that every prerequisite appears before the nodes that depend on it.

- Can be done with DFS (post-order) or BFS (Kahn’s Algorithm)

- Used in: Task scheduling, build systems, dependency resolution, directed cycle detection
Union-Find (Disjoint Set Union)

- A data structure used to efficiently track and merge disjoint groups (connected components) without needing explicit traversal.
  - Find(x): Gets the representative of x’s group
  - Union(x, y): Merges the groups containing x and y

- Used in: Kruskal’s MST, dynamic connectivity, undirected cycle detection
Shortest Path Algorithms

- Algorithms that calculate the least total cost or fewest steps needed to reach one node from another in a graph.

Algorithm	Best Used For
BFS	Shortest path in unweighted graphs
Dijkstra’s Algorithm	Shortest path in weighted graphs with no negative edge weights
Bellman-Ford Algorithm	Shortest path in weighted graphs that may contain negative edge weights
Floyd-Warshall Algorithm	All-pairs shortest paths, often useful for smaller or dense graphs
A*	Shortest path with a heuristic, commonly used in AI and pathfinding

Minimum Spanning Tree (MST)

- A Minimum Spanning Tree (MST) connects all nodes in a weighted, undirected graph with the minimum possible total edge weight, while using no cycles.

- Use in: Efficient infrastructure design (e.g., power grids, water pipes), network cabling, clustering problems.

Algorithm	Key Technique / Tool	Strategy
Kruskal’s	Union-Find (Disjoint Set Union)	Sorts all edges by weight and adds them greedily if they don’t form a cycle
Prim’s	Min-Heap (Priority Queue)	Grows the MST from any start node by picking the smallest edge to a new node

Use Cases

Real-Life	Description
Maps & Navigation	Cities and roads modeled as nodes and edges to find routes
Social Networks	Users as nodes, friendships/follows as edges
Web Crawling	Pages as nodes, hyperlinks as directed edges
Transportation	Airports or stations connected via routes or flight paths
Supply Chain	Warehouses and delivery centers connected by logistics routes
Utility Networks	Power, water, and internet infrastructure modeled as interconnected systems

Computer Science	Field	Description
Fraud Detection	Cybersecurity	Detect suspicious connections in financial transaction graphs
Compilation Order	Software Engineering	Topological sort ensures dependencies are compiled in correct sequence
Routing Protocols	Computer Networks	Use shortest path algorithms to route data efficiently
Game AI Navigation	Game Development	A* and Dijkstra’s used for smart movement and pathfinding
Graph Neural Networks	Machine Learning	Operate directly on structured graph data for predictions
PageRank Algorithm	Search Engines	Uses link structure (graph) to rank importance of web pages
Entity Relationship Models	Databases	Relationships between tables/entities form a graph-like structure

Core Algorithmic	Description	How DSA is Used
Shortest Path	Find lowest cost between two points	BFS, Dijkstra’s, Bellman-Ford, A*
Cycle Detection	Detect if a graph contains a loop	DFS, Topological Sort (directed), Union-Find (undirected)
Connectivity Check	Identify if nodes are reachable or part of same group	DFS, BFS, Union-Find
Topological Sorting	Linear ordering in DAG where tasks depend on each other	DFS post-order, Kahn’s Algorithm
Network Optimization	Connect all nodes with lowest cost (no cycles)	Kruskal’s, Prim’s (MST algorithms)
Clustering	Group similar nodes into subgraphs	DFS, Disjoint Set Union, K-means over graph structures
All-Pairs Pathfinding	Compute paths between every pair of nodes	Floyd-Warshall Algorithm