Graph examples

These examples store an undirected graph as an adjacency list, add connections, and visit the graph with breadth-first search.

Python

from collections import deque


class Graph:
    def __init__(self):
        self.adjacency = {}

    def add_connection(self, left, right):
        self.adjacency.setdefault(left, [])
        self.adjacency.setdefault(right, [])
        if right not in self.adjacency[left]:
            self.adjacency[left].append(right)
        if left not in self.adjacency[right]:
            self.adjacency[right].append(left)

    def breadth_first(self, start):
        if start not in self.adjacency:
            return []

        visited = {start}
        queue = deque([start])
        order = []
        while queue:
            current = queue.popleft()
            order.append(current)
            for neighbor in self.adjacency[current]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        return order


def print_label_value(label, value):
    print(f"\033[1;36m{label}:\033[0m {value}")


graph = Graph()
connections = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "E"), ("D", "F"), ("E", "F")]

for index, (left, right) in enumerate(connections, start=1):
    graph.add_connection(left, right)
    print_label_value(f"{index}. Add connection {left}-{right}", "connected")

print_label_value("7. Breadth-first traversal from A", " -> ".join(graph.breadth_first("A")))

JavaScript

class Graph {
  constructor() {
    this.adjacency = new Map();
  }

  addConnection(left, right) {
    if (!this.adjacency.has(left)) {
      this.adjacency.set(left, []);
    }
    if (!this.adjacency.has(right)) {
      this.adjacency.set(right, []);
    }

    const leftNeighbors = this.adjacency.get(left);
    const rightNeighbors = this.adjacency.get(right);
    if (!leftNeighbors.includes(right)) {
      leftNeighbors.push(right);
    }
    if (!rightNeighbors.includes(left)) {
      rightNeighbors.push(left);
    }
  }

  breadthFirst(start) {
    if (!this.adjacency.has(start)) {
      return [];
    }

    const visited = new Set([start]);
    const queue = [start];
    const order = [];
    let front = 0;

    while (front < queue.length) {
      const current = queue[front];
      front += 1;
      order.push(current);

      for (const neighbor of this.adjacency.get(current)) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    return order;
  }
}

function printLabelValue(label, value) {
  console.log(`\x1b[1;36m${label}:\x1b[0m`, value);
}

const graph = new Graph();
const connections = [
  ["A", "B"],
  ["A", "C"],
  ["B", "D"],
  ["C", "E"],
  ["D", "F"],
  ["E", "F"],
];

connections.forEach(([left, right], index) => {
  graph.addConnection(left, right);
  printLabelValue(`${index + 1}. Add connection ${left}-${right}`, "connected");
});

printLabelValue(
  "7. Breadth-first traversal from A",
  graph.breadthFirst("A").join(" -> "),
);

Expected output

1. Add connection A-B: connected
2. Add connection A-C: connected
3. Add connection B-D: connected
4. Add connection C-E: connected
5. Add connection D-F: connected
6. Add connection E-F: connected
7. Breadth-first traversal from A: A -> B -> C -> D -> E -> F