计算机软件技术基础-课件 07ch3(2)-DS

线性结构（线性表、栈、队、串、数组）数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算数据结构课程的内容多对多（m:n)3.2图

3.2.1图的定义和基本概念

3.2.2图的存储结构

3.2.3图的遍历3.2.1图的定义和基本概念1.图的基本概念图：记为G＝(V,E)

其中：V

是G的顶点集合，是有穷非空集；

E

是G中边的集合，是V中两个顶点之间关系的集合。V=vertexE=edge

V＝{vi|vi∈data_object}E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}其中，P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。在该图中：集合V＝集合E＝v1v2v3v4v53.2.1图的定义和基本概念{v1,v2,v3,v4,v5}；{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}3.2.1图的定义和基本概念2.图的术语（1）无向图: 在一个图中，如果任意两个顶点构成的偶对（vi,vj）∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。（2）有向图: 在一个图中，如果任意两个顶点构成的偶对（vi,vj）∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图。BACDv1v2v3v4v5无向图有向图(3)顶点、边、弧、弧头、弧尾。BACD数据元素vi称为顶点(vertex)；P(vi,vj)表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；用顶点的无序偶对（vi,vj）来表示。如果是在有向图中，一般称这条连线为弧；用顶点的有序偶对<vi,vj>来表示。有序偶对的第一个结点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第二个结点vj被称为终点（或弧头），在图中就是带箭头的一端。3.2.1图的定义和基本概念在有向图中，<V1，V3>表示从V1到V3的一条弧。

V1为弧尾或始点，V3为弧头或终点。在无向图中，(V1，V3)表示V1和V3之间的一条边。3.2.1图的定义和基本概念V1V3V2V4有向图V1V3V2V4无向图完全图，图G（有n个顶点）任意两个顶点都有一条边/弧相连接。有向完全图：至少有

条弧的有向图若是完全有向图，则顶点1必与所有其他顶点各有2条连线，即有2(n-1)条边，顶点2有2(n-2)条边，…，顶点n-1有2条边,顶点n有0条边.总边数＝2(n-1＋n-2＋…＋1＋0)=2(n-1+0)n/2=n(n-1)无向完全图：至少有

条边的无向图若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，…，顶点n-1有1条边,顶点n有0条边。总边数＝n-1＋n-2＋…＋1＋0=（n-1+0)n/2=n(n-1)/2稀疏图（边数<nlogn）和稠密图3.2.1图的定义和基本概念n×(n－1)n×(n－1)/2V1V2V3V4有向图V1V2V3V4无向图3.2.1图的定义和基本概念邻接点对于无向图G＝（V，E），如果边（v1，v2）

E，则称顶点v1，v2互为邻接点。边（v1,v2）依附于顶点v1和v2，边（v1,v2）和顶点v1与v2相关联。对于有向图G＝（V，E），若弧<v1，v2>

E，则称顶点v1邻接到顶点v2，顶点v2邻接自顶点v1。例：判断下列4种图形各属什么类型？无向无向图(树)有向图有向n(n-1)/2条边n(n-1)条边（a）G1的顶点集合为V(G1)={0,1,2,3}------无向图边集合为E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}完全图完全图注意点：1）对于有向图<Vi，Vj>和<Vj，Vi>是两条不同的边。2）对于无向图（Vi，Vj）和（Vj，Vi）是两条相同的边。（b）G3的顶点集合为V(G3)={0,1,2}------有向图

边集合为E(G3)={<0,1>,<1,0>,<1,2>}3.2.1图的定义和基本概念图的基本概念图：记为G＝(V,E)

其中：V

是G的顶点集合，是有穷非空集；

E

是G中边的集合，是V中两个顶点之间关系的集合。

V＝{vi|vi∈data_object}E＝{(vi,vj)|vi,vj∈V∧P(vi,vj)}其中，P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(vi,vj)表示一条边。问：当E(G)为空时，图G＝(V,E)存在否？答：还存在！但此时图G只有顶点而没有边。子图：设有两个图G＝（V，E）和图G’＝（V’，E’），若V’

