第8章图 at operator < const Edge&e)const( return length I=E length; ∥判边上权值小否 顶点的定义 friend class Graph ∥项点的名字 ∥边链表的头指针 图的类定义 rivate Vertex *Node Table ∥项点表(各边链表的头结点) /当前顶点个数 t NudGes; ∥当前边数 int Get VertexPos( const Type vertex);m给出顶点 vertex在图中的位置 raph( int Sz ) ∥构造函数 Graph(片; ∥析构函数 int NumberofVertices{ return Num vertices;}/返回图的顶点数 int NumberOfEdges(i return NumEdges; 3 ∥返回图的边数 char Get Value( int 1) ∥取位置为i的顶点中的值 i return i>=0&& i< NumVertices Node Table[i]. data:: float Get Weight int vl, int v2 ) ∥返回边v1,v2)上的权值 int GetFirstNeighbor( int v ); ∥取顶点v的第一个邻接顶点 int GetNextNeighbor( int v, int w ) ∥取顶点v的邻接顶点w的下一个邻接顶点 (2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合,利用链表来表示集合T。 集合T用有序链表表示,数据域为顶点序号,链表T中的顶点都是未找到最短路径的顶点。另外设 置一个数组S,其作用是记录已找到的顶点0到其他各顶点的最短路径path及最短路径长度len 算法的主要思路是 ①对数组S及链表T初始化,记录顶点0到各个顶点的初始最短路径及其长度; ②扫描链表T,寻找链表T中各个顶点到顶点0的当前最短路径中长度最小者,记为u ③在邻接表中扫描第u个顶点的出边表,确定每一边的邻接顶点号k 若顶点k的最短路径没有选中过,比较绕过顶点u到顶点k的路径长度和原来顶点0到顶点k 的最短路径长度,取其小者作为从顶点0到顶点k的新的最短路径 ④重复执行②、③步,直到图中所有顶点的最短路径长度都已选定为止 算法的实现如下: const float MaxNum= 10000000: typedef struct info i ∥辅助数组元素:各顶点最短路径信息 int pre; ∥在最短路径上前一顶点的顶点序号 float len; ∥当前最短路径长度第 8 章 图 108 int operator < ( const Edge & E ) const { return length != E.length; } //判边上权值小否 } struct Vertex { //顶点的定义 friend class Graph; char data; //顶点的名字 Edge *adj; //边链表的头指针 } class Graph { //图的类定义 private: Vertex *NodeTable; //顶点表 (各边链表的头结点) int NumVertices; //当前顶点个数 int NumEdges; //当前边数 int GetVertexPos ( const Type vertex ); //给出顶点 vertex 在图中的位置 public: Graph ( int sz ); //构造函数 ~Graph ( ); //析构函数 int NumberOfVertices ( ) { return NumVertices; } //返回图的顶点数 int NumberOfEdges ( ) { return NumEdges; } //返回图的边数 char GetValue ( int i ) //取位置为 i 的顶点中的值 { return i >= 0 && i < NumVertices ? NodeTable[i].data : ‘ ’; } float GetWeight ( int v1, int v2 ); //返回边(v1, v2)上的权值 int GetFirstNeighbor ( int v ); //取顶点 v 的第一个邻接顶点 int GetNextNeighbor ( int v, int w ); //取顶点 v 的邻接顶点 w 的下一个邻接顶点 } (2) 用集合 T = V(G) - S 代替 S (已找到最短路径的顶点集合)，利用链表来表示集合 T。 集合 T 用有序链表表示，数据域为顶点序号，链表 T 中的顶点都是未找到最短路径的顶点。另外设 置一个数组 S，其作用是记录已找到的顶点 0 到其他各顶点的最短路径 path 及最短路径长度 len。 算法的主要思路是： ① 对数组 S 及链表 T 初始化，记录顶点 0 到各个顶点的初始最短路径及其长度； ② 扫描链表 T，寻找链表 T 中各个顶点到顶点 0 的当前最短路径中长度最小者，记为 u； ③ 在邻接表中扫描第 u 个顶点的出边表，确定每一边的邻接顶点号 k。 若顶点 k 的最短路径没有选中过，比较绕过顶点 u 到顶点 k 的路径长度和原来顶点 0 到顶点 k 的最短路径长度，取其小者作为从顶点 0 到顶点 k 的新的最短路径。 ④ 重复执行②、③步，直到图中所有顶点的最短路径长度都已选定为止。 算法的实现如下： const float MaxNum = 10000000; typedef struct info { //辅助数组元素: 各顶点最短路径信息 int pre; //在最短路径上前一顶点的顶点序号 float len; //当前最短路径长度 }