克鲁斯卡尔

选一种语言就能看到代码

def find(parent, room):
    while parent[room] != room:
        parent[room] = parent[parent[room]]
        room = parent[room]
    return room


def kruskal_maze(w, h, rng):
    links = [0] * (w * h)
    parent = list(range(w * h))
    edges = [(room, d) for room in range(w * h) for d in (1, 2)
             if neighbor(room, d) >= 0]
    rng.shuffle(edges)
    for room, d in edges:
        other = neighbor(room, d)
        a, b = find(parent, room), find(parent, other)
        if a == b:
            continue
        parent[a] = b
        carve(links, room, other, d)
    return links

function find(parent, room) {
  while (parent[room] !== room) {
    parent[room] = parent[parent[room]];
    room = parent[room];
  }
  return room;
}

function kruskalMaze(w, h, rng) {
  const links = new Array(w * h).fill(0);
  const parent = Array.from({ length: w * h }, (_, i) => i);
  const edges = [];
  for (let room = 0; room < w * h; room++) {
    for (const d of [1, 2]) {
      if (neighbor(room, d) >= 0) edges.push([room, d]);
    }
  }
  rng.shuffle(edges);
  for (const [room, d] of edges) {
    const other = neighbor(room, d);
    const a = find(parent, room);
    const b = find(parent, other);
    if (a === b) continue;
    parent[a] = b;
    carve(links, room, other, d);
  }
  return links;
}

static int find(int parent[], int room) {
    while (parent[room] != room) {
        parent[room] = parent[parent[room]];
        room = parent[room];
    }
    return room;
}

void kruskal_maze(int links[], int w, int h) {
    int n = w * h;
    int* parent = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) parent[i] = i;

    int* edges = malloc(sizeof(int) * n * 2);
    int count = 0;
    for (int room = 0; room < n; room++) {
        if (neighbor(room, 1) >= 0) edges[count++] = room * 4 + 1;
        if (neighbor(room, 2) >= 0) edges[count++] = room * 4 + 2;
    }
    shuffle(edges, count);
    for (int i = 0; i < count; i++) {
        int room = edges[i] / 4, d = edges[i] % 4;
        int other = neighbor(room, d);
        int a = find(parent, room), b = find(parent, other);
        if (a == b) continue;
        parent[a] = b;
        carve(links, room, other, d);
    }
    free(parent);
    free(edges);
}

static int find(std::vector<int>& parent, int room) {
    while (parent[room] != room) {
        parent[room] = parent[parent[room]];
        room = parent[room];
    }
    return room;
}

void kruskal_maze(std::vector<int>& links, int w, int h, std::mt19937& rng) {
    int n = w * h;
    std::vector<int> parent(n);
    std::iota(parent.begin(), parent.end(), 0);

    std::vector<std::pair<int, int>> edges;
    for (int room = 0; room < n; room++) {
        for (int d : {1, 2}) {
            if (neighbor(room, d) >= 0) edges.push_back({room, d});
        }
    }
    std::shuffle(edges.begin(), edges.end(), rng);
    for (auto [room, d] : edges) {
        int other = neighbor(room, d);
        int a = find(parent, room), b = find(parent, other);
        if (a == b) continue;
        parent[a] = b;
        carve(links, room, other, d);
    }
}

static int Find(int[] parent, int room) {
    while (parent[room] != room) {
        parent[room] = parent[parent[room]];
        room = parent[room];
    }
    return room;
}

static int[] KruskalMaze(int w, int h, Random rng) {
    int n = w * h;
    int[] links = new int[n];
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    var edges = new List<(int Room, int Dir)>();
    for (int room = 0; room < n; room++) {
        foreach (int d in new[] { 1, 2 }) {
            if (Neighbor(room, d) >= 0) edges.Add((room, d));
        }
    }
    Shuffle(edges, rng);
    foreach (var (room, dir) in edges) {
        int other = Neighbor(room, dir);
        int a = Find(parent, room), b = Find(parent, other);
        if (a == b) continue;
        parent[a] = b;
        Carve(links, room, other, dir);
    }
    return links;
}

static int find(int[] parent, int room) {
    while (parent[room] != room) {
        parent[room] = parent[parent[room]];
        room = parent[room];
    }
    return room;
}

static int[] kruskalMaze(int w, int h, Random rng) {
    int n = w * h;
    int[] links = new int[n];
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    List<int[]> edges = new ArrayList<>();
    for (int room = 0; room < n; room++) {
        for (int d : new int[] {1, 2}) {
            if (neighbor(room, d) >= 0) edges.add(new int[] {room, d});
        }
    }
    Collections.shuffle(edges, rng);
    for (int[] edge : edges) {
        int other = neighbor(edge[0], edge[1]);
        int a = find(parent, edge[0]), b = find(parent, other);
        if (a == b) continue;
        parent[a] = b;
        carve(links, edge[0], other, edge[1]);
    }
    return links;
}