第7章图要点解析.ppt

7.1 图的基本概念 权： 某些图的边具有与它相关的数, 称之为权。 这种带权图也称为网。 带权图的路径长度：为路径上各条边权值的总和。 7.2 图的存储结构 网的邻接矩阵 几点说明： 在vi邻接表中，各个边结点的链入顺序任意，视边结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。 当图中结点数较少且边数较多时(稠密图)，采用邻接矩阵效率较高；当图中结点数较多且边数较少时(稀 疏图），采用邻接表效率较高。 (1) 初始化函数 void InitAdjoin(adjlist GL) { int i; for ( i = 0 ; i MaxVertexNum; i++ ) GL[i] = NULL; } (2) 建立邻接表函数 void CreateAdjoin( adjlist GL, int n, char *s, int k1, int k2) { // k1=0 代表无向图否则为有向图, // k2 =0 代表无权图否则为带权图。 // s 存放边集。n为顶点数。 istrstream sin(s); char c1,c2,c3; int i, j; weightType w; edgenode *p; //将指向新申请的边结点 sinc1; //读入第一个字符 ‘{’ 7.3 图的遍历 有向图的十字邻接表: 每个边结点对应一条有向边，包含：边的起点，边的终点，权值，入边链域，出边链域。其中，入边链域用于指向同一个顶点的下一条入边结点，通过它把入边链接起来；出边链域用于指向同一个顶点的下一条出边结点，通过它把出边链接起来。表头向量中的每个分量包括两个域：入边表的表头指针域和出边表的表头指针域。 V0 V1 V2 V3 0 1 2 3 0 1 ^ 1 3 ^ 2 3 ^ ^ 3 0 ^ ^ 0 2 ^ ^ typedef struct Node { int adjvex; // 邻接点的位置 WeightType weight； //权值域，根据需要设立 struct Node *next; // 指向下一条边（弧） } edgenode; // 边结点 //定义图的邻接表结构类型 （没包含顶点信息） typedef edgenode *adjlist[ MaxVertexNum ]; 例如： adjlist GL; 图的邻接表表示法的C语言描述： V0 V1 V2 V3 V4 G2 V0 V1 V2 V3 G1 有向图G1 无向图G2 0 ^ 1 2 3 2 1 ^ 3 ^ 0 ^ 0 1 2 3 4 3 1 ^ 2 4 2 0 ^ 4 3 1 ^ 0 ^ 2 1 ^ 图G1和G2的邻接表 GL[i] adjvex next if ( k2==0 ) // 建立无权图 do { sinc1ic2jc3; p = (edgenode *) malloc(sizeof(edgenode)); p-adjvex=j; p-weight=1; //插入边结点 p-next = GL[i]; GL[i] = p; if (k1==0) { //对无向图，需再插入一个边结点 p = (edgenode *) malloc(sizeof(edgenode));