C++从TXT文件读取图输入替代手动插入边的实现方法

要替换手动调用insertEdge的逻辑，改用TXT文件输入构建图，只需修改main函数，利用C++标准库的ifstream实现文件读取即可，步骤如下：

1. 打开目标文件并验证：使用ifstream打开指定路径的TXT文件，若打开失败则输出提示并退出。
2. 读取顶点数：读取文件第一行的顶点总数V，用来初始化Graph对象。
3. 循环读取边数据：依次读取后续每行的三个整数（起点u、终点v、权重wt），调用insertEdge插入到图中。

修改后的完整代码 #

#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f

// creating a struct for an edge
struct Edge
{
    int u, v, wt;
};

class Graph
{
    int V;
    // adjacency list
    list < pair <int, int > >*adjacency;

    vector < Edge > edges;

    public :
    Graph( int V )
    {
        this->V = V ;
        adjacency = new list < pair <int, int > >[V];
    }

    // declaring all the functions
    // inserting an edge
    void insertEdge ( int u, int v, int w );

    // deleting an edge
    void deleteEdge( int u, int v, int w );

    // finding minimum path
    int minimumPath (int u, int v );

    // deleting an edge
    void deleteEdge( int u, int v );

    // finding min cycles
    int FindMinCycle();

};

// inserting an edge
void Graph :: insertEdge ( int u, int v, int w )
{
    adjacency[u].push_back( make_pair( v, w ));
    adjacency[v].push_back( make_pair( u, w ));

    Edge e = { u, v, w };
    edges.push_back ( e );
}

// deleting an edge
void Graph :: deleteEdge( int u, int v, int w )
{
    adjacency[u].remove(make_pair( v, w ));
    adjacency[v].remove(make_pair(u, w ));
}

// finding minimum path function
int Graph :: minimumPath ( int u, int v )
{
    // storing vertices
    set< pair<int, int> > setds;

    // vector for distances
    vector<int> dist(V, INF);

    /* insert self source at first and initialize its distance as 0 */ 
    setds.insert(make_pair(0, u));
    dist[u] = 0;

    while (!setds.empty())
    {
/* The first vertex in Set is the one with the shortest distance; remove it from Set. */
        pair<int, int> tmp = *(setds.begin());
        setds.erase(setds.begin());

/* To preserve the vertices sorted distance, vertex label must be put in second of pair (distance must be first item in pair) */
        int u = tmp.second;
        list< pair<int, int> >::iterator i;
        for (i = adjacency[u].begin(); i != adjacency[u].end(); ++i)
        {
            int v = (*i).first;
            int weight = (*i).second;

            if (dist[v] > dist[u] + weight)
            {
/* If the distance of v is not INF, then it must be in our set; therefore, it should be removed and reinserted with an updated shorter distance. We only remove from Set the vertices for which the distance has been determined. Therefore, they would never see us arrive here. */
                if (dist[v] != INF)
                setds.erase(setds.find(make_pair(dist[v], v)));
                dist[v] = dist[u] + weight;
                setds.insert(make_pair(dist[v], v));
            }
        }
    }

    return dist[v] ;
}

// finding minimum path function
int Graph :: FindMinCycle ( )
{
    int min_cycle = INT_MAX;
    int E = edges.size();
    for ( int i = 0 ; i < E ; i++ )
    {
        Edge e = edges[i];
/* Obtain the edge vertices that we currently delete from the graph, and then use Dijkstra's shortest path technique to discover the shortest path between these two vertices. */
        deleteEdge( e.u, e.v, e.wt ) ;

        int dist = minimumPath( e.u, e.v );

/* If this is the shortest cycle, update min cycle; otherwise, add weight to currently deleted edges to create a cycle. */
        min_cycle = min(min_cycle, dist + e.wt);

        // add current edge back to the graph
        insertEdge( e.u, e.v, e.wt );
    }

    return min_cycle ;
}

int main()
{
    // 替换为你的TXT文件路径，同目录下直接写文件名，否则写绝对路径
    ifstream infile("graph_input.txt");
    if (!infile.is_open()) {
        cerr << "无法打开文件，请检查路径是否正确！" << endl;
        return 1;
    }

    int V;
    infile >> V;
    Graph g(V);

    int u, v, wt;
    // 循环读取所有边数据
    while (infile >> u >> v >> wt) {
        g.insertEdge(u, v, wt);
    }

    // 关闭文件
    infile.close();

    cout << "Minimum weight cycle in the graph is: "<<g.FindMinCycle() << endl;
    return 0;
}

注意事项 #

• 确保TXT文件格式与示例一致：第一行是顶点数，后续每行是三个整数表示一条无向边的起点、终点和权重。
• 文件路径：如果输入文件和编译后的程序在同一目录下，直接写文件名即可；否则需要填写完整的绝对路径（比如"C:/data/graph_input.txt"）。

内容的提问来源于stack exchange，提问作者Freddy Chiu