吉林大学：《数据结构》课程电子教案（PPT课件）第七章 图

第七章 图

第七章 图

7.1图的概念 7.1.1 图的定义 。定义：图G由两个集合V和E组成。 记为G=(V,E) 。有向图和无向图

7.1 图的概念 7.1.1 图的定义 ● 定义：图G由两个集合V和E组成。 记为G = (V , E) ● 有向图和无向图

7.1.2 图的基本术语 ①端点和邻接点：在一个无向图中，若存在一条 边(V,v),则称v1,v为此边的两个端点，并称 它们互为邻接点。 ②顶点的度、入度、出度： 在无向图中顶点的度定义为以该顶点为一 个端点的边的数目，称为顶点的度。 若G是有向图，则v的出度是以v为始点的边 的个数，v的入度是以v为终点的边的个数。 e=>D(v:) i=0

7.1.2 图的基本术语 ① 端点和邻接点：在一个无向图中，若存在一条 边(vi,vj)，则称vi,vj为此边的两个端点，并称 它们互为邻接点。 ② 顶点的度、入度、出度 ： 在无向图中顶点V的度定义为以该顶点为一 个端点的边的数目，称为顶点的度。 若G是有向图，则v的出度是以v为始点的边 的个数，v的入度是以v为终点的边的个数。 i=0 n－1 e = ½ ∑ D(vi)

③完全图：有向完全图（边数=n*(n-1) 无向完全图（边数=1/2*n*(n-1)) ④子图：G,H是图，如果V(H)≤V(G), E(H)CE(G),则称H是G的子图，G是H的 母图。如果H是G的子图，并且V(H)= V(G),则称H为G的支撑子图

③ 完全图 ：有向完全图(边数＝n*(n-1)) 无向完全图(边数＝1/2*n*(n-1)) ④ 子图 ：G，H是图，如果V(H) V(G)， E(H) E(G)，则称H是G的子图，G是H的 母图。如果H是G的子图，并且V(H) = V(G)，则称H为G的支撑子图。  

⑤路径和回路 : 设G是图，若存在一个顶点序列vp,V V2,,Vg使得,, ≤Vg1,Vg或(VpV),（y1,V2,,(Vg41,g) 属于E(G),则称v,到v存在一条路径。 路径的长度是该路径上的边的个数。 如果一条路径上除了起点和终点可以相同外， 再不能有相同的顶点，则称此路径为简单路径。 如果一条简单路径的起点和终点相同，且 路径长度大于等于2，则称之为简单回路

⑤ 路径和回路 ： 设G是图，若存在一个顶点序列vp，v1， v2，…， vq， 使得，，…， 或 ( vp ,v1 )， ( v1 ,v2 )，…， ( vq-1 ,vq ) 属于E(G)，则称vp到vq存在一条路径。 路径的长度是该路径上的边的个数。 如果一条路径上除了起点和终点可以相同外， 再不能有相同的顶点，则称此路径为简单路径。 如果一条简单路径的起点和终点相同，且 路径长度大于等于2，则称之为简单回路

⑥可及和连通分量： 若从顶点v到顶点v有路径，则称v与V可及（连 通的)。 ◆ 若G为无向图，且V(G)中任意两顶点都可及， 则称G为连通图。 无向图G的极大连通子图称为G的连通分量。 ⑦强连通图和强连通分量： 若G为有向图，且对于V(G)中任意两个不同的 顶点v和y,v与y可及，V与v也可及，则称 G为强连通图。 有向图G的极大强连通子图称为G的强连通分量

⑥ 可及和连通分量 ：  若从顶点vi到顶点vj有路径，则称vi与vj可及(连 通的）。  若G为无向图，且V(G)中任意两顶点都可及， 则称G为连通图。  无向图G的极大连通子图称为G的连通分量。 ⑦ 强连通图和强连通分量 :  若G为有向图，且对于V(G)中任意两个不同的 顶点vi和vj ， vi与vj可及， vj与vi也可及，则称 G为强连通图。  有向图G的极大强连通子图称为G的强连通分量

⑧权和网： ·在一个图中，每条边可以标上具有某种含义的 数值，此数值称为该边的权。 边上带有权的图称做带权图（网）

⑧ 权和网：  在一个图中，每条边可以标上具有某种含义的 数值，此数值称为该边的权。  边上带有权的图称做带权图（网）

7.2图的存储结构 7.2.1邻接矩阵 。定义：表示顶点之间相邻关系的矩阵叫邻接矩阵。 具有n个顶点的图G(W,E)是具有下列性质的n阶 方阵： to Ai,]= 若(，)或是E(G)中的边 若(v,)或不是E(G)中的边

7.2 图的存储结构 7.2.1 邻接矩阵 ● 定义:表示顶点之间相邻关系的矩阵叫邻接矩阵。 具有n个顶点的图G=(V,E)是具有下列性质的n阶 方阵： A[i,j]＝ 1 若(vi , vj)或是E(G)中的边 0 若(vi , vj)或不是E(G)中的边

·[例1]无向图的邻接矩阵 0123 0 0111 1 1001 2 100 1 3 111

 [例1]无向图的邻接矩阵 0 1 2 3 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 2 3 V0 V2 V3 V1

[例2]有向图的邻接矩阵 0123.4 001000 1 10001 2 2 01010 3 3 10000 4 00010

[例2]有向图的邻接矩阵 V0 V4 V3 V1 V2 0 1 2 3 4 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 2 3 4