图--十字链表-笔记

参考来源：大话数据结构。

对于有向图来说，邻接链表无法同时考虑到边的入度和出度问题，故有了十字链表这种数据结构。

顶点表 ： 

datafirstinfirstout

其中firstin表示入边表头指针，表示该顶点的入边表中的第一个结点，firstout表示出边表头指针，指向该顶点的出边表的第一个结点。

边表：

tailvexheadvexheadlink

taillink

tailvex表示该边的起点在顶点表中的下标， headvex表示该边的终点在顶点表中的下标。headlink表示以headvex为终点的一系列边，taillink表示以tailvex为起点的一系列边。

代码如下：

/*********十字链表***********/ /************边表*************/ class EdgeNode { public: int tailvex; //该边的起点 int headvex; //该边的终点 int weight; //边的权重 EdgeNode *headlink = NULL; //入边表指针域 EdgeNode *taillink = NULL; //出边表指针域 EdgeNode(int _tail, int _head, int _weight) : tail(_tail), head(_head), weight(_weight) {}; }; /**********顶点表*******/ class VertexNode { public: int data; EdgeNode *firstin; //入度 EdgeNode *firstout;//出度 //int pValue; //int dist = infty; };

 关于解决APSP问题的代码；

https://github.com/Shinered/Johnson-s-algoorithm-APSP/blob/master/class.hpp

 

转载于:https://www.cnblogs.com/Shinered/p/9481855.html

相关资源：JAVA上百实例源码以及开源项目