基于C++的带权重的无向图的实现(邻接表法)

基本概念

  1. 图的表达形式:Graph = (V,E)
    基于C++的带权重的无向图的实现(邻接表法)
    其中V代表顶点(Vertex)的集合,E代表边(Edge)的集合,每一组边用括号表示,比如(A,B)代表顶点A,B之间的边。

  1. 图可以分为有向图和无向图,例如:
    基于C++的带权重的无向图的实现(邻接表法)

  2. 我们可以用邻接矩阵或者邻接表,来实现“图”这种数据结构,比如,对于下图:
    基于C++的带权重的无向图的实现(邻接表法)

邻接矩阵和邻接表的表示如下:
基于C++的带权重的无向图的实现(邻接表法)

  • 邻接矩阵中,横轴和纵轴表示的数字分别为顶点,矩阵中的“0”和“1”表示两个顶点间是否有相邻关系。邻接矩阵中主对角线都是0因为顶点不可能与本身具有相邻关系。要知道某个顶点的度数,只需要求该顶点所在的行或者列的和即可。

  • 邻接表是一种数组与链表(或集合)结合的存储方法,其中数组用来存放所有顶点,链表(或集合)用来存在该顶点的所有邻接顶点。


  1. 如果顶点之间的边加上权重,则可以表示如下:

基于C++的带权重的无向图的实现(邻接表法)


本文所实现的就是这种带权重的无向图,测试案例用的就是该图顶点和边的数据,最终存储在如下所示的邻接表中:

基于C++的带权重的无向图的实现(邻接表法)

定义类

图类(class Graph)

由于C++中存在很多高效的STL容器,这里使用了map和set两种关联式容器来存储顶点和边的数据。

  1. map:存储键值对(key-value)的容器,提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可以称为该关键字所对应的值)的数据处理能力。这里我把顶点设置为键,其对应的邻接点和边的权重的集合设置为值。

  2. set:不会有相同元素,并且存进去的元素会自动进行升序排序(默认情况下),set就是每一个顶点的邻接表。

来存储每一个顶点及其邻接点和权重集合,设置了模板"T"这样图就可以存储任何数据类型的数据。

template <typename T>
class Graph {
public:
	map<T, set<Edge<T>>> adj;
};

边类(class Edge)

类中有两个成员变量,其中vertex表示相邻顶点,weight表示权重。

template <typename T>
class Edge {
public:
	T vertex;
	int weight;
};

实现的功能


在Graph类中实现了以下功能,T为提前定义好的模板:


函数名 用途
bool contains(const T& u) 判断图内是否存在顶点u
bool adjacent(const T& u, const T& v) 判断顶点u和v是否相邻
void add_vertex(const T& u) 在图中添加顶点u
void add_edge(const T& u, const T& v, int weight ) 给顶点u和v添加边
void change_weight(const T& u, const T& v, int weight) 改变顶点u和v之间边的权重值
void remove_weight(const T& u, const T& v) 删除顶点u和v之间边的权重值
void remove_vertex(const T& u) 删除给定的顶点u, 同时清除所有入射边
void remove_edge(const T& u, const T& v) 删除两个顶点之间的边
int degree(const T& u) 返回顶点的入射边数
int num_vertices() 返回图中的顶点总数
int num_edges() 返回图中的边的总数
int largest_degree() 返回最大顶点的度数。
int get_weight(const T& u, const T& v) 返回顶点u和v之间边的权重值
vector get_vertices() 返回图形中所有顶点ID的vector向量
vector get_neighbours(const T& u) 返回给定顶点的所有相邻顶点ID的vector向量。
vector depth_first(const T& u) 深度优先遍历(递归)
void dft_recursion(const T& u, set& visited, vector& result ) 递归函数
vector breadth_first(const T& u) 广度优先遍历(迭代)
void show() 打印图中所有数据

代码实现

  1. 在“edge.hpp”中的代码如下:
template <typename T>
class Edge {
public:
	T vertex;
	int weight;

	Edge(T neighbour_vertex) {
		this->vertex = neighbour_vertex;
		this->weight = 0;
	}

	Edge(T neighbour_vertex, int weight) {
		this->vertex = neighbour_vertex;
		this->weight = weight;
	}

	bool operator<(const Edge& obj) const {
		return obj.vertex > vertex;
	}

	bool operator==(const Edge& obj) const {
		return obj.vertex == vertex;
	}
};

重载了"<“和”=="运算符,这样Edge的对象就可以在集合中进行排序和查找。


  1. 在“graph.hpp”中的代码如下:
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include "edge.hpp"
using namespace std; 

template <typename T>
class Graph {
public:
	map<T, set<Edge<T>>> adj;

	bool contains(const T& u); 
	bool adjacent(const T& u, const T& v); 

	void add_vertex(const T& u); 
	void add_edge(const T& u, const T& v, int weight ); 

	void change_weight(const T& u, const T& v, int weight); 

