加权无向图

灰太狼 2022-08-18 11:52 189阅读 0赞

用一个更加通用的API来处理Edge对象，能够使程序适用于更加常见的场景。

\-Edge.h 带权重的边的数据类型

#ifndef __EDGE_H__
    #define __EDGE_H__
    
    #include <iostream>
    #include <string>
    
    class Edge {
    private:
    	int v;
    	int w;
    	double weight;
    
    public:
    	Edge(int _v, int _w, double _weight)
    		:v(_v), w(_w), weight(_weight) {}
    
    	double getWeight()const { return weight; }
    	int either()const { return v; }
    	int other(int vertex)const;
    	std::string toString()const;
    };
    
    int Edge::other(int vertex)const {
    	if (vertex == v) return w;
    	else if (vertex == w) return v;
    	else throw std::runtime_error("Inconsistent edge.");
    }
    
    std::string Edge::toString()const {
    	std::string s;
    	s += std::to_string(v) + "-" + std::to_string(w)
    		+ " " + std::to_string(weight);
    	return s;
    }
    
    bool operator<(const Edge& lhs, const Edge& rhs) {
    	return lhs.getWeight() < rhs.getWeight();
    }
    bool operator>(const Edge& lhs, const Edge& rhs) {
    	return lhs.getWeight() > rhs.getWeight();
    }
    
    #endif

\-EdgeWeightedGraph 加权无向图的数据类型

#ifndef __EDGE_WEIGHTED_GRAPH_H__
    #define __EDGE_WEIGHTED_GRAPH_H__
    
    #include <list>
    #include "Edge.h"
    
    class EdgeWeightedGraph {
    private:
    	int vNum;				// 顶点数
    	int eNum;				// 边数
    	std::list<Edge> *adj;	// 邻接表
    
    public:
    	EdgeWeightedGraph(int v);
    	EdgeWeightedGraph(const EdgeWeightedGraph& G);
    	~EdgeWeightedGraph() { delete[] adj; }
    
    	int getV()const { return vNum; }
    	int getE()const { return eNum; }
    	std::list<Edge> getAdj(int v)const { return adj[v]; }
    	std::list<Edge> edges()const;
    	void print()const;
    
    	void addEdge(Edge e);
    
    };
    // constructor
    EdgeWeightedGraph::EdgeWeightedGraph(int v) {
    	this->vNum = v;
    	this->eNum = 0;
    	this->adj = new std::list<Edge>[vNum];
    }
    // copy constructor
    EdgeWeightedGraph::EdgeWeightedGraph(const EdgeWeightedGraph& G) {
    	this->vNum = G.vNum;
    	this->eNum = G.eNum;
    	this->adj = new std::list<Edge>[vNum];
    	for (int i = 0; i < vNum; ++i) {
    		this->adj[i] = G.adj[i];
    	}
    }
    // edges
    std::list<Edge> EdgeWeightedGraph::edges()const {
    	std::list<Edge> b;
    	for (int i = 0; i < vNum; ++i) {
    		for (Edge e : adj[i]) {
    			b.push_front(e);
    		}
    	}
    	return b;
    }
    // addEdge
    void EdgeWeightedGraph::addEdge(Edge e) {
    	int v = e.either();
    	int w = e.other(v);
    	adj[v].push_front(e);
    	adj[w].push_front(e);
    	++eNum;
    }
    // toString
    void EdgeWeightedGraph::print()const {
    	for (int i = 0; i < vNum; ++i) {
    		std::cout << i << ": ";
    		for (Edge e : adj[i]) {
    			std::cout << e.either() << "-"
    				<< e.other(e.either()) << "-"
    				<< e.getWeight() << "  ";
    		}
    	}
    }
    
    
    #endif