图的基本概念和存储结构课件.ppt

《图的基本概念和存储结构课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图和图的存储结构图的定义和术语图的存储表示小结和作业创建图图和图的存储结构1.图的结构定义2.图的名词和术语3.图的基本操作图的结构定义谓词P(v,w)定义了弧的意义或信息。图是由一个顶点集V和一个弧集R构成的数据结构。Graph=(V,R)R＝{

2、v,w∈V且P(v,w)}表示从v到w的一条弧(Arc)，称v为弧尾(tail)，w为弧头(head)。图的结构定义—有向图如果“弧”是有方向的，则称由顶点集和弧集构成的图为有向图。EACBD例如:G1=(V1,R1)V1={A,B,C,D,E}R1={,,,,

3、>,,}图的结构定义—无向图若R必有R,则以无序对(v,w)代替这两个有序对，称(v,w)为顶点v和顶点w之间存在一条边。上述这种由顶点集和边集构成的图称作无向图。图的结构定义—无向图例如:G2=(V2,R2)BCAFEDV2={A,B,C,D,E,F}R2={(A,B),(A,E),(B,E),(B,F),(C,D),(C,F)(D,F}名词和术语1）子图、网2）完全图、稀疏图、稠密图3）邻接点、度、入度、出度4）路径、路径长度、简单路径、简单回路5）连通图、连通分量、强连通图、强连通分量6）生成树、生成森林名词和术语1）子图设图G=(V

4、,R)和图G=(V,R),且VV,RR,则称G为G的子图。EACBDEACBDB名词和术语2）网弧或边带权的图分别称作有向网或无向网。ABECD1597211132名词和术语2）完全图、稀疏图、稠密图假设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图;含有e=n(n-1)条弧的有向图称作有向完全图;若边或弧的个数e

5、EB名词和术语3）邻接点、度、入度、出度例如:TD(B)=3TD(A)=2ACDFEB右侧图中的无向图名词和术语3）邻接点、度、入度、出度ABECD顶点的出度:以顶点v为弧尾的弧的数目;记为OD（v）对于右图所示的有向图来说，由于弧有方向性，则有入度和出度之分名词和术语3）邻接点、度、入度、出度ABECD顶点的入度:以顶点v为弧头的弧的数目，记为ID（v）顶点的度(TD)=出度(OD)+入度(ID)ID(B)=2OD(B)=1TD(B)=3名词和术语ABECD4）路径、路径长度、简单路径、简单回路路径：设图G=(V,R)中的一个顶点序列{u=vi,0,vi,1,…,vi,m=w}中，

6、(vi,j-1,vi,j)R，1≤j≤m,则称从顶点u到顶点w之间存在一条路径。路径长度：路径上边的数目。如:从A到D长度为3的路径{A,B,C,D}名词和术语4）路径、路径长度、简单路径、简单回路简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同的路径。ABECD名词和术语5）连通图、连通分量、强连通图、强连通分量连通图：若无向图G中任意两个顶点之间都有路径相通，则称此图为连通图;BACDFE名词和术语5）连通图、连通分量、强连通图、强连通分量连通分量：若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。BACDFE名词和术语5）连通

7、图、连通分量、强连通图、强连通分量强连通图：若有向图任意两个顶点之间都存在一条有向路径，则称为强连通图。ABECD否则，其各个强连通子图称作它的强连通分量。ABECD名词和术语6）生成树、生成森林连通图的生成树：是一个极小连通子图，它含有图中的全部顶点，但只有足以构成一棵树的n-1条边。BACDFEBACDFE名词和术语6）生成树、生成森林生成森林：对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。BACDFEBAECDF基本操作1.结构的建立和销毁3.插入或删除顶点5.对邻接点的操作2.对顶点的访问操作6.遍历4.插入和删除弧基本操作CreatGraph(&G,V

8、,R)://按定义(V,R)构造图DestroyGraph(&G)://销毁图1.结构的建立和销毁基本操作2.对顶点的访问操作LocateVex(G,u);//若G中存在顶点u，则返回该顶点在//图中“位置”；否则返回其它信息。GetVex(G,v);//返回v的值。PutVex(&G,v,value);//对v赋值value。基本操作3.插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v);//删除G中顶