0图的存储结构一邻接矩阵 第七章图 算法描述 Status CreateGraph( Mgraph &G) //建立无向网的数组型存储结构 for( i=l; i G. vexnum; i++ scanf(&G.vexs[i]);//输入n个顶点的信息 for( i=li G. vexnum i++) for( j=li3<=G. vexnum; j++ G arcs[i][jI NULL //初始化 for(k=l; k <G arcum; k++) scanf(6v1,sv2,w);//输入一条边的信息,w为与边相关的权 i=L。 vErtex(G,v1) j= LocVertex(G,v2);//确定v1,v2在c中的位置 G arcs [i][j].ad]= wi G.arcs[订[i].ad=w//假设无其它和边相关的信息 // CreateGraph算法7.1 注,时间复杂度为o(n2+e·n) 第26页
第七章 图 第26页 算法描述 Status CreateGraph( Mgraph &G ) { //建立无向网的数组型存储结构 for( i=1; i <= G.vexnum; i++ ) scanf( &G.vexs[i] ); //输入n个顶点的信息 for( i=1; i <= G.vexnum; i++ ) for( j=1; j <= G.vexnum; j++ ) G.arcs[i][j] = ( ∞, NULL ); //初始化 for( k=1; k < G.arcnum; k++ ) { scanf( &v1, &v2, &w); //输入一条边的信息，w为与边相关的权 i = LocVertex( G, v1 ); j = LocVertex( G, v2 ); //确定v1,v2在G中的位置 G.arcs[i][j].adj = w; G.arcs[j][i].adj = w //假设无其它和边相关的信息 } } //CreateGraph 算 法 7.1 注. 时间复杂度为O(n2+e·n). ⚫ 图的存储结构 – 邻接矩阵
0图的存储结构一邻接矩阵 第七章图 说明 可在前述数组型存储结构下实现诸如 Firstaid (G,V)的基本操作。 先由 Loc Vertex(G,找到顶点ⅴ在G中的位置,即ⅴ 在一维数组vex中的序号i,则二维数组Arcs中第上 第一个ad域的值为1的分量所在列号,便为所求顶点v 的第一个邻接点在图G中的位置 同理,求 NextADJi(G,y)便为列之后第一个ad域的 值为1的分量所在列号 第27页
第七章 图 第27页 说明 可在前述数组型存储结构下实现诸如FirstADJ (G,v)的基本操作。 先由LocVertex(G,v)找到顶点v在G中的位置，即v 在一维数组vexs中的序号i，则二维数组Arcs中第i行上 第一个adj域的值为1的分量所在列号j，便为所求顶点v 的第一个邻接点在图G中的位置。 同理，求NextADJ(G,v)便为j列之后第一个adj域的 值为1的分量所在列号。 ⚫ 图的存储结构 – 邻接矩阵
第七章图 邻接表表示法 邻接表( Adjacency List)表示法类似于树的孩子链表表示法。它 是图的一种链式存储结构 对于图G中的每个顶点V,该方法把所有邻接于V的顶点链成 个单链表,这个单链表就称为该顶点V的邻接表 结点形式 (1)边或弧的结点 adjvex nextarc info adver:邻接域,指示与顶点V邻接的点在图中的位置 nextarc:链域,指示下一条边或弧的结点 info:数据域,存储和边或弧相关的信息 (2)顶点结点 vexdata firstarc vexdata:数据域,存储顶点V的名或其他有关信息 firstaid:链域,指向链表中第一个结点,这些顶点结点通常以 顺序结构(向量)的形式存储,以便随机地访问任 顶点的链表。 第28页
第七章 图 第28页 邻接表(Adjacency List)表示法类似于树的孩子链表表示法。它 是图的一种链式存储结构。 对于图G中的每个顶点Vi，该方法把所有邻接于Vi的顶点链成 一个单链表，这个单链表就称为该顶点Vi的邻接表。 结点形式 (1) 边或弧的结点 adjvex：邻接域，指示与顶点Vi邻接的点在图中的位置 nextarc：链域，指示下一条边或弧的结点 info：数据域，存储和边或弧相关的信息 (2) 顶点结点 vexdata：数据域，存储顶点Vi的名或其他有关信息 firstarc：链域，指向链表中第一个结点，这些顶点结点通 常以 顺序结构（向量）的形式存储，以便随机地访问任一 顶点的链表。 adjvex nextarc info vexdata firstarc 邻接表表示法
邻接表表示法 第七章图 一示例: 无向图G2 对无向图G2,若输入序对分别为1,2;1,4;2,3;2,5;34;3,5;可得 4 第29页
第七章 图 第29页 V1 4 2 ∧ V2 5 3 V3 5 4 V4 3 1 ∧ V5 3 2 ∧ 1 ∧ 2 ∧ 1 2 3 4 5 邻接表表示法 V1 V2 V4 V5 V3 无向图G2 对无向图G2，若输入序对分别为1,2; 1,4; 2,3; 2,5;3,4; 3,5；可得 示例：
邻接表表示法 第七章图 下面给出建立无向图的邻接表表示存储结构的算法 数据结构 define MAX VERTEX NUM 20 typedef struct ArcNode t int adver; 顶点的位置 truct ArcNode *nextarc 个顶点的指针 InfoType *info /其它信息 JArcNode typedef struct VNode VertexType data; 7/数据 ArcNode *firstarc /指向相邻顶点的链表 1 VNode, AdjList [MAX VERTEX NUM+l]i typedef structi AdjList vertices; //顶点向量 int vexnum, arcnumi int kind JALGraph; 第30页
第七章 图 第30页 下面给出建立无向图的邻接表表示存储结构的算法。 数据结构 #define MAX_VERTEX_NUM 20 typedef struct ArcNode{ int adjvex; //顶点的位置 struct ArcNode *nextarc; //下一个顶点的指针 InfoType *info; //其它信息 }ArcNode; typedef struct VNode{ VertexType data; //数据 ArcNode *firstarc; //指向相邻顶点的链表 }VNode, AdjList[MAX_VERTEX_NUM+1]; typedef struct{ AdjList vertices; //顶点向量 int vexnum, arcnum; int kind; }ALGraph; 邻接表表示法