图
基本概念
- 图的表达形式：Graph = (V,E)
其中V代表顶点（Vertex）的集合，E代表边（Edge）的集合，每一组边用括号表示，比如（A,B）代表顶点A，B之间的边。
-
图可以分为有向图和无向图，例如：
-
我们可以用邻接矩阵或者邻接表，来实现“图”这种数据结构，比如，对于下图：
邻接矩阵和邻接表的表示如下:
-
邻接矩阵中，横轴和纵轴表示的数字分别为顶点，矩阵中的“0”和“1”表示两个顶点间是否有相邻关系。邻接矩阵中主对角线都是0因为顶点不可能与本身具有相邻关系。要知道某个顶点的度数，只需要求该顶点所在的行或者列的和即可。
-
邻接表是一种数组与链表（或集合）结合的存储方法，其中数组用来存放所有顶点，链表（或集合）用来存在该顶点的所有邻接顶点。
- 如果顶点之间的边加上权重，则可以表示如下：
本文所实现的就是这种带权重的无向图，测试案例用的就是该图顶点和边的数据，最终存储在如下所示的邻接表中：
定义类
图类（class Graph)
由于C++中存在很多高效的STL容器，这里使用了map和set两种关联式容器来存储顶点和边的数据。
-
map：存储键值对(key-value)的容器，提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可以称为该关键字所对应的值）的数据处理能力。这里我把顶点设置为键，其对应的邻接点和边的权重的集合设置为值。
-
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() | 打印图中所有数据 |
代码实现
- 在“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的对象就可以在集合中进行排序和查找。
- 在“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;
}
输出结果：
再来跟刚刚的两张概念图直观对比一下，发现完全一致：
给大家推荐一个可交互的在线绘图的网站，在已知顶点和边的数据后可以在这里左边Node Count栏输入数据进行可视化：
https://csacademy.com/app/graph_editor/