第8章-图电子课件.pptx

江西省高等学校精品课程

计算机科学与技术专业核心课程;揭安全;揭安全;8.1图的基本概念;8.1图的基本概念;交通图（公路、铁路）;A;一、图的定义;通常，也将图G的顶点集和边集分别记为V（G）和E（G）。;图8-1;图8-1;在以后的讨论中，我们约定：

（1）一条边中涉及的两个顶点必须不相同，即：若（vi，vj）或vi，vj是E（G）中的一条边，则要求vi≠vj；

（2）一对顶点间不能有相同方向的两条有向边；

（3）一对顶点间不能有两条无向边，即只讨论简单的图。;V0;8.1图的基本概念;v1;在图中，顶点v的度就是与该顶点相关联的边的数目，记为D（v）。例如,无向图G3中，各顶点的度均为3。;若G为有向图，则把以顶点v为终点的边的数目称为顶点v的入度，记为ID（v）；把以顶点v为始点的边的数目称为v的出度，记为OD（v），D（v）=ID（v）+OD（v）。;无论有向图还是无向图，图中的每条边均关联于两个顶点，因此，顶点数n、边数e和度数之间有如下关系：;给定两个图Gi和Gj，其中Gi=（Vi，Ei），Gj=（Vj，Ej），若满足V(Gi)?V(Gj)，E(Gi)?E(Gj)，则称Gi是Gj的子图。;v1;v1;8.1图的基本概念;如果一条路径上除了起点v和终点u相同外，其余顶点均不相同，则称此路径为一条简单路径。

起点和终点相同（v=u）的简单路径称为简单回路或简单环。;8.1图的基本概念;8.1图的基本概念;在无向图G中，若从顶点vi到顶点vj有路径，则称vi与vj是连通的。

若V（G）中任意两个不同的顶点vi和vj都连通（即有路径），则称G为连通图。;v1;无向图G的极大连通子图称为G的连通分量。

根据连通分量的定义，可知任何连通图的连通分量是其自身。

非连通的无向图有多个连通分量。;（a）非连通图G5;在有向图G中，若对于V（G）中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。;有向图的极大强连通子图称为G的强连通分量。

根据强连通图的定义，可知强连通图的唯一强连通分量是其自身。

而非强连通的有向图有多个强连分量。;v1;有时在图的每条边上附上相关的数值，这种与图的边相关的数值叫权。;8.1图的基本概念;揭安全;8.2图的基本操作;图的基本操作如下：

（1）Creat（n） 创建一个具有n个顶点，没有边的图；

（2）Exist（i，j） 如果存在边（i，j）则返回1，否则返回0；

（3）Edges（） 返回图中边的数目；

（4）Vertices（） 返回图中顶点的数目；

（5）Add（i，j） 向图中添加边（i，j）；

（6）Delete（i，j） 删除边（i，j）；;（7）Degree（i） 返回顶点i的度；

（8）InDegree（i） 返回顶点i的入度；

（9）OutDegree（i） 返回顶点i的出度；

}ADTGraph;揭安全;8.3图的基本存储结构;1;;8.3.1邻接矩阵及其实现;v0;用邻接矩阵表示图，很容易判定任意两个顶点之间是否有边相连，并求得各个顶点的度数。;当G=（V，E）是一个网络时，G的邻接矩阵是具有如下性质的n阶方阵：;V0;邻接矩阵存储结构;/*函数功能：建立图的邻接矩阵存储结构

函数参数：邻接矩阵的指针变量g；存放图信息的文件名s；图的类型参数c，c=0表示建立无向图，否则表示建立有向图

*/

voidcreat(Mgraph*g,char*s,intc)

{inti,j,k,w; /*建立网络的邻接矩阵存储结构*/

FILE*rf;

rf=fopen(s,r);/*从文件中读取图的边信息*/

if(rf)

{

fscanf(rf,%d%d,g-n,g-e);;for(i=0;ig-n;i++) /*读入图中的顶点值*/

fscanf(rf,%1s,g-vexs[i]);

for(i=0;ig-n;i++) /*初始化邻接矩阵*/

for(j=0;jg-n;j++)

if(i==j)g-edges[i][j]=0;

elseg-edges[i][j]=FINITY;

for(k=0;kg-e;k++) /*读入网络中的边*/

{ fscanf(rf,%d%d%d,i,j,w);

g-edges[i][j]=w; /*建立无向图邻接矩阵*/

if(c==0)g-edges[j][