用一个Edge类描述顶点与边
#pragma once
#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; } //返回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<Weight>& e) { //当前边的权值是否小于给定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();
}
};
在DenseGraph 和 SparseGraph中加上权值信息
- DenseGraph
#pragma once
#include <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
using namespace std;
template<typename Weight>
class DenseGraph {
private:
int n, m; //v=vertex,e=edge
vector<vector<Edge<Weight>*>> 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<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; }
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++;
}
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<Weight>* begin() {
index = -1;
return next();
}
//返回下一个与顶点v相连的顶点
Edge<Weight>* 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 <iostream>
#include <vector>
#include <cassert>
#include "Edge.h"
using namespace std;
template<typename Weight>
class SparseGraph {
private:
int n, m;
vector<vector<Edge<Weight>*>> 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<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; }
void addEdge(int a, int b,Weight weight) {
assert(a >= 0 && a < n);
assert(b >= 0 && b < n);
g[a].push_back(new Edge<Weight>(a,b,weight));
if (a != b && !directed)
g[b].push_back(new Edge<Weight>(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<Weight>* begin() {
index = 0;
if (G.g[v].size())
return G.g[v][index];
return NULL;
}
//返回下一个与顶点v相连的顶点
Edge<Weight>* 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 <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <cassert>
using namespace std;
template<typename Graph,typename Weight>
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 <iostream>
#include "DenseGraph.h"
#include "SparseGraph.h"
#include <fstream>
#include <string>
#include "readGraph.h"
using namespace std;
int main() {
string filename = "testG1.txt";
DenseGraph<double> DG(13, false);
readGraph<DenseGraph<double>, double> readDG(DG, filename);
DG.show();
cout << "================================" << endl;
SparseGraph<double> SG(13, true);
readGraph<SparseGraph<double>, double> readSG(SG, filename);
SG.show();
cout << endl;
system("pause");
return 0;
}
“testG.txt”
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