Data Structure in Dart – Graphs

1. What Is a Graph?

A Graph is a data structure consisting of:

Vertices (Nodes)
Edges (Connections between nodes)

A —— B
| \  |
C —— D

Graphs are used to model relationships, not just hierarchy.

Real-world examples

Social networks (users → friendships)
Maps & GPS (cities → roads)
Internet (routers → connections)
Flutter navigation flow
Recommendation systems

2. Types of Graphs

Based on Direction

Undirected Graph
A — B
Directed Graph (Digraph)
A → B

Based on Weight

Unweighted Graph
Weighted Graph (edges have cost/distance)

A --5--> B --2--> C

Other Classifications

Cyclic vs Acyclic
Connected vs Disconnected
Tree (special type of graph)

3. Graph Representations

1. Adjacency Matrix

    A B C
A [ 0 1 1 ]
B [ 1 0 1 ]
C [ 1 1 0 ]

List<List<int>> matrix = [
  [0, 1, 1],
  [1, 0, 1],
  [1, 1, 0],
];

Pros

Fast edge lookup O(1)

Cons

Uses more memory → O(V²)

2. Adjacency List (Most Common)

A → B, C
B → A, C
C → A, B

Map<int, List<int>> graph = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1],
};

Pros

Memory efficient
Easy traversal

4. Depth-First Search (DFS)

DFS explores as deep as possible before backtracking.

Start → A → B → D → back → C

DFS (Recursive)

void dfs(
  Map<int, List<int>> graph,
  int node,
  Set<int> visited,
) {
  if (visited.contains(node)) return;

  visited.add(node);
  print(node);

  for (var neighbor in graph[node]!) {
    dfs(graph, neighbor, visited);
  }
}

Usage

void main() {
  Map<int, List<int>> graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1],
  };

  dfs(graph, 0, {});
}

5. Breadth-First Search (BFS)

BFS explores level by level, using a queue.

Level 0 → A
Level 1 → B C
Level 2 → D E

BFS in Dart

import 'dart:collection';

void bfs(Map<int, List<int>> graph, int start) {
  Set<int> visited = {};
  Queue<int> queue = Queue();

  queue.add(start);
  visited.add(start);

  while (queue.isNotEmpty) {
    int node = queue.removeFirst();
    print(node);

    for (var neighbor in graph[node]!) {
      if (!visited.contains(neighbor)) {
        visited.add(neighbor);
        queue.add(neighbor);
      }
    }
  }
}

6. DFS vs BFS Comparison

Feature	DFS	BFS
Data Structure	Stack / Recursion	Queue
Memory	Lower (usually)	Higher
Finds shortest path	❌	✅
Use cases	Cycle detection	Level traversal

7. Cycle Detection

Undirected Graph (DFS)

bool hasCycle(
  Map<int, List<int>> graph,
  int node,
  int parent,
  Set<int> visited,
) {
  visited.add(node);

  for (var neighbor in graph[node]!) {
    if (!visited.contains(neighbor)) {
      if (hasCycle(graph, neighbor, node, visited)) return true;
    } else if (neighbor != parent) {
      return true;
    }
  }
  return false;
}

8. Connected Components

How many separate graphs exist?

int countComponents(Map<int, List<int>> graph) {
  Set<int> visited = {};
  int count = 0;

  for (var node in graph.keys) {
    if (!visited.contains(node)) {
      dfs(graph, node, visited);
      count++;
    }
  }
  return count;
}

9. Shortest Path – Dijkstra Algorithm

Used in:

Google Maps
GPS navigation
Network routing

Weighted Graph

Map<int, List<MapEntry<int, int>>> graph = {
  0: [MapEntry(1, 4), MapEntry(2, 1)],
  1: [MapEntry(3, 1)],
  2: [MapEntry(1, 2), MapEntry(3, 5)],
  3: [],
};

Dijkstra (Simplified)

import 'dart:collection';

Map<int, int> dijkstra(
  Map<int, List<MapEntry<int, int>>> graph,
  int start,
) {
  final distances = <int, int>{};
  final pq = PriorityQueue<MapEntry<int, int>>(
    (a, b) => a.value.compareTo(b.value),
  );

  for (var node in graph.keys) {
    distances[node] = double.maxFinite.toInt();
  }

  distances[start] = 0;
  pq.add(MapEntry(start, 0));

  while (pq.isNotEmpty) {
    var current = pq.removeFirst();
    int node = current.key;

    for (var edge in graph[node]!) {
      int newDist = distances[node]! + edge.value;
      if (newDist < distances[edge.key]!) {
        distances[edge.key] = newDist;
        pq.add(MapEntry(edge.key, newDist));
      }
    }
  }
  return distances;
}

10. Flutter Real-World Use Case

Navigation Graph

Each screen = node
Each route = edge

Home → Profile → Settings
   ↘ Cart → Checkout