Kruskal算法用链表判断回路C++实现不使用vector

Kruskal算法是一种用于求解最小生成树的经典算法，其中需要使用到判断回路的操作。使用链表来实现判断回路的话，可以按照以下步骤来进行：

1. 定义一个结构体Edge来表示图中的边，其中包括起点、终点和权值三个元素。

struct Edge {
    int start, end, weight;
};

2. 定义一个链表节点结构体Node，其中包括Edge类型的数据成员和指向下一个节点的指针。

struct Node {
    Edge data;
    Node* next;
};

3. 定义一个链表类LinkedList，其中包括头节点指针和尾节点指针两个数据成员，以及插入节点和查找节点的方法。

class LinkedList {
private:
    Node* head;
    Node* tail;

public:
    LinkedList() {
        head = nullptr;
        tail = nullptr;
    }

    void insert(Edge edge) {
        Node* node = new Node();
        node->data = edge;
        node->next = nullptr;
        if (head == nullptr) {
            head = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
    }

    bool find(int start, int end) {
        Node* node = head;
        while (node != nullptr) {
            if (node->data.start == start && node->data.end == end) {
                return true;
            }
            node = node->next;
        }
        return false;
    }
};

4. 在Kruskal算法中，每次选取权值最小的边时，需要判断这条边是否会形成回路。可以定义一个并查集来实现这个判断过程，同时使用链表来记录已经选择过的边。

int findRoot(int i, int* parent) {
    while (parent[i] != i) {
        i = parent[i];
    }
    return i;
}

void kruskal(Edge* edges, int n) {
    int* parent = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }

    LinkedList selectedEdges;

    for (int i = 0; i < n; i++) {
        Edge edge = edges[i];
        int start = edge.start;
        int end = edge.end;
        int root1 = findRoot(start, parent);
        int root2 = findRoot(end, parent);
        if (root1 != root2) {
            parent[root2] = root1;
            selectedEdges.insert(edge);
        } else {
            if (!selectedEdges.find(start, end)) {
                std::cout << "There is a loop!" << std::endl;
            }
        }
    }

    delete[] parent;
}

以上就是使用链表来判断回路的Kruskal算法的C++实现，希望能对你有所帮助。