图(一).

Presentation on theme: "图(一)."— Presentation transcript:

1 图(一)

2 主要内容 （1）图的定义和术语 （2）图的存储结构

3 图的概念和基本术语 图可以表示为G=( V, E ) V表示顶点的非空有限集合。 E表示两个顶点之间关系的集合。 顶点:图中的数据元素
B A C D V表示顶点的非空有限集合。 E表示两个顶点之间关系的集合。 图可以表示为G=( V, E ) V＝{vi| vi∈dataobject} E＝{( vi,vj)| vi, vj ∈V ∧P(vi, vj)} 其中，G表示一个图，V是图G中顶点的集合，E是图 G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之 间有一条直接连线，即偶对(vi,vj)表示一条边。

4 图的概念和基本术语 v1 v2 v3 v4 v5 在该图中： 集合V＝{v1,v2,v3,v4,v5}；
集合E＝(v1,v2),(v1,v4),(v2,v3),(v3,v4), (v3,v5),(v2,v5)}

5 图的概念和基本术语 v1 v2 v3 v4 v5 B A C D （1）无向图。在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。 （2）有向图。在一个图中，如果任意两个顶点构成的偶对（vi, vj）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。

6 图的概念和基本术语 在有向图中，<V1，V3>表示从V1到V3的一条弧。 V1为弧尾或初始点，V3为弧头或终端点。

7 图的概念和基本术语 G=( V, E ) 注意：在无向图中（V1，V3）和（V3，V1）的区别，
顶点集合V={V1 ， V2 ， V3 ， V4 } 弧的集合E={<V1 ，V3>, <V3 ，V4>, <V2 ，V4>, <V4，V1>} V1 V3 V2 V4 顶点集合V={V1 ， V2 ， V3 ， V4 } 边的集合E={(V1, V3), (V1, V2), (V1, V4),(V2, V4)} 注意：在无向图中（V1，V3）和（V3，V1）的区别， 以及在有向图中<V1，V3>与<V3，V1>的区别。

8 图的概念和基本术语 （3）顶点、边、弧、弧头、弧尾。 B A C D

9 图的概念和基本术语 完全图 稀疏图（边数<n×logn）和稠密图 有向完全图：有n×(n－1)条弧的有向图

10 图的概念和基本术语 邻接点 对于无向图G＝（V，E），如果边（V，V’）E，则称顶点V，V’互为邻接点
则称顶点V邻接到顶点V’，顶点V’邻接于顶点V V1 V3 V2 V4 无向图 V1 V3 V2 V4 有向图

11 图的概念和基本术语 子图：设有两个图G＝（V，E）和图G’＝（V’，E’），若V’V 且 E’ E ，则称G’为G的子图 A B C D

12 图的概念和基本术语 权：与图的边或弧相关的数。 网（或赋权图）：带权的图。 顶点的度（TD(V)）：依附于该顶点的边数或弧数。
出度(OD(V)):(仅对有向图)以该顶点为尾的弧数。 入度(ID(V)):(仅对有向图)以该顶点为头的弧数。 对于有向图，TD(V)=OD(V)＋TD(V) 3 5 B A C D B A C D 2 4 1 6

13 图的概念和基本术语 路径：是一个顶点序列。 路径长度:路径上边或弧的数目。 简单路径：表示路径的顶点序列中的顶点各不相同。
回路（环）：第一个顶点和最后一个顶点相同 （即V＝V’）的路径。 简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路。 3 5 A B C 2 4 1 6 D

14 图的概念和基本术语 连通的、连通图、连通分量。在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量。图 (a)中有两个连通分量，如图 (b)所示。

15 图的概念和基本术语 强连通图、强连通分量。对于有向图来说，若图中任意一对顶点vi 和vj(i≠j)均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。图a中有两个强连通分量，分别是{v1,v3,v4}和{v2}，如图b所示。

16 图的存储结构 最常用的存储表示形式： 邻接矩阵 邻接表

17 邻接矩阵表示法 存贮方式： 一个存储所有顶点信息的表（一维数组） 一个表示顶点之间边（弧）的邻接矩阵（二维数组）

18 邻接矩阵 V V V3 V4 V V V V V1 V3 V2 V4 有向图 V V V3 V4 V V V V V1 V3 V2 V4 无向图

19 邻接矩阵表示法的特点 无向图(网)的关系矩阵一定是对称矩阵。
无向图(网)的关系矩阵的第i行(或第i列)非零元素个数为第i个顶点的度D(vi)。 有向图的关系矩阵的第i行非零元素个数为第i个顶点的出度OD(vi)，第i列非零元素个数就是第i个顶点的入度ID(vi)。 比较容易确定图中任意两个顶点之间是否有边相连。 无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n^2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需 (n-1)=n(n-1)/2个单元。对稀疏图浪费空间。 A= V0 V2 V1 V3 19/26

