加权无向图_加权无向图数据集

        用数学语言讲，设G为图，对图的每一条边e来说，都对应于一个实数W(e)（可以通俗的理解为边的“长度”，只是在数学定义中图的权可以为负数），我们把W（e）称为e的“权”。把这样的图G称为“加权图”。

加权无向图数据结构使用邻接表来存储

源代码示例：

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <functional>
 
using namespace std;
 
class Edge
{
public:
	Edge(size_t _v, size_t _w, double _weight) : v(_v), w(_w), weight(_weight) {}
 
	double getWeight() const { return weight; }
	size_t either() const { return v; }
	size_t other(size_t v) const
	{
		if (v == this->v)
			return this->w;
		else if (v == this->w)
			return this->v;
		else
		{
			cout << "error in Edge::other()" << endl;
			exit(1);
		}
	}
	void print() const{ cout << "(" << v << ", " << w << ", " << weight << ") "; }
 
private:
	size_t v, w; // 两个顶点
	double weight; // 权重
};
 
class EdgeWeithtedGraph
{
public:
	EdgeWeithtedGraph(size_t vertax_nums) : vertaxs(vertax_nums), edges(0), arr(vertax_nums) {}
 
	void addEdge(const Edge e);
 
	vector<Edge> adj(size_t v) const { return v < arrSize() ? arr[v] : vector<Edge>(); }
	vector<Edge> allEdges() const;		// 返回加权无向图的所有边
	size_t arrSize() const { return arr.size(); }
	size_t vertax() const { return vertaxs; }
	size_t edge() const { return edges; }
	void printVertax(size_t v) const;
	void printGraph() const;
 
private:
	size_t vertaxs; // 顶点个数
	size_t edges; // 边的个数
	vector<vector<Edge>> arr; // 邻接表
};
 
int main(void)
{
	EdgeWeithtedGraph graph(8);
 
	graph.addEdge(Edge(0, 7, 0.16));
	graph.addEdge(Edge(0, 2, 0.26));
	graph.addEdge(Edge(0, 4, 0.38));
	graph.addEdge(Edge(0, 6, 0.58));
	graph.addEdge(Edge(1, 7, 0.19));
	graph.addEdge(Edge(5, 7, 0.28));
	graph.addEdge(Edge(2, 7, 0.34));
	graph.addEdge(Edge(4, 7, 0.37));
	graph.addEdge(Edge(1, 3, 0.29));
	graph.addEdge(Edge(1, 5, 0.32));
	graph.addEdge(Edge(1, 2, 0.36));
	graph.addEdge(Edge(2, 3, 0.17));
	graph.addEdge(Edge(6, 2, 0.40));
	graph.addEdge(Edge(3, 6, 0.52));
	graph.addEdge(Edge(4, 5, 0.35));
	graph.addEdge(Edge(6, 4, 0.93));
 
	cout << "arrSize: " << graph.arrSize() << endl;
	cout << "vertax: " << graph.vertax() << endl;
	cout << "edge: " << graph.edge() << endl;
	cout << "----------------" << endl;
 
	graph.printGraph();
	cout << endl;
 
	system("pause");
	return 0;
}
 
void EdgeWeithtedGraph::addEdge(const Edge e)
{
	size_t v = e.either();
	size_t w = e.other(v);
	if (!(v < arrSize() && w < arrSize()))
		return;
 
	arr[v].push_back(e);
	arr[w].push_back(e);
	this->edges++;
}
 
vector<Edge> EdgeWeithtedGraph::allEdges() const
{
	vector<Edge> vec;
 
	for (size_t i = 0; i < arrSize(); i++)
	{
		for (size_t j = 0; j < arr[i].size(); j++)
		{
			if (arr[i][j].other(i) > i) // 所有边的权重各不不同，可以这样判断，每个边只保留一个
				vec.push_back(arr[i][j]);
		}
	}
	return vec;
}
 
void EdgeWeithtedGraph::printVertax(size_t v) const
{
	if (v >= arrSize())
		return;
 
	for (size_t i = 0; i < arr[v].size(); i++)
		arr[v][i].print();
	cout << endl;
}
 
void EdgeWeithtedGraph::printGraph() const
{
	for (size_t i = 0; i < arrSize(); i++)
	{
		cout << i << ": ";
		printVertax(i);
	}
}

        1、https://github.com/luoxn28/algorithm_data_structure （里面有常用的数据结构源代码，图相关算法在graph文件夹中）

        2、《算法 第4版》 图有关章节