《图的定义和术语》PPT课件

《《图的定义和术语》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章图6.1图的定义和术语6.2图的存储结构6.3图的遍历6.4最小生成树6.5最短路径6.6拓扑排序6.7典型题例6.8实训例题6.1图的定义和术语6．1．1图的定义图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E)其中：V(G)是顶点的非空穷集合有穷集合E(G)是用顶点对表示的边（Edge）的有穷集合，可以为空。无向图——若图G中表示边的顶点对是无序的（称无向边），则称图G为无向图。通常用(vi，vj)表示顶点vi和vj间的无向边。有向图——若图G中表示边的顶

2、点对是有序的（称有向边），则称图G为有向图。通常用表示从顶点vi到顶点vj的有向边，有向边也称为弧，顶点vi称为弧尾（或初始点），顶点vj称为弧头（或终端点），用由弧尾指向弧头的箭头形象地表示弧。例如图6.1所示，G1是无向图，其中，V={v0，v1，v2，v3，v4}，E={(v0，v1)，(v0，v3)，(v0，v4)，(v1，v4)，(v1，v2)，(v2，v4)，(v3，v4)}；G2是有向图，其中，V={v0，v1，v2，v3}，E={，

3、，v2>，，}。(a)图G1(b)图G2图6.1图的示例v4v3v0v3v0v1v2v1v26.1.2图的基本术语邻接点——在无向图G＝(V，E)中，若边(vi，vj)∈E，则称顶点vi和vj互为邻接点（Adjacent），或vi和vj相邻接，并称边(vi，vj)与顶点vi和vj相关联，或者说边(vi，vj)依附于顶点vi，vj。在有向图G＝（V，E）中，若弧E，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，并称弧和顶点vi，vj相关

4、联。顶点的度、入度和出度——顶点vi的度（Degree）是图中与vi相关联的边的数目，记为TD(vi)。对于有向图，顶点vi的度等于该顶点的入度和出度之和，即TD（vi）＝ID（vi）＋OD（vi）。其中，顶点vi的入度（InDegree）ID（vi），是以vi为弧头的弧的数目；顶点vi的出度（OutDegree）OD（vi）是以vi为弧尾的弧的数目。完全图、稠密图、稀疏图——若无向图中有n(n–1)条边，即图中每对顶点之间都有一条边，则称该无向图为无向完全图。若有向图中有n(n–1)条弧，即图

5、中每对顶点之间都有方向相反的两条弧，则称该有向图为有向完全图。有很少条边或弧（e

6、是有向的，且〈vij–1，vij〉∈E，１≤j≤m。路径上边或弧的数目称为路径长度。如果路径的起点和终点相同（即v＝v‘），则称此路径为回路或环（Cycle）。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。(a)图6.1中G1的子图v0v4v0v1v2v4v3v0v1v0v1v0v3v0v1v2(b)图6.1中G2的子图图6.3子图示例连通图、连通分量：在无向图G中，若从顶点vi到顶点vj(i≠j)有路径相通，则称vi和

7、vj是连通的。如果图中任意两个顶点vi和vj(i≠j)都是连通的，则称该图是连通图（ConnectedGraph）。无向图中极大连通子图称为连通分量（ConnectedComponent）。强连通图、强连通分量：在有向图中，若任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi都有路径相通，则称该有向图为强连通图，例如图6.2中G4就是强连通图。有向图中的极大强连通子图称为该有向图的强连通分量。v5图6.4无向图及其连通分量v4v3v0v1v2(a)无向图G5v7v6(b)G5的三个连通分

8、量v4v3v0v1v2v5v7v6v3v0v1v2图6.5有向图G2的两个强连通分量(a)(b)权、网：图的每条边或弧上常常附上一个具有一定意义的数值，这种与边或弧相关的数值称为该边（弧）的权（Weight）。边或弧上带权的连通图称为网（Network）。如图6.6所示。10706030205090图6.6网G6示例v1v4v0v2v36．2图的存储结构6．2．1邻接矩阵1．邻接矩阵这种存储结构采用两个数组来表示图：一个是一维数组，存储图中的所有顶点的信息；另一个是二维数组即邻接矩阵，存储顶点之