V且E’

E，则称G’为G的子图ABCDABCDABD3.2.1图的定义和基本概念G的子图G的子图不是G的子图图G与图的边或弧相关的数据信息。带权的图。依附于该顶点的边数或弧数。以该顶点为始点(尾)的弧数。以该顶点为终点(头)的弧数。BACD631542对于有向图，TD(V)=OD(V)＋ID(V)BACD3.2.1图的定义和基本概念无论是有向图，还是无向图，顶点数n、边数e和度数TD(vi)之间的关系如下：权:网（或赋权图）：顶点的度（TD(V)）：出度(OD(V))(仅对有向图):入度(ID(V))(仅对有向图):简单路径：路径上各顶点v1,v2,...,vm

均不互相重复。回路：若路径上第一个顶点v1

与最后一个顶点vm

重合，则称这样的路径为回路或环。路径：在图G＝(V,E)中,若从顶点

vi出发,沿一些边经过一些顶点

vp1,vp2,…,vpm，到达顶点vj。则称顶点序列

(vi

vp1vp2...vpm

vj)

为从顶点vi到顶点

vj的路径。它经过的边(vi,vp1)、(vp1,vp2)、...、(vpm,vj)应当是属于E的边。路径长度：路径上边的条数。3.2.1图的定义和基本概念简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路。例：连通图：在无向图中,若从顶点v1到顶点v2有路径,则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的,则称此图是连通图。强连通图：在有向图中,

若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。3.2.1图的定义和基本概念V0V4V3V1V2连通图V0V4V3V1非连通图V2V0V4V3V1强连通图V0V4V3V1非强连通图连通分量：无向图的极大连通子图称为连通分量。极大连通子图：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。强连通分量：有向图的极大连通子图称为强连通分量。3.2.1图的定义和基本概念连通分量1

连通分量2生成树：连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图。它必定包含且仅包含G的(n-1)条边。生成森林：非连通图中，每个连通分量的生成树构成了非连通图的生成森林。3、图的基本操作 3.2.1图的定义和基本概念V0V4V3V1V2连通图G1V0V4V3V1V2连通图G1的生成树V0V4V3V1V2=V0V4V3V1非连通图V23.2.2图的存储结构图的特点：非线性结构（m:n）邻接表邻接多重表十字链表设计为邻接矩阵链式存储结构：顺序存储结构：无简单形式！（多个顶点，无序可言）但可用数组描述元素间关系。可用多重链表重点：邻接矩阵(数组)表示法邻接表(链式)表示法存储方式：用一维数组存储图中顶点的信息：顶点表V(G)用邻接矩阵表示图中各顶点间的邻接关系（边或弧）：E(G)设图G=(V,E)有n

个顶点，则无向图的邻接矩阵是一个二维数组A[n][n]，定义为：一、邻接矩阵（数组）表示法v1v2v3v5v4v4A例1：邻接矩阵：A

=（

v1v2

v3v4v5

）v1v2v3v4v500

0

0000

0000

00000000000000分析1：无向图的邻接矩阵是对称的；分析2：顶点i

的度＝第i

行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。分析3：矩阵中1的个数的一半为图中边的个数。01

0

1010

1010

101110101011

1001

0

1010

1

010

1

0111

010101110顶点表：v1v2v3v4v5无论是有向图，还是无向图，顶点数n、边数e和度数TD(vi)之间的关系如下：例2：有向图的邻接矩阵分析1：有向图的邻接矩阵可能是不对称的。分析2：顶点的出度=第i行元素之和，OD(Vi)=

顶点的入度=第i列元素之和。ID(Vi)=

顶点的度=第i行元素之和+第i列元素之和,即：TD(Vi)=OD(Vi)+ID(Vi)分析3：

