Prim算法

#define _CRT_SECURE_NO_WARNINGS
#include <queue>
#include <set>
#include <string>
#include <vector>
#include<map>

using namespace std;
void read_directed_graph(FILE* fptr,
    map<int, vector<pair<int, int>>>& adj_list)
{
    int node_cnt;
    fscanf_s(fptr, "%d", &node_cnt);
    for (int i = 0; i < node_cnt; i++)
    {
        int node;
        fscanf_s(fptr, "%d", &node);
        vector<pair<int, int>> empty;
        adj_list[node] = empty;
    }

    int edge_cnt;
    fscanf_s(fptr, "%d", &edge_cnt);
    for (int i = 0; i < edge_cnt; i++)
    {
        int start;
        int end;
        int weight;
        fscanf_s(fptr, "%d%d%d", &start, &end, &weight);
        adj_list[start].push_back({ end, weight });
    }
}

void read_undirected_graph(FILE* fptr,
    map<int, vector<pair<int, int>>>& adj_list)
{
    int node_cnt;
    fscanf_s(fptr, "%d", &node_cnt);
    for (int i = 0; i < node_cnt; i++)
    {
        int node;
        fscanf_s(fptr, "%d", &node);
        vector<pair<int, int>> empty;
        adj_list[node] = empty;
    }

    int edge_cnt;
    fscanf_s(fptr, "%d", &edge_cnt);
    for (int i = 0; i < edge_cnt; i++)
    {
        int start;
        int end;
        int weight;
        fscanf_s(fptr, "%d%d%d", &start, &end, &weight);
        adj_list[start].push_back({ end, weight });
        adj_list[end].push_back({ start, weight });
    }
}

#include "util.hpp"
#include "disjoint-set.hpp"
using namespace std;

struct Edge
{
    int start;
    int end;
    int weight;
    friend bool operator < (Edge e1, Edge e2)
    {
        return e1.weight > e2.weight;
    }
};

int main()
{
    map<int, vector<pair<int, int>>> adj_list;
    std::string input_file = "input.txt";
    FILE* fptr = fopen(input_file.c_str(), "r");
    read_undirected_graph(fptr, adj_list);
    fclose(fptr);

    priority_queue<Edge> edge_pq;
    set<int> node_set;
    vector<Edge> edge_vec;

    auto it = adj_list.begin();
    int start_node = it->first;
    node_set.insert(start_node);
    for (auto& entry : it->second)
    {
        edge_pq.push({ start_node, entry.first, entry.second });
    }

    while (edge_vec.size() < adj_list.size() - 1)
    {
        Edge cur = edge_pq.top();
        edge_pq.pop();
        int start_node = cur.end;
        if (node_set.find(start_node) != node_set.end())
        {
            continue;
        }

        for (auto entry : adj_list[start_node])
        {
            int end_node = entry.first;
            edge_pq.push({ start_node,  end_node, entry.second });
            if (node_set.find(end_node) != node_set.end())
            {
                continue;
            }

        }

        edge_vec.push_back(cur);
        node_set.insert(start_node);
    }
    return 0;
}

7
1
2
3
4
5
6
7
12
1   2   2 
1   4   1
2   4   3
2   5   10
3   1   4
3   6   5
4   3   2
4   6   8
4   7   4
4   5   7
5   7   6
7   6   1