第7章 图结构
}
cout<<\按邻接表显示结果为：\\n\for(i=0;i cout<<\按逆邻接表显示结果为：\\n\for(i=0;i (5)程序演示主程序代码 程序中分别建立一个有向图G1和一个有向网G2的十字链表，并按邻接表和逆邻接表两种形式显示所建立的的十字链表的内容。 void main() { OLGraph G1,G2; GKind gk1=DG,gk2=DN; cout<<\建立一个有向图的十字链表G1:\\n\ CreateGraph_OLG(G1,gk1); cout<<\建立一个有向网的十字链表G2:\\n\ CreateGraph_OLG(G2,gk2); cout<<\有向图G1的信息为:\\n\ DisplyOLG(G1); cout<<\有向网G2的信息为:\\n\ DisplyOLG(G2); }程序运行演示结构为： -.183.- 第7章 图结构 建立一个有向图的十字链表G1: 输入顶点数和边(弧)数vexnum arcnum:4 7↙ 按某种顺序输入4个顶点的值: 1 2 3 4↙ 输入图中7条弧的信息u v: 1 2 1 3 3 1 3 4 4 1 4 2 4 3↙ 建立一个有向网的十字链表G2: 输入顶点数和边(弧)数vexnum arcnum:4 7↙ 按某种顺序输入4个顶点的值: 1 2 3 4↙ 输入图中7条弧和权的信息u v w: 1 2 8 1 3 5 3 1 2 3 4 4 4 1 6 4 2 7 4 3 3↙ 有向图G1的信息为: 按邻接表显示结果为： 0 (1): [0 2] [0 1] 1 (2): 2 (3): [2 3] [2 0] 3 (4): [3 2] [3 1] [3 0] 按逆邻接表显示结果为： 0 (1): [3 0] [2 0] 1 (2): [3 1] [0 1] 2 (3): [3 2] [0 2] 3 (4): [2 3] 有向网G2的信息为: 按邻接表显示结果为： 0 (1): [0 2 5] [0 1 8] 1 (2): 2 (3): [2 3 4] [2 0 2] 3 (4): [3 2 3] [3 1 7] [3 0 6] 按逆邻接表显示结果为： 0 (1): [3 0 6] [2 0 2] 1 (2): [3 1 7] [0 1 8] 2 (3): [3 2 3] [0 2 5] 3 (4): [2 3 4] 说明： （1）在程序显示的结果中，第一列、第二列分别为顶点位置的下标和顶点的值。对于图，单链表中的每一项表示该顶点及其邻接点的下标；对于网，还要显示相应弧的权值。 （2）程序演示中所建立的是图7.15中有向图(a)和有向网(b)的十字链表的一种表示。 （3）从存储结构可以看出，在十字链表中很容易算出一个顶点的出度和入度，并且建立十字链表的时间复杂度与建立邻接表的时间复杂度相同，均为O(n*e)。所以在有向图的应用中，十字链表是一个很有用的工具。 7.2.4无向图的邻接多重表表示法 在无向图的邻接表表示中，每一条边(v,w)均出现两次，即在顶点v的单链表中有顶点v、w构成的边结点，同时在顶点w的单链表中有顶点w、v构成的边结点。这样，在对边进行搜索的有关问题中，同一条边出现两次显然会带来一些不便；同时，当图中的边数较大时明显增加了内存空间的占用量。为此，下面给出无向图的邻接多重链表表示法。 1．邻接多重表的定义 在邻接多重表中包含链表的头结点和链表中的边结点两种类型的结点，图7.16给出邻接多重表中头结点和边结点结构的结构示图。 其中，头结点包含顶点信息域(data)、指向依附于该顶点的第一条边结点的指针域 -.184.- 第7章 图结构 (firstedge)。边结点包含判断该边是否被扫描过的标志域(mark)、该边依附的第一个顶点位置域(ivex)、边依附的第二个顶点位置域(jvex)、指向下一条依附于ivex的边的指针域(ilink)、指向下一条依附于jvex的边的指针域(jlink)、边的信息（比如权值）域(info)。 例如，图7.17给出无向图的一种邻接多重表表示。 在邻接多重表中，所有依附于同一顶点的边链接在一个链表中，由于一条边依附于两个顶点，所以每个边结点同时出现在两个链表中。所以，无向图的邻接多重表中边结点的个数是其邻接表表示中边结点个数的一半。邻接多重链表中，表的头结点之间是顺序存储结构，边结点所在的链表是非循环链表，结点之间的相对位置也是自然形成的，不一定按顶点序列号有序。所以，无向图的邻接多重表表示方式是不唯一的。 2．邻接多重表的存储表示与实现 (1)邻接多重表存储结构的类型定义 下面分别给出边结点(EBox)、顶点结点(VexBox)、邻接多重链表(AMLGraph)的类型定义。 struct EBox{ //边结点的结构定义 int mark; //访问标志域 int ivex,jvex; //边依附的两个顶点的位置 EBox *ilink,*jlink; //指向依附两个顶点的下一条边的指针域 int info; //边的相关信息（如权值）域 }; struct VexBox{ //顶点结点结构定义 VType data; //顶点信息 EBox *firsedge; //指向第一条依附该顶点的边 }; struct AMLGraph{ //定义邻接多重链表类型 VexBox* xlist; //链表头结点数组指针 int vexnum,edgenum; //无向图的顶点数和边数 GKind kind; }; (2)邻接多重链表的查找操作 函数int LocateVex_AMLG(AMLGraph G,VType u)返回顶点u在图G中的位置，如果查找失败则返回0值。 -.185.- 第7章 图结构 int LocateVex_AMLG(AMLGraph G,VType u) { int i; for(i=0;i (3)建立邻接多重链表的算法实现 函数void CreateGraph_AMLG(AMLGraph& G,GKind kind)根据图的类型(kind)建立一个无向图或无向网的邻接多重链表(G)。 void CreateGraph_AMLG(AMLGraph& G,GKind kind) { int i,j,k; VType u,v; EBox* pr; G.kind=kind; cout<<\输入顶点数和边数vexnum edgenum:\ cin>>G.vexnum>>G.edgenum; G.xlist=new VexBox[G.vexnum]; //为顶点数组分配内存空间 cout<<\按某种顺序输入\.vexnum<<\个顶点的值:\\n\ for(i=0;i -.186.-