0.x 15.图论基础-有权图表示

dddd数据结构课本

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

有权图的表示

边的表示和图信息的读取

#include <iostream>
#include <cassert>
using namespace std;
// 边
template<typename Weight>
class Edge{
private:
    int a,b;    // 边的两个端点
    Weight weight;  // 边的权值
public:
    // 构造函数
    Edge(int a, int b, Weight weight){
        this->a = a;
        this->b = b;
        this->weight = weight;
    }
    // 空的构造函数, 所有的成员变量都取默认值
    Edge(){}
    ~Edge(){}
    int v(){ return a;} // 返回第一个顶点
    int w(){ return b;} // 返回第二个顶点
    Weight wt(){ return weight;}    // 返回权值
    // 给定一个顶点, 返回另一个顶点
    int other(int x){
        assert( x == a || x == b );
        return x == a ? b : a;
    }
    // 输出边的信息
    friend ostream& operator<<(ostream &os, const Edge &e){
        os<<e.a<<"-"<<e.b<<": "<<e.weight;
        return os;
    }
    // 边的大小比较, 是对边的权值的大小比较
    bool operator<(Edge<Weight>& e){
        return weight < e.wt();
    }
    bool operator<=(Edge<Weight>& e){
        return weight <= e.wt();
    }
    bool operator>(Edge<Weight>& e){
        return weight > e.wt();
    }
    bool operator>=(Edge<Weight>& e){
        return weight >= e.wt();
    }
    bool operator==(Edge<Weight>& e){
        return weight == e.wt();
    }
};

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <cassert>
using namespace std;
// 读取有权图
template <typename Graph, typename Weight>
class ReadGraph{
public:
    // 从文件filename中读取有权图的信息, 存储进图graph中
    ReadGraph(Graph &graph, const string &filename){
        ifstream file(filename);
        string line;
        int V, E;
        assert(file.is_open());
        // 第一行读取图中的节点个数和边的个数
        assert( getline(file,line));
        stringstream ss(line);
        ss >> V >> E;
        assert( graph.V() == V );
        // 读取每一条边的信息
        for( int i = 0 ; i < E ; i ++ ){
            assert( getline(file,line));
            stringstream ss(line);
            int a, b;
            Weight w;
            ss>>a>>b>>w;
            assert( a >= 0 && a < V );
            assert( b >= 0 && b < V );
            graph.addEdge(a, b, w);
        }
    }
};

邻接矩阵

#include <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
using namespace std;
// 稠密图 - 邻接矩阵
template <typename Weight>
class DenseGraph{
private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图
    vector<vector<Edge<Weight> *>> g;   // 图的具体数据
public:
    // 构造函数
    DenseGraph( int n , bool directed){
        assert( n >= 0 );
        this->n = n;
        this->m = 0;
        this->directed = directed;
        // g初始化为n*n的矩阵, 每一个g[i][j]指向一个边的信息, 初始化为NULL
        g = vector<vector<Edge<Weight> *>>(n, vector<Edge<Weight> *>(n, NULL));
    }
    // 析构函数
    ~DenseGraph(){
        for( int i = 0 ; i < n ; i ++ )
            for( int j = 0 ; j < n ; j ++ )
                if( g[i][j] != NULL )
                    delete g[i][j];
    }
    int V(){ return n;} // 返回节点个数
    int E(){ return m;} // 返回边的个数
    // 向图中添加一个边, 权值为weight
    void addEdge( int v, int w , Weight weight ){
        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );
        // 如果从v到w已经有边, 删除这条边
        if( hasEdge( v , w  ) ){
            delete  g[v][w];
            if( v != w && !directed )
                delete g[w][v];
            m --;
        }
        g[v][w] = new Edge<Weight>(v, w, weight);
        if( v != w && !directed )
            g[w][v] = new Edge<Weight>(w, v, weight);
        m ++;
    }
    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){
        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );
        return g[v][w] != NULL;
    }
    // 显示图的信息
    void show(){
        for( int i = 0 ; i < n ; i ++ ){
            for( int j = 0 ; j < n ; j ++ )
                if( g[i][j] )
                    cout<<g[i][j]->wt()<<"\t";
                else
                    cout<<"NULL\t";
            cout<<endl;
        }
    }
    // 邻边迭代器, 传入一个图和一个顶点,
    // 迭代在这个图中和这个顶点向连的所有边
    class adjIterator{
    private:
        DenseGraph &G;  // 图G的引用
        int v;
        int index;
    public:
        // 构造函数
        adjIterator(DenseGraph &graph, int v): G(graph){
            this->v = v;
            this->index = -1;   // 索引从-1开始, 因为每次遍历都需要调用一次next()
        }
        ~adjIterator(){}
        // 返回图G中与顶点v相连接的第一个边
        Edge<Weight>* begin(){
            // 索引从-1开始, 因为每次遍历都需要调用一次next()
            index = -1;
            return next();
        }
        // 返回图G中与顶点v相连接的下一个边
        Edge<Weight>* next(){
            // 从当前index开始向后搜索, 直到找到一个g[v][index]为true
            for( index += 1 ; index < G.V() ; index ++ )
                if( G.g[v][index] )
                    return G.g[v][index];
            // 若没有顶点和v相连接, 则返回NULL
            return NULL;
        }
        // 查看是否已经迭代完了图G中与顶点v相连接的所有边
        bool end(){
            return index >= G.V();
        }
    };
};

