第七章 图(2).ppt

第七章图 图的定义图的存储方式图的连通性最小生成树有向无环图的应用 7 2图的存储方式 1 邻接矩阵表示法 2 邻接表表示法 邻接表 AdjacencyList 表示法实际上是图的一种链式存储结构 基本思想 为图中每个顶点建立一个单链表 第i个单链表中的结点表示依附于顶点Vi的边 有向图中指以Vi为尾的弧 邻接表的结点结构 1 顶点表 由所有表顶点以顺序结构 向量 的形式存储 以便可以随机访问任一顶点的单链表 顶点表结构由两部分构成 数据域 vexdata 用于存储顶点的名或其它有关信息 链域 firstarc 用于指向链表中第一个顶点 即与顶点vi邻接的第一个邻接点 2 边表 由表示图中顶点间邻接关系的n个边链表组成 它由三部分组成 邻接点域 adjvex 用于存放与顶点vi相邻接的顶点在图中的位置 链域 nextarc 用于指向与顶点vi相关联的下一条边或弧的结点 数据域 info 用于存放与边或弧相关的信息 如赋权图中每条边或弧的权值等 无向图的邻接表 同一个顶点发出的边链接在同一个边链表中 每一个链结点代表一条边 边结点 如何求顶点i的度 顶点i的边表中结点的个数 有向图的邻接表 可见 在有向图的邻接表中不易找到指向该顶点的弧 如何求顶点i的出度 顶点i的出边表中结点的个数 如何求顶点i的入度 各顶点的出边表中以顶点i为终点的结点个数 有向图的逆邻接表 在有向图的邻接表中 对每个顶点 链接的是指向该顶点的弧 网的邻接表 邻接表的结点结构 defineMaxVertexNum100typedefstructnode intadjvex 邻接点域 存放与Vi邻接的点在表头数组中的位置structnode next 链域 指示下一条边或弧intinfo EdgeNode typedefstructtnode 表头接点 VertexTypevexdata 存放顶点信息EdgeNode firstarc 指示第一个邻接点 VertexNode typedefVertexNodeAdjList MaxVertexNum AdjList是邻接表类型typedefstruct 对于简单的应用 无须定义此类型 可直接使用AdjList类型 AdjListadjlist 邻接表intn e 图中当前顶点数和边数 ALGraph voidCreatALGraph ALGraph G inti j k EdgeNode s printf 请输入顶点个数和边的个数 scanf d d 建立边表for k 0 kn k printf 请输入边的两个顶点 scanf d d 将s插入顶点Vj的边表头部 邻接表表示法特点 1 无向图邻接表边结点数是边数的两倍 2 顶点vi的度 在无向图中等于第i个链表中的结点数 在有向图邻接表中 第i行的结点数等于顶点i的出度 在有向图逆邻接表中 第i行的结点数等于顶点i的入度 3 在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点 4 设存储顶点的一维数组大小为n 图的顶点数n G占用存储空间 n e G占用存储空间与它的顶点数和边数有关 适用于边稀疏的图 3 有向图的十字链表表示法 十字链表 OrthogonalList 是有向图的另一种链式存储结构 我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表 有向图中的每一条弧对应十字链表中的一个弧结点 同时有向图中的每个顶点在十字链表中对应有一个结点 叫做顶点结点 弧的结点结构 弧尾顶点位置弧头顶点位置弧的相关信息 指向弧头相同的下一条弧 指向弧尾相同的下一条弧 typedefstructnode 弧的结构表示inttailvex headvex InfoType info structnode hlink tlink EdgeNode tailvexheadvexhlinktlinkinfo 顶点的结点结构 datafirstinfirstout 指向该顶点的第一条入弧 指向该顶点的第一条出弧 typedefstructvnode 顶点的结构表示VertexTypedata EdgeNode firstin firstout VertexNode 0 1 2 3 十字链表的优点 在十字链表中既能够很容易地找到以vi为尾的弧 也能够容易地找到以vi为头的弧 因此对于有向图 若采用十字链表作为存储结构 则很容易求出顶点vi的度 4 无向图的邻接多重表表示法 邻