第7章 图结构
在图G的邻接表中，顶点v的相邻元素可以通过遍历该顶点对应的单链表求得，设该链表中结点的个数为k那么，G为无向图时k表示v的度，G为有向图时k表示v的出度。如果求顶点v的入度，则需要遍历邻接表中的所有单链表，统计与v的序号相同的结点个数。这样处理很不方便，为此，仿照邻接表，建立一个逆邻接表，即对每个顶点v建立一个单链表，把所有邻接于v的顶点链接在一起，此时该单链表的长度即为v的入度。
例如，图7.11(a)所示的有向图可用逆邻接表表示为图7.12。
3．邻接表的存储表示与实现 (1)邻接表存储结构的类型定义
定义单链表结点类型ArcNode：
struct ArcNode{ int adjvex,weight;ArcNode* nextarc;}; 定义链表头结点结构类型VexNode：
struct VexNode{VType data;int flag;ArcNode* nextarc;}; 定义邻接表存储结构的类型ALGraph： struct ALGraph{ VexNode* vertices; //定义头结点数组指针vertices int vexnum,arcnum; //顶点数vexnum和边或弧数arcnum GKind kind; //图的种类标志kind };
(2)查找图中顶点位置的操作
函数的功能是，返回顶点u在图G中的位置，查找失败返回0值。 int LocateVex_AL(ALGraph G,VType u) { int i; for(i=0;i (3)邻接表的建立操作 函数的功能是，根据图G的种类标志kind建立G的邻接表表示的存储结构。 #include\ void CreateGraph_AL(ALGraph& G,GKind kind) { int i,j,k; -.177.- 第7章 图结构 } VType u,v; ArcNode* pr,*pr1; G.kind=kind; cout<<\输入顶点数和边(弧)数vexnum arcnum:\cin>>G.vexnum>>G.arcnum; G.vertices=new VexNode[G.vexnum]; //为顶点数组分配内存空间 cout<<\按某种顺序输入\.vexnum<<\个顶点的值:\\n\for(i=0;i { G.vertices[i].flag=0; //flag=0表示该顶点未被访问 cin>>G.vertices[i].data; //输入所有顶点的信息到vex中 G.vertices[i].nextarc=NULL; //设定初始的单链表为空 } if(G.kind==DG||G.kind==UDG) cout<<\输入图中\.arcnum<<\条边(弧)的信息u v:\\n\else cout<<\输入图中\.arcnum<<\条边(弧)和权的信息u v w:\\n\ for(k=0;k (4)显示输出邻接矩阵的操作 函数功能是，显示输出图G的邻接链表中的所有信息。 void DisplyAL(ALGraph G)//显示邻接矩阵G { int i; -.178.- 第7章 图结构 } ArcNode* p; for(i=0;i (5)演示程序主函数 程序中分别建立有向图G1、无向图G2、有向网G3和无向网G4的邻接表，并显示输出所建立的每个邻接表的数据信息。 void main() { ALGraph G1,G2,G3,G4; GKind gk1=DG,gk2=UDG,gk3=DN,gk4=UDN; cout<<\建立一个有向图的邻接表G1:\\n\ CreateGraph_AL(G1,gk1); cout<<\建立一个无向图的邻接表G2:\\n\ CreateGraph_AL(G2,gk2); cout<<\有向图G1的邻接表为:\\n\ DisplyAL(G1); cout<<\无向图G2的邻接表为:\\n\ DisplyAL(G2); cout<<\ cout<<\建立一个有向网的邻接表G3:\\n\ CreateGraph_AL(G3,gk3); cout<<\建立一个无向网的邻接表G4:\\n\ CreateGraph_AL(G4,gk4); cout<<\有向网G3的邻接表为:\\n\ DisplyAL(G3); cout<<\无向网G4的邻接表为:\\n\ DisplyAL(G4); } 程序运行演示结果为： 建立一个有向图的邻接表G1: 输入顶点数和边(弧)数vexnum arcnum:6 8↙ -.179.- 第7章 图结构 按某种顺序输入6个顶点的值: 1 2 3 4 5 6↙ 输入图中8条边(弧)的信息u v: 1 2 1 4 3 1 3 6 4 3 5 4 6 1 6 5↙ 建立一个无向图的邻接表G2: 输入顶点数和边(弧)数vexnum arcnum:6 7↙ 按某种顺序输入6个顶点的值: 1 2 3 4 5 6↙ 输入图中7条边(弧)的信息u v: 1 2 1 4 2 3 2 6 5 3 5 6 5 4↙ 有向图G1的邻接表为: 0 (1): [3] [1] 1 (2): 2 (3): [5] [0] 3 (4): [2] 4 (5): [3] 5 (6): [4] [0] 无向图G2的邻接表为: 0 (1): [3] [1] 1 (2): [5] [2] [0] 2 (3): [4] [1] 3 (4): [4] [0] 4 (5): [3] [5] [2] 5 (6): [4] [1] *************************************** 建立一个有向网的邻接表G3: 输入顶点数和边(弧)数vexnum arcnum:4 4↙ 按某种顺序输入4个顶点的值: 1 2 3 4↙ 输入图中4条边(弧)和权的信息u v w: 1 2 7 1 3 1 3 4 5 4 1 9↙ 建立一个无向网的邻接表G4: 输入顶点数和边(弧)数vexnum arcnum:5 5↙ 按某种顺序输入5个顶点的值: 1 2 3 4 5↙ 输入图中5条边(弧)和权的信息u v w: 1 2 9 4 1 8 4 2 3 4 5 1 3 5 12↙ 有向网G3的邻接表为: 0 (1): [2,1] [1,7] 1 (2): 2 (3): [3,5] 3 (4): [0,9] 无向网G4的邻接表为: 0 (1): [3,8] [1,9] 1 (2): [3,3] [0,9] 2 (3): [4,12] 3 (4): [4,1] [1,3] [0,8] 4 (5): [2,12] [3,1] 说明： （1）程序演示中建立的是图7.1、图7.3中4个图的一种邻接表表示：G1.vertices、G2.vertices、G3.vertices和G4.vertices。 （2）在程序显示的结果中，第一列为顶点的下标，第二列为图中所有顶点的值。对于图，单链表中的每一项表示该顶点的邻接点的下标；对于网，单链表中的每一项表示该顶点的邻接点的下标值和相应边（弧）的权值。 （3）在建立邻接表时，由于输入的是顶点信息，所以要先通过查找求得该顶点在图中的位置，再将相应结点插入到对应单链表的首部，所以，该操作的时间复杂度为O(n*e)。 7.2.3有向图的十字链表表示法 十字链表是有向图的另一种链式存储结构，该方法是将有向图的邻接表和逆邻接表结合起来得到的一种链表。 1．十字链表的定义 类似邻接表，在十字链表中包含链表的头结点和弧结点两种类型的结点，图7.13给出十字链结点结构的示图。 其中，头结点包含顶点信息域(data)、指向以该顶点为弧头的第一个弧结点的指针域(firstin)、指向以该顶点为弧尾的第一个弧结点的指针域(firstout)，表的所有头结点以顺序存储。弧结点包含表示弧尾顶点下标的尾域(tailvex)、表示弧头顶点下标的头域(headvex)、指向弧头相同的下一条弧的指针域(hlink)、指向弧尾相同的下一条弧的指针域(tlink)、弧的信息（如权 -.180.- 第7章 图结构 值）域(info)。 例如，图7.14给出有向图的一种十字链表表示。 如果将有向图的邻接矩阵看成是稀疏矩阵的话，则十字链表也可以看成是邻接矩阵的十字链表存储结构。在有向图的十字链表表示中，链表的头结点之间是顺序存储结构，弧结点所在的链表是非循环链表，结点之间的相对位置自然形成，不一定按顶点序列号有序。由此可见，有向图的十字链表表示方式是不唯一的。 2．十字链表的存储表示与实现 (1)十字链表存储结构的类型定义 下面分别给出十字链弧结点(ArcBox)、顶点结点(OLVexNode)、十字链表(OLGraph)的类型定义。 struct ArcBox{ //弧结点的结构定义 int tailvex,headvex; //定义弧尾和弧头顶点的位置 ArcBox *hlink,*tlink; //弧头相同、弧尾相同的弧的链域 int weight; //定义有向网中弧的权值 }; struct OLVexNode{ //顶点结点结构定义 VType data; //顶点信息 ArcBox *firstin,*firstout; //分别指向顶点的第一条入弧和出弧 }; struct OLGraph{ //定义十字链表类型 OLVexNode *xlist; //链表头结点数组指针 int vexnum,arcnum; //有向图的顶点数和弧数 GKind kind; }; (2)十字链表的查找操作 函数int LocateVex_OLG(OLGraph G,VType u) 返回顶点u在图G中的位置，如果查找失败则返回0值。 int LocateVex_OLG(OLGraph G,VType u) { int i; for(i=0;i -.181.- 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《第7章 图结构》习题解答(3)在线全文阅读。
相关推荐：