邻接表有向图（二） C++详解

邻接表有向图（二） C++详解2014-12-18

邻接表有向图的介绍

邻接表有向图是指通过邻接表表示的有向图。

上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9条边。

上图右边的矩阵是G2在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点所对应的出边的另一个顶点的序号"。例如，第1个顶点（顶点B）包含的链表所包含的节点的数据分别是"2,4,5"；而这"2,4,5"分别对应"C,E,F"的序号，"C,E,F"都属于B的出边的另一个顶点。

邻接表有向图的代码说明

1. 基本定义

#define MAX 100// 邻接表class ListDG{private: // 内部类// 邻接表中表对应的链表的顶点class ENode{public:int ivex; // 该边所指向的顶点的位置ENode *nextEdge;// 指向下一条弧的指针};// 邻接表中表的顶点class VNode{public:char data;// 顶点信息ENode *firstEdge; // 指向第一条依附该顶点的弧};private: // 私有成员int mVexNum; // 图的顶点的数目int mEdgNum; // 图的边的数目VNode mVexs[MAX];public:// 创建邻接表对应的图（自己输入）ListDG（）;// 创建邻接表对应的图（用已提供的数据）ListDG（char vexs[], int vlen, char edges[][2], int elen）;~ListDG（）;// 打印邻接表图void print（）;private:// 读取一个输入字符char readChar（）;// 返回ch的位置int getPosition（char ch）;// 将node节点链接到list的最后void linkLast（ENode *list, ENode *node）;};

（01） ListDG是邻接表对应的结构体。 mVexNum是顶点数，mEdgNum是边数；mVexs则是保存顶点信息的一维数组。
（02） VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstEdge是该顶点所包含链表的表头指针。
（03） ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextEdge是指向下一个节点的。