Everything is connected.
Not everything is a tree.

use std::collections::{VecDeque, BinaryHeap, HashSet, HashMap};
use std::cmp::Reverse;

// BFS: shortest path in unweighted graph.
// Returns the visited order from start node.
fn bfs(graph: &Graph, start: u32) -> Vec<u32> {
    let mut visited = HashSet::new();
    let mut queue   = VecDeque::new();
    let mut order   = Vec::new();

    visited.insert(start);
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &(neighbour, _weight) in graph.neighbours(node) {
            if !visited.contains(&neighbour) {
                visited.insert(neighbour);
                queue.push_back(neighbour);
                // queue: FIFO ensures level-by-level
                // the stacks and queues page built this
            }
        }
    }
    order
}

// DFS: iterative using an explicit stack.
// Recursive DFS uses the call stack instead.
fn dfs(graph: &Graph, start: u32) -> Vec<u32> {
    let mut visited = HashSet::new();
    let mut stack   = Vec::new(); // Vec as stack
    let mut order   = Vec::new();

    stack.push(start);

    while let Some(node) = stack.pop() {
        if visited.contains(&node) { continue; }
        visited.insert(node);
        order.push(node);

        for &(neighbour, _weight) in graph.neighbours(node) {
            if !visited.contains(&neighbour) {
                stack.push(neighbour);
                // stack: LIFO gives depth-first behaviour
            }
        }
    }
    order
}

// Dijkstra: shortest path in weighted graph.
// Returns distance to every reachable node.
fn dijkstra(graph: &Graph, start: u32)
    -> HashMap<u32, u32>
{
    // BinaryHeap: min-heap using Reverse wrapper.
    // Holds (cost, node) pairs; tuples compare by
    // cost first, so the cheapest node pops first.
    let mut heap: BinaryHeap<Reverse<(u32, u32)>> =
        BinaryHeap::new();
    let mut dist: HashMap<u32, u32> = HashMap::new();

    dist.insert(start, 0);
    heap.push(Reverse((0, start)));

    while let Some(Reverse((cost, node))) = heap.pop() {
        // skip if we found a better path already
        if cost > *dist.get(&node).unwrap_or(&u32::MAX) {
            continue;
        }
        for &(neighbour, weight) in graph.neighbours(node) {
            let new_cost = cost + weight;
            let best = dist.entry(neighbour)
                           .or_insert(u32::MAX);
            if new_cost < *best {
                *best = new_cost;
                heap.push(Reverse((new_cost, neighbour)));
                // priority queue picks lowest cost next
                // same BinaryHeap as the mempool priority queue
            }
        }
    }
    dist
}

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

#define INF UINT32_MAX

/*
 * BFS in C: iterative with a queue array.
 * queue[]: plain array. each node enters at most
 * once, so capacity n is always enough.
 * visited[]: boolean array indexed by node id.
 */
void bfs(const Graph *g, uint32_t start,
         uint32_t *order, uint32_t *order_len) {
    uint8_t  *visited = calloc(g->n, 1);
    uint32_t *queue   = malloc(g->n * sizeof *queue);
    uint32_t  head = 0, tail = 0;
    *order_len = 0;

    visited[start] = 1;
    queue[tail++]  = start;

    while (head < tail) {
        uint32_t node   = queue[head++];
        order[(*order_len)++] = node;
        for (Edge *e = g->heads[node]; e; e = e->next) {
            if (!visited[e->to]) {
                visited[e->to] = 1;
                queue[tail++]  = e->to;
            }
        }
    }
    free(visited);
    free(queue);
}

/*
 * Dijkstra in C: simple O(V^2) version.
 * For sparse graphs use a min-heap.
 * This version scans all nodes for the minimum.
 * Clear. Correct. O(V^2 + E).
 */
void dijkstra(const Graph *g, uint32_t start,
              uint32_t *dist) {
    uint8_t *done = calloc(g->n, 1);

    for (uint32_t i = 0; i < g->n; i++)
        dist[i] = INF;
    dist[start] = 0;

    for (uint32_t iter = 0; iter < g->n; iter++) {
        /* find unvisited node with minimum distance */
        uint32_t u = g->n;
        for (uint32_t i = 0; i < g->n; i++)
            if (!done[i] && (u == g->n || dist[i] < dist[u]))
                u = i;
        if (u == g->n || dist[u] == INF) break;
        done[u] = 1;

        /* relax edges from u */
        for (Edge *e = g->heads[u]; e; e = e->next) {
            if (dist[u] + e->weight < dist[e->to])
                dist[e->to] = dist[u] + e->weight;
        }
    }
    free(done);
    /* dist[i] = shortest path cost from start to i */
    /* INF means unreachable */
}