概念Breadth-First Search (BFS)目的: 主要用于遍历或搜索图中的所有顶点。特点: 从根节点开始先访问所有与之相邻的节点然后再一层一层地深入。应用: 可以用来寻找两节点间的最短路径当边的权重相等时检测图中是否存在环路以及层次遍历二叉树等。数据结构: 使用队列来存储待访问的节点。Depth-First Search (DFS):目的: 同样用于遍历或搜索图中的所有顶点。特点: 从根节点开始尽可能深地搜索树的分支。应用: 用于解决连通性问题如检测环路、拓扑排序、迷宫求解等。数据结构: 使用栈可以是递归栈来存储待访问的节点。Dijkstra算法目的: 用于找到图中一个节点到其他所有节点的最短路径。特点: 要求图中没有负权边并且是从一个源节点开始计算最短路径。应用: 寻找两点之间的最短路径广泛应用于路由算法。数据结构: 使用优先队列最小堆来存储待处理的节点。Kruskal算法目的: 用于找到图的最小生成树Minimum Spanning Tree, MST。特点: 是一种贪心算法适用于边稀疏的图。应用: 在网络设计中用于构建成本最低的网络连接。数据结构: 使用并查集Union-Find来维护生成树的形成过程。需要注意的是Kruskal算法通常不直接用于有向图因为它主要用于无向图中的最小生成树问题。对于有向图我们通常考虑的是最短路径问题而不是生成树问题用法#include ../src/algo/bfs.h #include ../src/algo/dfs.h #include ../src/algo/dijkstra.h #include ../src/algo/kruskal.h #include gtest/gtest.h #include chrono #include memory #include vector class GraphTest : public ::testing::Test { protected: }; TEST_F(GraphTest, BFSTest) { Graph graph{ false, false }; graph.addEdges(a, { b }); graph.addEdges(b, { a, c }); graph.addEdges(c, { b, d, e }); graph.addEdges(d, { c, e }); graph.addEdges(e, { c, d }); auto begin std::chrono::high_resolution_clock::now(); BFS bfs{ graph }; // DFS dfs{ graph }; bfs.traverseGraph(); auto end std::chrono::high_resolution_clock::now(); auto elapsed std::chrono::duration_caststd::chrono::microseconds(end - begin); std::cout BFSTest : time in microseconds : elapsed.count() std::endl; // 节点遍历 const auto nodes graph.getNodes(); } TEST_F(GraphTest, DijkstraTest) { Graph graph{ true, true }; graph.addEdgesWeighted(a, { { d, 3 }, { h, 5 } }); graph.addEdgesWeighted(b, { { c, 4 }, { i, 1 } }); graph.addEdgesWeighted(c, { { a, 4 }, { l, 5 } }); graph.addEdgesWeighted(d, { { b, 2 }, { e, 1 }, { f, 8 } }); graph.addEdgesWeighted(e, { { c, 5 }, { j, 7 } }); graph.addEdgesWeighted(f, { { e, 2 }, { h, 2 }, { i, 7 }, { k, 10 } }); graph.addEdgesWeighted(g, { { e, 3 } }); graph.addEdgesWeighted(h, { { g, 6 }, { l, 4 }}); graph.addEdgesWeighted(i, { { k, 6 } }); graph.addEdgesWeighted(j, { { c, 8 } }); graph.addEdgesWeighted(k, { { g, 3 }, { j, 5 } }); graph.addEdgesWeighted(l, { { g, 2 }, { e, 5 }, {f, 12 } }); char src a; char dst b; Dijkstra dijkstra{ graph }; auto begin std::chrono::high_resolution_clock::now(); dijkstra.traverseGraph(src); auto end std::chrono::high_resolution_clock::now(); auto elapsed std::chrono::duration_caststd::chrono::microseconds(end - begin); std::cout DijkstraTest : time in microseconds : elapsed.count() std::endl; // 最短路径 const auto nodesList std::make_uniquestd::listchar(); nodesList-push_front(dst); dijkstra.traverseGraph(src); const std::mapchar, route routes dijkstra.getRoutes(); std::optionalchar predecessor; predecessor routes.at(dst).predecessor; while (predecessor ! std::nullopt) { nodesList-push_front(predecessor.value()); predecessor routes.at(predecessor.value()).predecessor; } auto shortPaths std::make_uniquestd::vectorchar(nodesList-begin(), nodesList-end()); } TEST_F(GraphTest, KruskalTest) { Graph graph{ false, true }; graph.addEdgesWeighted(a, { { b, 3 }, { f, 2 } }); graph.addEdgesWeighted(b, { { c, 17 }, { d, 16 } }); graph.addEdgesWeighted(c, { { d, 8 }, { i, 18 } }); graph.addEdgesWeighted(d, { { e, 11 }, { i, 4 } }); graph.addEdgesWeighted(e, { { f, 1 }, { g, 6 }, { h, 5 }, { i, 10 } }); graph.addEdgesWeighted(f, { { g, 7 } }); graph.addEdgesWeighted(g, { { h, 15 } }); graph.addEdgesWeighted(h, { { i, 12 }, { j, 13 } }); graph.addEdgesWeighted(i, { { j, 9 } }); auto begin std::chrono::high_resolution_clock::now(); Kruskal kruskal{ graph }; std::unique_ptrstd::vectorEdge edges kruskal.makeMinSpanningTree(); auto end std::chrono::high_resolution_clock::now(); auto elapsed std::chrono::duration_caststd::chrono::microseconds(end - begin); std::cout KruskalTest : time in microseconds : elapsed.count() std::endl; // 最小生成树边的权值之和最低的子图 auto edgesTuple std::make_uniquestd::vectorstd::tuplechar, char(); for (const Edge edge : *edges) { edgesTuple-push_back(std::tuplechar, char{ edge.src, edge.dst }); } }参考C 有向图拓扑排序算法_有向图排序c-CSDN博客https://github.com/Przemyslawmd/Graphs创作不易小小的支持一下吧