矩阵中1的个数为图中弧的数目v1v2v3v4A注：在有向图的邻接矩阵中，第i行含义：第i列含义：邻接矩阵：A=(

v1v2

v3v4)v1v2v3v400

0

000

000

0000000顶点表：01

1

000

000

0

01

1

00001

1

000

000

0

01

1000

v1v2

v3v4以结点Vi为始点(尾)的弧(即出度边）；以结点Vi为终点(头)的弧(即入度边）。有向网

A

B

C

D

A

∞3∞2

B

∞

∞54

C

∞

∞

∞6

D1∞

∞

∞BACD632154例3：网图的邻接矩阵

îíìÎ==

<Vi,Vj>

[j][i]

]][[

否则如果0或∞,wij,AAEji图的邻接矩阵数据类型描述#defineMaxVertexNum100//图中顶点数

typedefintVertexType;typedefintEdgeTypetypedefstruct

{

VertexTypeV[MaxVertexNum];//顶点表

EdgeTypeedges[MaxVertexNum][MaxVertexNum]；//邻接矩阵

intn,e; //顶点数和边数}MGraph; //邻接矩阵存储的图类型无向图的邻接矩阵的建立voidCreateMGraph(MGraph*G){ inti,j,k; for(k=1;k<=G->n;k++) Scanf(“%d”,&G->V[k]);//输入顶点信息

for(i=1;i<=G->n;i++) for(j=1;j<=G->n;j++) G->edges[i][j]=0;//邻接矩阵初始化 for(k=1;k<=G->e;k++) { Scanf(“%d”,&i); Scanf(“%d”,&j); G->edges[i][j]=1;//输入顶点i到j的边 G->edges[j][i]=1;//无向图 }}v1v2v3v5v4v4邻接矩阵的插入与删除邻接矩阵的插入：无向图G->edges[i][j]=G->edges[j][i]=1有向图G->edges[i][j]=1邻接矩阵的删除：无向图G->edges[i][j]=G->edges[j][i]=0有向图G->edges[i][j]=0容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。

邻接矩阵法优点：邻接矩阵法缺点：邻接矩阵法结论：n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。

对稀疏图而言尤其浪费空间，此时可以采用邻接表存储法。5432154321顶点表v5v4v3v2v1图的邻接表表示法：顶点表+邻接表对图G中的每个顶点vi，将所有邻接于vi的顶点（即邻接矩阵中同一行的非0元素）链接在一个单链表（边表）中。称为vi的邻接表。所有顶点的邻接表的表头（头指针）放到数组中（顺序表），构成图的顶点表。顺序存储与链式存储相结合的方法。二、邻接表（链式）表示法头指针邻结点^24^2453^153^145^245^234^234^253^153^1邻接表例1：无向图的邻接表v1v2v3v5v4v4头指针邻结点12345^2445^253^1注：邻接表不唯一，因各个边结点的链入顺序是任意的。v1v2v3v4v534^253^1无向图的邻接表性质：1）第i链表中结点的数目为顶点vi的度（头结点不算）2）所有顶点邻接表中结点数目总和的一半为图中的边数3）占用存储单元的数目为n＋2e个顶点表邻接表有向图的邻接表性质：1）第i个链表中结点的数目为顶点i的出度2）第i个顶点的入度为该顶点在所有链表中出现的次数3）占用存储单元的数目为n＋ev1v2v3v4V4V3^V2V13^4^1^2邻接表^4^1^3^1V4V3V2V1逆邻接表例2：有向图的邻接表例3：已知某网的邻接（出边）表，请画出该网络。当邻接表的存储结构形成后，图便唯一确定！邻接表结构的数据类型描述#defineMaxVexNum100typedefintVertexType;typedefstructnode{//邻接表结点

VertexTypeadjvex;// WeightTypewdata;//边上信息 structnode*next;}EdgeNode;typedefstructvnode{//顶点表结点

VertexTypevertex;

EdgeNode*firstedge;//邻接表头指针}VertexNode;typedefstruct{ VertexNodeadjlist[MaxVexNum];// intn,e; //顶点数和边数}ALGraph //以邻接表方式存储的图类型顶点表结点：VertexNodefirstedgevextex数据域：存储顶点vi的名链域：指向vi的邻接表中第一个结点邻接表结点：EdgeNodenextinfoadjvex邻接点域：指示与顶点vi邻接的点在图中的位置链域：指向vi下一个边或弧的结点数据域：与边有关信息（如权值）建立有向图的邻接表voidCreateALGraph(ALGraph*G){ inti,j,k;

EdgeNode*s; //邻接表结点 scanf(“%d,%d”,&G->n,&G->e); for(i=1;i<=G->n;i++) //建立n个顶点的顶点表 { scanf(“\n%c”,&(G->adjlist[i].vertex)) //顶点信息

G->adjlist[i].firstedge=NULL; //顶点的边表头指针设为空 } for(k=1;k<=G->e;k++) //建立边表 { scanf(“\n%d,%d”,&i,&j); //读入<vi,vj>顶点对应序号

s=(EdgeNode*)malloc(sizeof(EdgeNode));

s->adjvex=j; //邻接点序号j

//将新邻接表结点s插入到顶点vi的邻接表的头部 s->next=G->adjlist[i].firstedge; G->adjlist[i].firstedge=s; }}邻接表结点：EdgeNodenextinfoadjvex邻接点域：指示与顶点vi邻接的点在图中的位置链域：指向vi下一个边或弧的结点数据域：与边有关信息（如权值）顶点表结点：VertexNodefirstedgevextex数据域：存储顶点vi的名链域：指向vi的邻接表中第一个结点邻接表的缺点：邻接表的优点：空间效率高；容易寻找顶点的邻接点；判断两顶点间是否有边或弧，需搜索两顶点对应的单链表，没有邻接矩阵方便。邻接表结论讨论：邻接表与邻接矩阵有什么异同之处？联系： 邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于邻接矩阵一行中非零元素的个数。2.区别：①对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号有关）。②对于无向图，邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+2e)。v1v2v3v5v4v4A图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。一、深度优先搜索二、广度优先搜索

3.2.3图的遍历遍历定义：遍历实质：图的特点：解决思路：图常用的遍历：怎样避免重复访问？找每个顶点的邻接点的过程。 可设置一个辅助数组

visited[n]，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i

被访问，就立即改visited[i]为1，防止它被多次访问。从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，这样的过程称为图的遍历，它是图的基本运算。一、深度优先搜索(DFS)基本思想—仿（二叉）树的先序遍历过程。以图中某一结点作为当前结点，进行：1)处理或输出当前结点，并记录当前结点的查访标志。2)若当前结点有邻接点，则取第一个邻接点。若该邻接点未被查访过，则以该邻接点为当前结点用深度优先搜索法进行查访。如下例所示：Depth_FirstSearch深度优先搜索(DFS)仿树的先序遍历过程：v1v1v2v3v8v7v6v4v5DFS结果例1：→→→→→→→v2v4v8v5v3v6v7例2：v2→v1→v3→v5→DFS结果v4→v6起点起点遍历步骤首先设置一个辅助数组visited[i]，用来标记每个被访问过的顶点i，它的初态为0，访问后置“1”标识。1)首先访问顶点i，并标识visited[i]=1,表示访问过。2）搜索与顶点i有边相连的下一个顶点j；①若j未被访问过就标识visited[j]=1，然后从j开始重复此过程；②若j已被访问过，再看与i有边相连的其它顶点。3）若图中尚有顶点未被访问，则另选一个未被访问的顶点作为起始顶点，重复上述过程，直到图中所有的顶点都被访问过。

