即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

《数据结构实战》——————————————-图论 无加权最短路径算法

编程语言 li2818 41℃ 0评论

该代码是用于计算无加权的最短路径算法:

#ifndef __CDIRECTEDGRAPH__H
#define __CDIRECTEDGRAPH__H
#include 
#include 

// 邻接表表示有向图 拓扑排序 无权最短路径

const int NERVER_ATTACH = 9999;

struct VertexNode // 顶点
{
 std::string cName; // 顶点名字
 int  nInDegree; // 入度
 int  nDistance; // 最短路径
 std::list 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 
#include 
#include 

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 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 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;
}



用到的图如下:




转载请注明:CodingBlog » 《数据结构实战》——————————————-图论 无加权最短路径算法

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情