	void remove_weight(const T& u, const T& v); 
	void remove_vertex(const T& u); 
	void remove_edge(const T& u, const T& v); 

	int degree(const T& u); 
	int num_vertices(); 
	int num_edges(); 
	int largest_degree(); 

	int get_weight(const T& u, const T& v); 
	vector<T> get_vertices(); 
	vector<T> get_neighbours(const T& u); 

	void dft_recursion(const T& u, set<T>& visited, vector<T>& result ); 
	vector<T> depth_first(const T& u); 
	vector<T> breadth_first(const T& u); 

	void show();
};

template <typename T> void Graph<T>::show() {
	for (const auto& u : adj) {
		cout <<"顶点"<< u.first << ": ";
		for (const auto& v : adj[u.first])
			cout << "(相邻顶点: " << v.vertex << ", 边的权重: " << v.weight << ") ";
		cout <<endl;
	}
}

template <typename T> bool Graph<T>::contains(const T& u) {
	for (auto neighbor : adj)
		if (neighbor.first == u)
			return true;
	return false;
}

template <typename T> bool Graph<T>::adjacent(const T& u, const T& v) {
	if (contains(u) && contains(v) && u != v) {
		for (auto edge : adj[u])
			if (edge.vertex == v)
				return true;
	}
	return false;
}

template <typename T> void Graph<T>::add_vertex(const T& u) {
	if (!contains(u)) {
		set<Edge<T>> edge_list;
		adj[u] = edge_list;
	}
}

template <typename T> void Graph<T>::add_edge(const T& u, const T& v, int weight) {
	if (!adjacent(u, v)) {
		adj[u].insert(Edge<T>(v, weight));
		adj[v].insert(Edge<T>(u, weight));
	}
}

template <typename T> void Graph<T>::change_weight(const T& u, const T& v, int weight) {
	if (contains(u) && contains(v)) {
		if (adj[u].find(Edge<T>(v)) != adj[u].end()) {
			adj[u].erase(Edge<T>(v));
			adj[u].insert(Edge<T>(v, weight));
		}

		if (adj[v].find(Edge<T>(u)) != adj[v].end()) {
			adj[v].erase(Edge<T>(u));
			adj[v].insert(Edge<T>(u, weight));
		}
	}
}

template <typename T> void Graph<T>::remove_weight(const T& u, const T& v) {
	if (contains(u) && contains(v)) {
		if (adj[u].find(Edge<T>(v)) != adj[u].end()) {
			adj[u].erase(Edge<T>(v));
			adj[u].insert(Edge<T>(v, 0));
		}

		if (adj[v].find(Edge<T>(u)) != adj[v].end()) {
			adj[v].erase(Edge<T>(u));
			adj[v].insert(Edge<T>(u, 0));
		}
	}
}

template <typename T> void Graph<T>::remove_vertex(const T& u) {
	if (contains(u)) {
		for (auto& vertex : adj) {
			if (vertex.second.find(Edge<T>(u)) != vertex.second.end())
				vertex.second.erase(Edge<T>(u));
		}
		adj.erase(u);
	}
}

template <typename T> void Graph<T>::remove_edge(const T& u, const T& v) {
	if (u == v || !contains(u) || !contains(v)) return;

	if (adj[u].find(Edge<T>(v)) != adj[u].end()) {
		adj[u].erase(Edge<T>(v));
		adj[v].erase(Edge<T>(u));
	}
}


template <typename T> int Graph<T>::degree(const T& u) {
	if (contains(u)) return adj[u].size();

	return -1; // 度数为-1说明图中没有该顶点
}

template <typename T> int Graph<T>::num_vertices() {
	return adj.size();
}

template <typename T> int Graph<T>::num_edges() {
	int count = 0;
	set<Edge<T>> vertex_set;

	for (auto vertex : adj) {
		vertex_set.insert(Edge<T>(vertex.first, 0));
		for (auto edge : vertex.second) {
			if (vertex_set.find(edge) != vertex_set.end()) continue;
			count++;
		}
	}
	return count;
}

template <typename T> int Graph<T>::largest_degree() {
	if (num_vertices() == 0) return 0;

	unsigned max_degree = 0;
	for (auto vertex : adj) {
		if (vertex.second.size() > max_degree)
			max_degree = vertex.second.size();
	}
	return max_degree;
}

template <typename T> int  Graph<T>::get_weight(const T& u, const T& v) {
	if (contains(u) && contains(v)) {
		for (Edge<T> edge : adj[u])
			if (edge.vertex == v) return edge.weight;
	}
	return -1;  
}

template <typename T> vector<T> Graph<T>::get_vertices() {
	vector<T> vertices;
	for (auto vertex : adj)
		vertices.push_back(vertex.first);

	return vertices;
}

template <typename T> vector<T> Graph<T>::get_neighbours(const T& u) {
	vector<T> neighbours;

	if (contains(u)) {
		for (Edge<T> edge : adj[u])
			neighbours.push_back(edge.vertex);
	}

	return neighbours;
}

