2021-1 从文件构建图 加权有向边 加权有向图的构建 邻接表 c++

图构造对比

• 加权无向图
• 无权有向图
• 无权无向图
• 加权有向图[本文]

API

1 有向边的类

2 加权有向图

测试图

实现

1 有向边类

#pragma once
#include<iostream>using namespace std;#define out(x) cout<<x<<" "
#define hh printf_s("\n")string intToStr(int n);
string doubleToStr(double d);class DirectedEdge
{
    
public:DirectedEdge(int v, int w, double weight);double weight();int from();int to();string toString();private:int m_from=0;int m_to=0;double m_weight = 0.0;};void test_DirectedEdge();

#include "DirectedEdge.h"string intToStr(int n)
{
    char int_s[20] = {
     0 };//末尾加上'\0'_itoa_s(n, int_s, 10);// 10 表示十进制return string(int_s);
}string doubleToStr(double x) {
    char double_str[100] = {
     0 };sprintf_s(double_str, "%.2f", x);//保留两位有效小数return string(double_str);
}DirectedEdge::DirectedEdge(int v, int w, double weight):m_from(v),m_to(w),m_weight(weight){
    }double DirectedEdge::weight()
{
    return m_weight;
}int DirectedEdge::from()
{
    return m_from;
}int DirectedEdge::to()
{
    return m_to;
}string DirectedEdge::toString()
{
    string ans = "";ans += intToStr(m_from) + "->" + intToStr(m_to) + " " + doubleToStr(m_weight);return ans;
}void test_DirectedEdge()
{
    DirectedEdge e(2, 3, 0.98);out(e.toString()), hh;
}/* int main() {test_DirectedEdge();system("pause");return 0; } */

2 加权有向图

#pragma once
#include<vector>
#include<list>
#include<fstream>
#include"DirectedEdge.h"class EdgeWeigthDigraph
{
    
public:EdgeWeigthDigraph(int V);EdgeWeigthDigraph(string file);int V() {
     return m_V; }int E() {
     return m_E; }void addEdge(DirectedEdge e);list<DirectedEdge>* adj(int v) {
     return m_adj->at(v); }list<DirectedEdge>* edges();string toString();
private:int m_V=0;int m_E=0;vector<list<DirectedEdge>*>* m_adj = nullptr;
};void test_EdgeWeigthDigraph();

#include "EdgeWeigthDigraph.h"EdgeWeigthDigraph::EdgeWeigthDigraph(int V):m_V(0),m_E(0)
{
    m_adj = new vector<list<DirectedEdge>*>(V);for (int i = 0; i < V; ++i) {
    //具体开辟空间代替空指针m_adj->at(i) = new list<DirectedEdge>();}
}EdgeWeigthDigraph::EdgeWeigthDigraph(string file)
{
    ifstream in(file, ios::in);if (!in) {
    out("open file error!\n");return;}int V, E;in >> V;m_adj = new vector<list<DirectedEdge>*>(V);for (int i = 0; i < V; ++i) {
    m_adj->at(i) = new list<DirectedEdge>();}m_V = V;in >> E;for (int i = 0; i < E; ++i) {
    int v, w; double wei = 0.0;in >> v >> w >> wei;addEdge(DirectedEdge(v, w, wei));}in.close();
}void EdgeWeigthDigraph::addEdge(DirectedEdge e)
{
    //这里可以添加平行边自环的判断m_adj->at(e.from())->push_front(e);++m_E;
}list<DirectedEdge>* EdgeWeigthDigraph::edges()
{
    list<DirectedEdge>* edges = new list<DirectedEdge>();for (int v = 0; v < m_V; ++v) {
    for (auto& e : *m_adj->at(v)) {
    edges->push_front(e);}}return edges;
}string EdgeWeigthDigraph::toString()
{
    string s = intToStr(m_V) + " vertices, " + intToStr(m_E) + " edges\n\n";for (int i = 0; i < m_V; i++){
    s += intToStr(i) + ": ";for (auto edge : *(m_adj->at(i))){
    s += edge.toString() + " ";}s += "\n";}return s;
}void test_EdgeWeigthDigraph()
{
    EdgeWeigthDigraph G("tinyEWD.txt");out(G.toString()), hh;
}int main() {
    test_EdgeWeigthDigraph();system("pause");return 0;
}

3 tinyEWD.txt

8
15
4 5 0.35
5 4 0.35
4 7 0.37
5 7 0.28
7 5 0.28
5 1 0.32
0 4 0.38
0 2 0.26
7 3 0.39
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93

运行