图的定义和术语及存储结构.ppt

《图的定义和术语及存储结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程的内容：多对多（m:n)17.1基本术语7.2存储结构7.3图的遍历7.4图的连通性7.5图的应用第7章图27.1图的基本术语其中：V是G的顶点集合，是有穷非空集；VR＝{

2、v,w∈V且P(v,w)},是有穷集.问：当VR为空时，图G存在否？V=vertex图：记为Graph＝(V,VR)EACBD表示从v到w的一条弧，并称w为弧头，v为弧尾。P(v,w)定义了弧的意义或信息。答：还存在！但此时图G只有顶点。3EACBD例如:G=(V,VR)其中V={A,B,C,D,E}VR={,,,,,

3、>,}无向图：由顶点集和边集构成的图(“边”无方向）若VR必有VR,则称(v,w)为顶点v和顶点w之间存在一条边。有向图：由顶点集和弧集构成的图（“弧”是有方向的）4BCAFED例如:G=(V,VR)其中：V={A,B,C,D,E,F}VR={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}若n个顶点的无向图有n(n-1)/2条边,称为无向完全图若n个顶点的有向图有n(n-1)条边,称为有向完全图证明：①有向完全图有n(n-1)条边。证明：若是有向完全图，则n个顶点中的每个顶点都有一条弧指向其它n-1个顶点,因此总边数

4、=n(n-1)12345证明：从①可以直接推论出无向完全图的边数——因为无方向，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。②无向完全图有n(n-1)/2条边。1234例：判断下列4种图形各属什么类型？6稀疏图：稠密图：设有两个图G＝(V,E)和G’＝(V’,E’)。若V’V且E’E,则称图G’是图G的子图。子图：边较少的图。通常边数远少于nlogn边很多的图。无向图中，边数接近n(n-1)/2有向图中，边数接近n(n-1)BBCABECFABECF例如：7ABECF1597211132有向网或无向网是弧或边带权的图。邻接点：若边(v,w)∈VR，则顶点v和顶点w互为邻

5、接点。边(v,w)依附于顶点v和w，或者与顶点v,w相关联。顶点v的度：是和v相关联的边的数目,记为TD(v).顶点v的出度:以顶点v为尾的弧的数目;记为OD(v).顶点v的入度:以顶点v为头的弧的数目,记为ID(v).顶点的度(TD)=出度(OD)+入度(ID)问：当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？答：是树！而且是一棵有向树！8路径:设图G=(V,VR)中的一个顶点序列:v=vi,0,vi,1,…,vi,m=w中，(vi,j-1,vi,j)（或〈vi,j-1,vi,j〉）VR1≤j≤m,则称从顶点v到顶点w之间存在一条路径。路径长度：路径上边（或弧）

6、的数目。ABECF如:从A到F长度为3的路径{A,B,C,F}或{A，E，C，F}简单路径:指序列中顶点不重复出现的路径。简单回路:指序列中第一个顶点和最后一个顶点相同，其余顶点不重复出现的回路。9连通图：无向图G中任意两个顶点之间都有路径相连通。连通分量：非连通图中的极大连通子图。BACDFEBACDFE强连通图：在有向图中,每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径强连通分量：非强连通图中的极大强连通子图。ABECFABECF10生成树：v1v2v3v4生成森林：假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此

7、连通图的生成树。由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。（对有向或无向图均适用）11CreatGraph(&G,V,VR)//按定义(V,VR)构造图DestroyGraph(&G)//销毁图结构的建立和销毁对顶点的访问操作LocateVex(G,u)//若G中存在顶点u，则返回该顶点在图中“位置”，否则返回其它信息。GetVex(G,v)//返回v的值。PutVex(&G,v,value)//对v赋值value。结构的建立和销毁插入或删除顶点对邻接点的操作遍历插入或删除弧基本操作对顶点的访问操作12对邻接点的操作FirstAdjVex(G,v);//返回v的“第一个邻

8、接点”若该顶点在G中没有邻接点，则返回“空”。NextAdjVex(G,v,w);//返回v的（相对于w的）“下一个邻接点”。若w是v的最后一个邻接点，则返回“空”。插入或删除顶点InsertVex(&G,v);//在图G中增添新顶点v。DeleteVex(&G,v)；//删除G中顶点v及其相关的弧。13插入和删除弧InsertArc(&G,v,w);//在G中增添弧，若G是无向的，则还增添对称弧。DeleteA