该代码是用于计算无加权的最短路径算法：
#ifndef __CDIRECTEDGRAPH__H #define __CDIRECTEDGRAPH__H #include <iostream> #include <list> // 邻接表表示有向图 拓扑排序 无权最短路径 const int NERVER_ATTACH = 9999; struct VertexNode // 顶点 { std::string cName; // 顶点名字 int nInDegree; // 入度 int nDistance; // 最短路径 std::list<struct VertexNode*> listNodes; // 邻接点 VertexNode() { cName = ""; nInDegree = NERVER_ATTACH; // 未分配的顶点 nDistance = NERVER_ATTACH; listNodes.clear(); } }; class CDirectedGraph { public: CDirectedGraph(int nNodes); ~CDirectedGraph(); public: bool InsertEdge(std::string aIn, std::string bOut); // 插入有向边 aIn-->aOut void TopologicalSort(); // 拓扑排序 void ShortedPath(std::string sVertex); // 无权最短路径算法 private: void FindIndexInsert(std::string aIn, int& nInsertIndex, bool& bFindInsert, bool& bFindIn); private: struct VertexNode* m_pNodes; // 所有点的集合 int m_nNodes; // 顶点数量 }; #endif#include "DirectedGraph.h" #include <algorithm> #include <queue> #include <string> CDirectedGraph::CDirectedGraph(int nNodes) : m_nNodes(nNodes) { if (!m_pNodes) m_pNodes = new VertexNode[nNodes]; } CDirectedGraph::~CDirectedGraph() { delete[] m_pNodes; } void CDirectedGraph::FindIndexInsert(std::string aIn, int& nInsertIndex, bool& bFindInsert, bool& bFindIn) { nInsertIndex = 0; bFindInsert = false; bFindIn = false; for (int i = 0; i < m_nNodes; i++) { if ((m_pNodes + i)->cName != aIn && (m_pNodes + i)->nInDegree == NERVER_ATTACH && !bFindInsert) { nInsertIndex = i; bFindInsert = true; } if ((m_pNodes + i)->cName == aIn) { bFindIn = true; nInsertIndex = i; break; } } } bool CDirectedGraph::InsertEdge(std::string aIn, std::string bOut) { int nInsertIndex = 0; bool bFindInsert = false; bool bFindIn = false; int nInsertIndexOut = 0; bool bFindInsertOut = false; bool bFindInOut = false; FindIndexInsert(aIn, nInsertIndex, bFindInsert, bFindIn); if (bFindInsert && !bFindIn) // 还未分配 { (m_pNodes + nInsertIndex)->cName = aIn; (m_pNodes + nInsertIndex)->nInDegree = 0; // 入度为0 } FindIndexInsert(bOut, nInsertIndexOut, bFindInsertOut, bFindInOut); if (bFindInsertOut && !bFindInOut) // 还未分配 { (m_pNodes + nInsertIndexOut)->cName = bOut; (m_pNodes + nInsertIndexOut)->nInDegree = 0; // 入度为0 } (m_pNodes + nInsertIndexOut)->nInDegree += 1; // 入度加1 (m_pNodes + nInsertIndex)->listNodes.push_back(m_pNodes + nInsertIndexOut); // 改变邻接表 return true; } void CDirectedGraph::TopologicalSort() // 拓扑排序 注意一次排序后就更改了所有节点的度 { std::queue<VertexNode*> queueVertex; // 度为0的顶点 for (int i = 0; i < m_nNodes; i++) if ((m_pNodes + i)->nInDegree == 0) queueVertex.push(m_pNodes + i); while (!queueVertex.empty()) { VertexNode* pNode = queueVertex.front(); queueVertex.pop(); std::cout << pNode->cName << "\t"; // 更新邻接点的度 for (auto& iter : pNode->listNodes) { iter->nInDegree -= 1; if (iter->nInDegree == 0) queueVertex.push(iter); } } } void CDirectedGraph::ShortedPath(std::string sVertex) // 无权最短路径算法 { std::cout << std::endl; int nInsertIndex = 0; bool bFindInsert = false; bool bFindIn = false; FindIndexInsert(sVertex, nInsertIndex, bFindInsert, bFindIn); if (!bFindIn) // 没有该顶点 return; for (int i = 0; i < m_nNodes; i++) // 初始化到所有顶点的路径长度 (m_pNodes + i)->nDistance = NERVER_ATTACH; (m_pNodes + nInsertIndex)->nDistance = 0; // 自己到自己的路径为0 std::queue<VertexNode*> queueDistance; queueDistance.push(m_pNodes + nInsertIndex); while (!queueDistance.empty()) { VertexNode* pNode = queueDistance.front(); queueDistance.pop(); if (!pNode->listNodes.empty()) { for (auto iter = pNode->listNodes.begin(); iter != pNode->listNodes.end(); iter++) { if ((*iter)->nDistance == NERVER_ATTACH) (*iter)->nDistance = pNode->nDistance + 1; // 更新长度 queueDistance.push(*iter); } } } // 打印到所有顶点的无权路径 for (int i = 0; i < m_nNodes; i++) { std::cout << sVertex << " 到顶点" << (m_pNodes + i)->cName << "的最短距离为: "; if ((m_pNodes + i)->nDistance == NERVER_ATTACH) std::cout << "无法到达" << std::endl; else std::cout << (m_pNodes + i)->nDistance << std::endl; } } #include "DirectedGraph.h" int main() { CDirectedGraph directedGraph(7); directedGraph.InsertEdge("v1", "v2"); directedGraph.InsertEdge("v1", "v4"); directedGraph.InsertEdge("v1", "v3"); directedGraph.InsertEdge("v2", "v4"); directedGraph.InsertEdge("v2", "v5"); directedGraph.InsertEdge("v3", "v6"); directedGraph.InsertEdge("v4", "v3"); directedGraph.InsertEdge("v4", "v6"); directedGraph.InsertEdge("v4", "v7"); directedGraph.InsertEdge("v5", "v4"); directedGraph.InsertEdge("v5", "v7"); directedGraph.InsertEdge("v7", "v6"); directedGraph.TopologicalSort(); directedGraph.ShortedPath("v1"); directedGraph.ShortedPath("v6"); std::cin.get(); return 0; } 用到的图如下：
