【数据结构基础C++】图论07-构造带权图

#pragma once
#include 
#include 

using namespace std;

template

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; }									//返回a-b边的权值

	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& e) {								//当前边的权值是否小于给定e的权值
		return weight < e.wt();
	}

	bool operator<=(Edge& e) {
		return weight <= e.wt();
	}

	bool operator>(Edge& e) {
		return weight > e.wt();
	}

	bool operator>=(Edge& e) {
		return weight >= e.wt();
	}

	bool operator==(Edge& e) {
		return weight == e.wt();
	}
};

1. DenseGraph

#pragma once
#include 
#include 
#include 
#include "Edge.h"

using namespace std;
template

class DenseGraph {
private:
	int n, m;										//v=vertex,e=edge
	vector*>> g;				//邻接矩阵,二维,为什么要用指针？邻接矩阵中不相邻的边用NULL表示
	bool directed;

public:
	DenseGraph(int n, bool directed) {
		assert(n >= 0);
		this->n = n;
		this->m = 0;
		this->directed = directed;
		for (int i = 0; i < n; ++i) {
			g.push_back(vector*>(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; }
	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(v, w, weight);
		
		//如果是无向图
		if (v != w && !directed)
			g[w][v] = new Edge(w, v, weight);
		m++;
	}
	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] != NULL)
					cout << g[i][j]->wt() << " ";
				else
					cout << "NULL ";
			}
			cout << endl;
		}
	}

	//迭代器
	class adjIterator {
	private:
		DenseGraph& G;
		int index;
		int v;

	public:
		//构造函数
		adjIterator(DenseGraph& g, int v) :G(g) {
			assert(v >= 0 && v < G.n);
			this->v = v;
			this->index = -1;
		}
		//析构函数
		~adjIterator() {}
		//返回
		Edge* begin() {
			index = -1;
			return next();
		}
		//返回下一个与顶点v相连的顶点
		Edge* next() {
			//稠密图，邻接矩阵
			for (index += 1; index < G.V(); index++) {
				if (G.g[v][index] != NULL)
					return G.g[v][index];
			}
			//若没有顶点与v相连，
			return NULL;
		}
		//判断是否遍历到最后一个顶点
		bool end() {
			return index >= G.V();
		}
	};	
};

2.SparseGraph

#pragma once
#include 
#include 
#include 
#include "Edge.h"
using namespace std;

template
class SparseGraph {
private:
	int n, m;
	vector*>> g;
	bool directed;

public:
	SparseGraph(int n, bool directed) {
		assert(n >= 0);
		this->n = n;
		this->m = 0;
		this->directed = directed;
		for (int i = 0; i < n; ++i) {
			g.push_back(vector*>());
		}
	}
	~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; }

	void addEdge(int a, int b,Weight weight) {
		assert(a >= 0 && a < n);
		assert(b >= 0 && b < n);

		g[a].push_back(new Edge(a,b,weight));
		if (a != b && !directed)
			g[b].push_back(new Edge(b, a, weight));
		m++;
	}

	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 << ": ";
			for (int j = 0; j < g[i].size(); ++j) {
				cout << "{to: " << g[i][j]->w() << ", wt: " << g[i][j]->wt() << "} ";
			}
			cout << endl;
		}
	}

	//adjIterator
	class adjIterator {
	private:
		SparseGraph& G;
		int v;
		int index;

	public:
		adjIterator(SparseGraph& g, int v) :G(g) {
			assert(v >= 0);
			this->v = v;
			this->index = 0;
		}
		~adjIterator() {}
		//稀疏图，邻接表
		Edge* begin() {
			index = 0;
			if (G.g[v].size())
				return G.g[v][index];
			return NULL;
		}
		//返回下一个与顶点v相连的顶点
		Edge* next() {
			index++;
			if (index < G.g[v].size())
				return G.g[v][index];
			return NULL;
		}
		bool end() {
			return index >= G.g[v].size();
		}
	};
};

3.readGraph

#pragma once
#include 
#include 
#include 
#include 
#include 

using namespace std;
template

class readGraph {
public:
	//从文件读取有权图信息，存进graph中
	readGraph(Graph& graph, const string& filename) {
		ifstream ifs(filename);
		string line;
		int V, E;
		assert(ifs.is_open());
		
		assert(getline(ifs, line));
		stringstream ss(line);
		
		ss >> V >> E;

		assert(graph.V() == V);
		//读取每一条边的信息
		for (int i = 0; i < E; ++i) {
			int a, b;
			Weight w;
			assert(getline(ifs, line));
			stringstream ss(line);
			ss >> a >> b >> w;
			assert(a >= 0 && a < V);
			assert(b >= 0 && b < V);
			graph.addEdge(a, b, w);
		}
	}
};

#include 
#include "DenseGraph.h"
#include "SparseGraph.h"
#include 
#include 
#include "readGraph.h"
using namespace std;

int main() {
	string filename = "testG1.txt";
	DenseGraph DG(13, false);
	readGraph, double> readDG(DG, filename);
	DG.show();

	cout << "================================" << endl;

	SparseGraph SG(13, true);
	readGraph, double> readSG(SG, filename);
	SG.show();
	cout << endl;

	system("pause");
	return 0;
}

13 13
0 5 .12
4 3 .56
0 1 .78
9 12 .66
6 4 .02
5 4 .15
0 2 .05
11 12 .85
9 10 .12
0 6 .36
7 8 .25
9 11 .94
5 3 .99