自考数据结构02142-第五章详解.ppt

第五章 图 5.1 图的基本概念 5.2 图的存储结构 5.3 图的遍历 5.4 图的应用 一、图的定义 图G —— 是由集合V和E组成，记成G=（V，E） 其中： V — 顶点集（非空）； E — 边集（可空）。 边是顶点的有序对或无序对。 （边反映了两顶点之间的关系） ●有向图：边是顶点的有序对的图。 （图中每条边都用箭头指明了方向） ●无向图：边是顶点的无序对的图。 5.1 图的基本概念 例： V(G1)={ 1，2，3，4 } E(G1)={ (1,2)，(1,3)，(1,4)，(2,3)， (2,4)，(3,4) } V(G2)={ 1，2，3，4 ，5，6，7 } E(G2)={ (1,2)，(1,3)，(2,4)，(2,5)， (3,6)，(3,7) } V(G3)={ 1，2，3 } E(G3)={ 1,2，2,1，2,3 } 注：1）边集可空； 2）边集中不允许出现相同的边。 二、图的基本术语 ●顶点(Vertex)——图中的数据元素； ●Vi,Vj——有向图中,顶点Vi到 顶点Vj的边,也称弧； ●完全图—— 无向完全图：边数=n*(n-1)/2的无向图； 有向完全图：边数=n*(n-1)的有向图； (顶点数n) ●权——图的边附带的数值（可表示从一个顶点到另一 顶点的距离、代价等） ●子图——图G和G′,若有V(G′)? V(G)和 E(G′)? E(G), 则称 G′为图G的子图。 ●邻接——若(Vi,Vj)∈E(G)，则称Vi和Vj互为邻接点; ●关联——若(Vi,Vj)∈E(G)，则称边(Vi,Vj)关联于顶 点Vi和Vj; 注：1）邻接是指顶点之间的关系，而关联是指边与 顶点间的关系。 2）若弧Vi,Vj∈E(G)，则称Vj是Vi的邻接点 ●度— 无向图：顶点Vi的度为与Vi相关联的边的个数； D(Vi) 有向图 出度:顶点Vi的出度为以Vi为尾的出边数； OD(Vi) 入度:顶点Vi的入度为以Vi为头的入边数； ID(Vi) 度:有向图的度=入度+出度； D(Vi) D(Vi)= OD(Vi)+ID(Vi) 注：图中边数e与顶点的度的关系 （一边带二度，两度组成一边） ●路径——图中，顶点Vp至顶点Vq的路径是顶点序列 { Vp,Vi1,Vi2,…,Vin,Vq } 且 对无向图，边(Vp,Vi1),(Vi1,Vi2),…,(Vin,Vq)∈VR(G); 对有向图，弧Vp,Vi1,Vi1,Vi2,…,Vin,Vq∈VR(G); ●路径长度——路径上边或弧的数目； ●简单路径——序列中顶点不重复出现的路径； ●回路—第一个和最后一个顶点相同的路径，也称环； ●简单回路—除第一个和最后一个外，其余各顶 点均不相同的回路； 注：回路中可以有多个圈，而简单回路只能有一个圈。 ●连通——无向图中，若从顶点Vi到Vj顶点有路径，则称Vi和Vj是连通的。 ●连通图和连通分量 针对无向图而言 定 义 例 无 向 图 连通图 连通 分量 图中每对顶点 间都连通; Vi～Vj 图中极大的连通子图（再扩大一点就不连通） ① ① ②　　③ ②　 　 ③ ④　 ④ ⑤ ⑥ ⑦ (G1) (G2) ① ⑤ （G3不是连通 ②　　③ ⑥ 　 图，但它有两 ④ ⑦ 个连通分量） (G3 ) ⑧ 有向图 强连 通图 强连通分量 图中任意一对顶点Vi和Vj都有顶点Vi到顶点Vj的路径，也有从vj到vi的路径，两个顶点间双向连通。 有向图的极大强连通子图。 ① ② ③ ① ① ② ④ ② ④ ③ ③ (G4)