图的基本概念、存储、遍历ppt课件.ppt

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

1、图的基本概念山东省青岛第二中学臧方青1、图的的定义如果数据元素集合D中的各元素之间存在任意的前驱和后继关系R，则此数据结构G=（D，R）称为图。如果将数据元素抽象为结点，元素之间的先后关系用边表示，则图亦可以表示为G=（V，E），其中V是结点的有穷（非空）集合，E为边的集合。如果元素a是元素b的前驱，这种先后关系对应的边用(a，b)表示，即(a，b)∈E。图可以分为无向图和有向图两种形式。2：图结构的基本概念（1)图：一个图G由两个集合V和E组成，记为G=（V，E）。图的数据元素通常称为顶点（vertex），V是有限的非空顶点集，E是两个顶点之间的关系的有限集，分

2、别记为V（G）、E（G）。（2)有向图：任意∈E（G），表示从顶点x到顶点y的一条弧（arc），且称x为弧尾（tail）或初始点，称y为弧头（head）或终端点。此时E（G）中的元素是有序的（即≠），称G为有向图（digraph）。（3）无向图：任意（x，y）∈E（G），表示x和y这两个顶点之间有一条边（edge）。此时E（G）中的元素是无序的（即（x，y）=（y，x）），称G为无向图（undigraph）。（4）图的顶点和边的性质1：设图G中有n个顶点、e条边，即n=︱V（G）︳，e=︱E（G）︳，则（1）对无向图，0≤e≤n(n-

3、1)/2；（2）对有向图，0≤e≤n(n-1)。（5）完全图、有向完全图、稀疏图、稠密图：有n(n-1)/2条边的无向图称为完全图（completedgraph）；有n(n-1)条边的有向图称为有向完全图；边或弧很少（如e

4、G’的子图（subgraph）。（8）邻接点、度：对于无向图G=（V，E），如果边（v，v’）∈E（G）,则称顶点v和v’互为邻接点（adjacent），即v和v’相邻接。边（v，v’）依附于顶点v和v’，或者说边（v，v’）和顶点v、v’相关联。对于无向图G=（V，E），v∈V（G），顶点v的度（degree）是和v相关联的边的数目，记为TD（v）。对于有向图G=（V，E），如果弧∈E（G），则称顶点v邻接到v’，顶点v’邻接自顶点v，弧和顶点v、v’相关联。对于有向图G=（V，E），v∈V（G），以顶点v为头的弧的数目称为v的入度（in

5、-degree），记为ID（v）；以v为尾的弧的数目称为v的出度(out-degree)，记为OD（v）；顶点v的度为TD（v）=ID（v）+OD（v）。（9）图的顶点和边的性质2：一个有n个顶点v1，v2，…，vn，e条边或弧的图，满足如下关系：（10）路径、回路、环：无向图G=（V，E）中从顶点v到顶点v’的路径（path）是一个顶点序列（v=vi0，vi1，…，vin=v’），其中，（vi(j-1)，vij）∈E（G），1≤j≤n。如果G是有向图，则路径也是有向的，顶点序列应满足∈E（G），1≤j≤n。路径的长度是路径上边或弧的数目

6、或它们的权之和。第1个顶点和最后1个顶点相同的路径称为回路或环(cycle)。序列中顶点不重复出现的路径称为简单路径。除了第1个顶点和最后1个顶点相同外，其余顶点不重复出现的回路，称为简单回路或简单环。（11）连通、连通图、连通分量：在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。如果图中任意两个顶点之间都存在路径，则称该无向图G为连通图。连通分量指的是图中的极大连通子图。在有向图G中，如果对于每一对顶点v、v’，从v到v’和从v’到v都存在路径，则称G是强连通图。有向图的极大强连通子图称为有向图的强连通分量。3、图的存储结构图的邻接矩阵表示法邻

7、接矩阵是表示结点间相邻关系的矩阵。若G=（V，E）是一个具有n个结点的图，用邻接矩阵表示法来表示时，除了用邻接矩阵中的n*n个元素存储顶点间相邻关系外，往往还需要另设一个向量存储n个顶点的信息。因此其类型定义如下：const vnum=…;{图的顶点数}　type adj=0..1;　　adjmatrix=arry[1..vnum,1..vnum]ofadj;{邻接矩阵matrix：英文（在数学中）矩阵}　　graph=record　　　　　　vexs:array[1..vnum]ofvextype;{顶点向量}　　　　　　arcs:adjmatrix;

8、{邻接矩阵