第七章图的表示法

第七章图图的基本概念及术语图的表示法图的遍历图的应用本章目标7.2图的存储结构邻接矩阵表示法邻接表表示法邻接多重表十字链表设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A

[n][n]，定义：故，图的邻接矩阵表示法也称为：数组表示法7.2.1邻接矩阵(AdjacencyMatrix)无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。0123012863129542031网的邻接矩阵1.无向图的邻接矩阵是对称矩阵，所以可采用压缩存储法（下三角），其存储空间只需＿＿＿＿＿。2.有向图的邻接矩阵一定不是对称矩阵，对吗？3.有向图的邻接矩阵需要＿＿＿＿＿＿个存储空间。练习n(n-1)/2n2不对！有可能是对称矩阵在有向图中,统计第i

行

1的个数可得顶点

i

的出度，统计第j列

1的个数可得顶点j

的入度。在无向图中,统计第i

行(列)1的个数可得顶点i

的度。邻接矩阵的C语言描述采用邻接矩阵表示法创建有向网－P205见算法7.1思考：如何采用邻接矩阵表示法创建有向网的其它操作？？？只须将实现有向网中边的权值表示方式按如下修改即可

每条边的边权规定为1，边权为0时表示无边用邻接矩阵实现有向图边权规定为1，边权为0时表示无边一条边可看作两条相反方向的弧，如：-----插入一条边(i,j)的操作：用邻接矩阵实现无向图G->arcs[i][j].adj=1;G->arcs[j][i].adj=1;优点：易于操作缺点：对于稀疏图来讲，该方法极浪费邻接矩阵表示法解决方法：邻接表表示法邻接矩阵表示法内容结束之后回邻接表(AdjacencyList)表示法ABCDvexdata

firstarcABCD0123adjvex

nextarc

130210无向图的邻接表表头结点表边表表头结点表下标可从1开始也可从0开始ABCABC012

ABC012102

011有向图的邻接表邻接表(出边表)逆邻接表(入边表)vexdata

firstarcadjvex

nextarcvexdata

firstarcadjvex

nextarcBACD69528ABCD0123

1

53

62

83

2(出边表)(顶点表)有向网(带权图)的邻接表1

9vexdata

firstarcadjvexinfonextarc优点：不必存储不存在的边（弧）缺点：结构较复杂如建立逆邻接表，方便计算入度，但实际上，一条边需分别在邻接表与逆邻接表中存储邻接表表示法解决方法：十字链表（优点一条弧只被存放一次）

十字链表“结点结构”之后回弧结点：0312info35189013tailvex=0headvex=1hlink=弧＜1,3＞地址31tlink=弧＜0,2＞地址02info存储弧的相关信息：如权值3顶点结点：031B35189A1DDA0231B123D1firstin=弧＜1,0＞地址firstout=弧＜0,2＞地址data存储与顶点有关的信息,如：名字A

十字链表1.“图例”后回并练习2.形式化定义与算法作图方法：1.先画出顶点结点（数组形式）2.画出所有弧结点（刚弧尾将各弧结点放置在对应的顶点结点后面）3.连线是有向图的一种链式存储结点结构优点：计算出度、入度十分方便缺点：结构较复杂十字链表表示法

邻接多重表内容结束后回是无向图的一种存储结构优点：提供更为方便的边处理信息，如：

比较无向图的邻接表表示法中，每一条边在邻