255 lines
6.8 KiB
C++
255 lines
6.8 KiB
C++
#include<iostream>
|
||
#include<string>
|
||
#include<vector>
|
||
#include<map>
|
||
#include<set>
|
||
#include<queue>
|
||
#include<stack>
|
||
#include<limits.h>
|
||
#include "edge.hpp"
|
||
#define MAX 100
|
||
using namespace std;
|
||
|
||
template <typename T>
|
||
class Graph {
|
||
public:
|
||
int wealth[MAX];
|
||
map<T, set<Edge<T>>> adj; /* 邻接表 */
|
||
|
||
bool contains(const T& u); /* 判断顶点u是否在图中 */
|
||
bool adjacent(const T& u, const T& v); /* 判断顶点u和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(); /* 得到图中所有顶点 */
|
||
void show_neighbours(const T& u); /* 得到顶点u的所有边 */
|
||
string get_neighbours(const T& u);
|
||
int get_wealth(const T u);
|
||
void show();
|
||
void dft_recursion(const T& u, set<T>& visited, vector<T>& result); /* 深度优先遍历递归辅助函数 */
|
||
vector<T> depth_first_rec(const T& u); /* 深度优先遍历递归法 */
|
||
vector<T> depth_first_itr(const T& u); /* 深度优先遍历迭代法*/
|
||
vector<T> breadth_first(const T& u); /* 广度优先遍历迭代法 */
|
||
|
||
string dijkstra(const T start); /* dijkstra最短路径算法 */
|
||
};
|
||
|
||
template <typename T> void Graph<T>::show() {
|
||
int i = 0;
|
||
for (const auto& u : adj) {
|
||
cout << "城堡" << u.first << "(" << this->wealth[i] << "): ";
|
||
for (const auto& v : adj[u.first])
|
||
cout << "[->城堡" << v.vertex << " 危险值: " << v.weight << "]";
|
||
cout << endl;
|
||
i++;
|
||
}
|
||
}
|
||
|
||
template <typename T> bool Graph<T>::contains(const T& u) {
|
||
return adj.find(u) != adj.end();
|
||
}
|
||
|
||
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> void Graph<T>::show_neighbours(const T& u) {
|
||
|
||
for (const auto& v : adj[u])
|
||
cout << "[->城堡" << v.vertex << "(" << this->wealth[v.vertex - 'A'] << "): 危险值: " << v.weight << "]";
|
||
cout << endl;
|
||
|
||
}
|
||
|
||
template <typename T> string Graph<T>::get_neighbours(const T& u) {
|
||
string a = "";
|
||
for (const auto& v : adj[u])
|
||
a += v.vertex;
|
||
return a;
|
||
}
|
||
|
||
template <typename T> int Graph<T>::get_wealth(const T u) {
|
||
return wealth[u - 'A'];
|
||
}
|
||
|
||
template <typename T> string Graph<T>::dijkstra(const T start) {
|
||
int size = this->num_vertices();
|
||
cout << size;
|
||
// 设置dis用来存放初始点到图中任何一个顶点的距离
|
||
map<T, int> dis;
|
||
// 设置带权重的队列，按每个pair的第一个元素进行从小到大的排列
|
||
priority_queue<pair<int, T>, vector<pair<int, T>>, greater<pair<int, T>>> q;
|
||
|
||
for (T vertex : get_vertices()) {
|
||
// 设置初始顶点到自己的距离为0
|
||
if (vertex == start) dis[start] = 0;
|
||
// 设置初始顶点到其他顶点的距离为无穷大
|
||
else dis[vertex] = INT_MAX;
|
||
}
|
||
|
||
// 设置集合visited来存放已经访问过的顶点
|
||
set<T> visited;
|
||
|
||
// 入队：入队的元素是一个pair类型，第一个值是权重，第二个值是顶点
|
||
q.push(make_pair(0, start));
|
||
|
||
while (!q.empty()) {
|
||
// 队首元素出队
|
||
auto front = q.top();
|
||
q.pop();
|
||
|
||
// 获得当前顶点
|
||
T u = front.second;
|
||
|
||
// 如果该顶点已经访问过则跳过本此循环，否则存入到集合visited中表示已经访问过
|
||
if (visited.find(u) != visited.end()) continue;
|
||
else visited.insert(u);
|
||
|
||
// 获得到顶点u的最短路径"shortest_distance_to_u"，将此路径存入到dis结果中
|
||
int shortest_distance_to_u = front.first;
|
||
dis[u] = shortest_distance_to_u;
|
||
|
||
// 依次访问顶点u尚未访问过的邻居
|
||
for (auto v : adj[u]) {
|
||
if (visited.find(v.vertex) == visited.end()) {
|
||
// 从顶点u到邻居v的路径记为“distance_to_v”
|
||
int distance_to_v = v.weight;
|
||
q.push(make_pair(shortest_distance_to_u + distance_to_v, v.vertex));
|
||
}
|
||
}
|
||
}
|
||
return "1";
|
||
}
|
||
|