20 图的邻接矩阵存储表示 #define MaxVertexNum 100 /*最大顶点数设为100*/
typedef char VertexType; /*顶点类型设为字符型*/ typedef int EdgeType; typedef struct { VertexType vexs[MaxVertexNum]; EdeType edges[MaxVertexNum][MaxVertexNum]; int n,e; }Mgragh;

21 // 建立一个图的邻接矩阵存储的算法如下：
void CreateMGraph(MGraph *G) {/*建立有向图G的邻接矩阵存储*/ int i,j,k,w; scanf("%d,%d",&(G->n),&(G->e));/*输入顶点数和边数*/ for (i=0;i<G->n;i++) scanf("%c",&(G->vexs[i])); for (i=0;i<G->n;i++) for (j=0;j<G->n;j++) G->edges[i][j]=0; for (k=0;k<G->e;k++) { scanf("%d%d",&i,&j); /*输入e条边，建立邻接矩阵*/ G->edges[i][j]=1; /*若加入G->edges[j][i]=1;，*/ } }/*CreateMGraph*/

22 邻接矩阵表示法 有向网 A B C D A ∞ 3 ∞ 2 B ∞ ∞ 5 4 C ∞ ∞ ∞ 6 D 1 ∞ ∞ ∞ B A C D 6

23 邻接矩阵表示法 练习：给出下列网的邻接矩阵表示法 1 2 3 4 ∞ 9 6 3 ∞ 9 ∞ 4 5 ∞ A＝ 6 4 ∞ ∞ 7
3 4 ∞ ∞ 9 ∞ ∞ A＝ ∞ ∞ 7 ∞ ∞ 8 ∞ ∞ ∞ 9 6 4 3 5 7 8

24 邻接表 存贮方式 把从一个顶点出发的边链接在一个单链表（又称边链表）中 所有边链表的表头指针放在一个顺序表（又名顶点表）中 边链表结点：
nextarc info adjvex 或 顶点表结点： firstarc vexdata

25 邻接表 V1 V2 V3 V4 V1 V3 V2 V4 有向图 V1 V2 V3 V4 V1 V3 V2 V4 无向图  3  4 

26 邻接表的特点 在边稀疏的情况下，节省存储空间 判定任意两个顶点之间是否有边或弧不方便 不便于计算有向图各个顶点的度

27 邻接表存储表示 ＃define MaxVerNum 100 /*最大顶点数为100*/ typedef char VertexType ; typedef struct node { /*边表结点*/ int adjvex; struct node * next; /*若要表示边上信息，则应增加一个数据域info*/ }EdgeNode; typedef struct vnode { /*顶点表结点*/ VertexType vertex; EdgeNode * firstedge; }VertexNode; typedef struct{ VertexNode AdjList[MaxVertexNum]; int n,e; }ALGraph;

28 // 建立一个有向图的邻接表存储的算法如下： void CreateALGraph(ALGraph. G) {/. 建立有向图的邻接表存储
// 建立一个有向图的邻接表存储的算法如下： void CreateALGraph(ALGraph *G) {/*建立有向图的邻接表存储*/ int i,j,k; EdgeNode * s; scanf("%d,%d",&(G->n),&(G->e)); /*读入顶点数和边数*/ for (i=0;i<G->n;i++) { scanf(“\n%c",&(G->AdjList[i].vertex)); G->adjlist[i].firstedge=NULL; } for (k=0;k<G->e;k++) /*建立边表*/ scanf("\n%d,%d",&i,&j); s=(EdgeNode*)malloc(sizeof(EdgeNode)); s->adjvex=j; /*邻接点序号为j*/ s->next=G->AdjList [i].firstedge; /*将新边表结点s插入到顶点Vi的边表头部*/ G->adjlist[i].firstedge=s; }/*CreateALGraph*/

29 邻接表 B A C D 6 3 2 1 5 4 有向网 A Ｂ Ｃ Ｄ 2 3 4 2  3 5 4  4 6  1 

30 逆邻接表 V1 V2 V3 V4 V1 V3 V2 V4 有向图 V1 V2 V3 V4  3  4  1   4  1  2

31 小结 本讲主要介绍了图的定义和基本术语，以及图的两种不同的存储结构：邻接矩阵和邻接表。重点介绍了邻接矩阵和邻接表的存储结构以及如何建立相应存储结构的图。 31/26

32 作业与实验 作业 1．在有向图的邻接矩阵中如何求某个顶点的入度和出度？ 在无向图的邻接表中如何求某个顶点的度数？
2．设计将图的邻接矩阵转为图的邻接表的算法。 32/26