记

visited[i]=0图中第i个顶点未被访问过1图中第i个顶点被访问过深度优先搜索（遍历）操作：起点DFS:213546讨论1：邻接矩阵如何实现DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111DFS结果邻接矩阵A辅助数组visited[n]起点v2→v1→v3→v5→v4→v6——开辅助数组

visited[n]！例：123456101110021000103100010410000150110006000100邻接矩阵的DFS算法如何编程？DFS1(MGraph*g,inti)

{intj；printf(“%d”,g->V[i]);visited[i]=1;for(j=1;j<=n;j++)if((g->edges[i][j]==1)&&(!visited[j]))

DFS1(g,j);}——可以用递归算法！//g邻接矩阵，i为起始顶点(编号）//访问（例如打印）顶点v

//DFS1edges[i,j]＝1有邻接点visited[j]=0未访问过//访问后立即修改辅助数组标志//从v所在行从头搜索邻接点起点DFS:213546讨论2：在图的邻接表中如何进行DFS？v0→v1→v2→v3DFS结果00000123辅助数组visited[n]1000110011101111例：—照样借用visited[n]！起点0123

邻接表的DFS算法如何编程？DFS2(ALGraph*G，inti){EdgeNode

*p;printf(“%d”,G->adjlist[i]->vextex);visited[i]=1;p=G->adjlist[i].firstedge;while(p!=null){if(visited[p->adjvex]==0) DFS2(G,p->adjvex);p=p->next;}}//访问后立即修改辅助数组标志//若指针为空，则结束本次遍历//取Vi链表的头指针——仍可用递归算法//递归调用//指向下一邻接点邻接表结点：EdgeNodenextinfoadjvex邻接点域：指示与顶点vi邻接的点在图中的位置链域：指向vi下一个边或弧的结点数据域：与边有关信息（如权值）顶点表结点：VertexNodefirstedgevextex数据域：存储顶点vi的名链域：指向vi的邻接表中第一个结点typedefstruct{VertexNodeadjlist[MaxVexNum];intn,e;}ALGraph深度优先算法的说明若图不连通，则不能完成遍历voidDSF_GRAPH(ALGraph*G){