template <typename T> void Graph<T>::dft_recursion(const T& u, set<T>& visited, vector<T>& result) {
	result.push_back(u);
	visited.insert(u);

	for (Edge<T> edge : adj[u])
		if (visited.find(edge.vertex) == visited.end())
			dft_recursion(edge.vertex, visited, result);
}

template <typename T> vector<T> Graph<T>::depth_first(const T& u) {
	vector<T> result;
	set<T> visited;
	if (contains(u))  dft_recursion(u, visited, result);
	return  result;
}

template <typename T> vector<T> Graph<T>::breadth_first(const T& u) {
	vector<T>result;
	set<T> visited;
	queue<T> q;

	if (!contains(u)) return result;

	q.push(u);
	visited.insert(u);

	while (!q.empty()) {
		T v = q.front();
		q.pop();

		result.push_back(v);

		for (Edge<T> edge : adj[v]) {
			if (visited.find(edge.vertex) == visited.end()) {
				visited.insert(edge.vertex);
				q.push(edge.vertex);
			}
		}
	}
	return result;
}

测试

在“graph_testing.cpp”中的代码如下:

#include "graph.hpp"

int main() 
{
    Graph<char> g;
    g.add_vertex('A');
    g.add_vertex('B');
    g.add_vertex('C');
    g.add_vertex('D');
    g.add_vertex('E');
    g.add_vertex('F');
    g.add_vertex('G');

    g.add_edge('A', 'B', 7);
    g.add_edge('A', 'D', 5);
    g.add_edge('B', 'C', 8);
    g.add_edge('B', 'D', 9);
    g.add_edge('B', 'E', 7);
    g.add_edge('C', 'E', 5);
    g.add_edge('D', 'E', 15);
    g.add_edge('D', 'F', 6);
    g.add_edge('E', 'F', 8);
    g.add_edge('E', 'G', 9);
    g.add_edge('F', 'G', 11);

    g.add_vertex('H');
    g.add_edge('B', 'H', 9);
    g.add_edge('A', 'H', 10);
    g.add_edge('D', 'H', 11);
    g.add_edge('A', 'H', 12);
    g.remove_vertex('H');
    cout << "打印图中顶点及其邻接表的详细信息如下" << endl;
    g.show();
    cout << endl;

    cout << "'A' 和 'D'之间边的权重为:" << g.get_weight('A','D') << endl;
    g.change_weight('A', 'D', 100);
    cout << "将'A' 和 'D'之间边的权重更改为100后,其权重为:" << g.get_weight('A', 'D') << endl;
    g.remove_weight('A', 'D');
    cout << "将'A' 和 'D'之间边的权重删除后,其权重为:" << g.get_weight('A', 'D') << endl;
    cout << "将'A' 和 'D'之间边的权重重新设置为5" << endl;
    g.change_weight('A', 'D', 5);

    cout << "顶点总数:" << g.num_vertices() << endl;
    cout << "边的总数:" << g.num_edges() << endl;

    cout << "图中包含'F'吗?" << (g.contains('F') ? "包含" : "不包含") << endl;
    cout << "图中包含'G'吗?" << (g.contains('G') ? "包含" : "不包含") << endl;
    cout << "'A'和'D'相邻吗?" << (g.adjacent('A', 'D') ? "相邻" : "不相邻") << endl;
    cout << "'B'和'E'相邻吗?" << (g.adjacent('B', 'E') ? "相邻" : "不相邻") << endl;
    cout << "结点'A'的度数为: " << g.degree('A') << endl;
    cout << "最大度数为:" << g.largest_degree() << endl;

    auto vertices = g.get_vertices();
    cout << "图中的顶点分别为:";
    for (auto u : vertices) cout << " " << u;
    cout << endl;

    auto nbrs = g.get_neighbours('F');
    cout << "顶点F的邻接结点为:";
    for (auto u : nbrs) cout << " " << u;
    cout << endl;

    auto dft = g.depth_first('A');
    cout << "从顶点A进行深度优先遍历: {";
    for (auto u : dft) cout << u << " ";
    cout << "}" << endl;

    auto bft = g.breadth_first('A');
    cout << "从顶点A进行广度优先遍历: {";
    for (auto u : bft) cout << u << " ";
    cout << "}" << endl;

    cout << endl << endl;

	return 0;
}

输出结果:

基于C++的带权重的无向图的实现(邻接表法)

再来跟刚刚的两张概念图直观对比一下,发现完全一致:
基于C++的带权重的无向图的实现(邻接表法)

基于C++的带权重的无向图的实现(邻接表法)

给大家推荐一个可交互的在线绘图的网站,在已知顶点和边的数据后可以在这里左边Node Count栏输入数据进行可视化:
https://csacademy.com/app/graph_editor/
基于C++的带权重的无向图的实现(邻接表法)

上一篇:匈牙利算法 二分图的最大匹配


下一篇:2019年12月真题词汇(持续更新)