06-图说课稿市公开课一等奖课件名师大赛获奖课件.pptx

;15;15;第7章图;一、图的构造定义;ADTGraph{;;;3.若v,w?VR必有w,v

?VR,则称(v,w)为顶点v和顶点w之间存在一条边。;A;假设图中有n个顶点，e条边，则;假若顶点v和顶点w之间存在一条边，

则称顶点v和w互为邻接点7，;顶点的出度10:以顶点v为弧尾的弧的数目；;设图G=(V,{VR})中的一种顶点序列

{u=vi,0,vi,1,…,vi,m=w}中，(vi,j-1,vi,j)?VR1≤j≤m,

则称从顶点u到顶点w之间存在一条途径12。;例;若图G中任意两个顶点之间都有途径相通，则称此图为连通图16；;若任意两个顶点之间都存在一条有向途径，则称此有向图为强连通图18。;生成树20

包含无向图G全部顶点的的极小连通子图称为G的生成树

极小连通子图意思是：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，

若T是G的生成树当且仅当T满足以下条件

T是G的连通子图

T包含G的全部顶点

T中无回路;假设一种连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一种极小连通子图，称该极小连通子图为此连通图的生成树20。;图

;巩固练习(1);巩固练习(2);对于下面两个图，求出：

无向图中每个顶点的度，有向图中每个顶点的入度，出度和度。

与否是连通图/强连通图，如果不是，画出连通分量/强连通分量。;7.2图的存储构造;7.2图的存储表达;1、邻接矩阵表达法（数组表达法）;Aij={;有向图的邻接矩阵不一定为对称矩阵！;？借助邻接矩阵与否能够判断：

1.任意两个顶点之间与否相连？

2.各个顶点的度是多少？;类似地能够定义网的邻接矩阵为：;;特点：;邻接矩阵表达法中图的存储表达

#definen6/*图的顶点数*/

#definee8/*图的边数*/

typedefcharvextype;/*顶点的数据类型*/

typedeffloatadjtype;/*权值类型*/

typedefstruct

{vextypevexs[n];

adjtypearcs[n][n];

}graph;;;特点：;二、邻接表

实现：顶点：普通按编号次序将顶点数据存储在一维数组中；

关联同一顶点的边：用线性链表存储。即为图中每个顶点建

立一种单链表，第i个单链表中的结点表达依附于顶点Vi的边;例;特点

无向图设存储顶点的一维??组大小为m(m?图的顶点数n),图的边数为e，G占用存储空间为：m+2*e。(有向图??)G占用存储空间与G的顶点数、边数都有关；合用于边稀疏的图;特点;特点

无向图中顶点Vi的度为第i个单链表中的结点数

无向图在G中增减边：要在两个单链表插入、删除结点；有向图要几个?();例;逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表

;;巩固练习;巩固练习;巩固练习;例2：已知某网的邻接（出边）表，请画出该网络。;邻接表;有向图的十字链表表达法;3.邻接表;有向图的十字链表表达法(C语言实现);例;无向图的邻接多重表表达法;例