inti;for(i=1;i<=G->n;i++) visited[i]=0;for(i=1;i<=G->n;i++) {if(!visited[i]) DFS2(G,i); }}DFS算法效率分析:（设图中有n个顶点，e条边）如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。如果用邻接表来表示图，寻找邻接点所需时间为O(e)，加上访问n个头结点的时间，因此遍历图的时间复杂度为O(n+e)。结论：稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。v1v2v3v5v4v4A二、广度优先搜索(BFS)基本思想——仿树的层次遍历过程。

从图的某一个结点出发，首先依次访问该结点的邻接点，然后再顺序访问这些邻接点的所有未被访问过的邻接点。依此类推，直到所有被访问结点的邻接点均被访问过为止。特点：尽可能先对横向进行搜索，故为广度优先搜索。Breadth_FirstSearch广度优先搜索(BFS)基本思想——仿树的层次遍历过程。v1v1v2v3v8v7v6v4v5BFS结果例1：→→→→v2v3→v4v5→v6v7→v8例2：v3→BFS结果v4

→v5→起点遍历步骤起点v2→v1→v6→v9→v8→v7广度优先搜索（遍历）步骤：简单归纳：1）首先访问了起始点i之后，标识visited[i]＝1；2）依次访问与顶点i有边相连的所有邻接点；3）然后再依次访问这些邻接顶点中未被访问过的邻接点；(先访问的邻接顶点，其邻接点亦被先访问－－队列）4）直到所有顶点都被访问过为止。说明：广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。

因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。讨论1：邻接表的BFS？邻接表——除辅助数组visited[n]外，还需再开一辅助队列！例：起点辅助队列（先访问，再入队）v2已访问过了BFS遍历结果2入队！初始f=0,r=0邻接表的BFS算法如何编程？——层次遍历应当用队列！