邻接表

#include <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
using namespace std;
// 稀疏图 - 邻接表
template<typename Weight>
class SparseGraph{
private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图
    vector<vector<Edge<Weight> *> > g;   // 图的具体数据
public:
    // 构造函数
    SparseGraph( int n , bool directed){
        assert(n >= 0);
        this->n = n;
        this->m = 0;    // 初始化没有任何边
        this->directed = directed;
        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        g = vector<vector<Edge<Weight> *> >(n, vector<Edge<Weight> *>());
    }
    // 析构函数
    ~SparseGraph(){
        for( int i = 0 ; i < n ; i ++ )
            for( int j = 0 ; j < g[i].size() ; j ++ )
                delete g[i][j];
    }
    int V(){ return n;} // 返回节点个数
    int E(){ return m;} // 返回边的个数
    // 向图中添加一个边, 权值为weight
    void addEdge( int v, int w , Weight weight){
        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );
        // 注意, 由于在邻接表的情况, 查找是否有重边需要遍历整个链表
        // 我们的程序允许重边的出现
        g[v].push_back(new Edge<Weight>(v, w, weight));
        if( v != w && !directed )
            g[w].push_back(new Edge<Weight>(w, v, weight));
        m ++;
    }
    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){
        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );
        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v][i]->other(v) == w )
                return true;
        return false;
    }
    // 显示图的信息
    void show(){
        for( int i = 0 ; i < n ; i ++ ){
            cout<<"vertex "<<i<<":\t";
            for( int j = 0 ; j < g[i].size() ; j ++ )
                cout<<"( to:"<<g[i][j]->w()<<",wt:"<<g[i][j]->wt()<<")\t";
            cout<<endl;
        }
    }
    // 邻边迭代器, 传入一个图和一个顶点,
    // 迭代在这个图中和这个顶点向连的所有边
    class adjIterator{
    private:
        SparseGraph &G; // 图G的引用
        int v;
        int index;
    public:
        // 构造函数
        adjIterator(SparseGraph &graph, int v): G(graph){
            this->v = v;
            this->index = 0;
        }
        ~adjIterator(){}
        // 返回图G中与顶点v相连接的第一个边
        Edge<Weight>* begin(){
            index = 0;
            if( G.g[v].size() )
                return G.g[v][index];
            // 若没有顶点和v相连接, 则返回NULL
            return NULL;
        }
        // 返回图G中与顶点v相连接的下一个边
        Edge<Weight>* next(){
            index += 1;
            if( index < G.g[v].size() )
                return G.g[v][index];
            return NULL;
        }
        // 查看是否已经迭代完了图G中与顶点v相连接的所有顶点
        bool end(){
            return index >= G.g[v].size();
        }
    };
};