常德网站优化咨询电话,基于jsp的网站开发,wordpress文件核对,西宁建设网站目录 第六章 图6.1 图的基本概念知识回顾 6.2 图的储存结构#xff08;邻接矩阵法#xff09;1. 数组表示法(1) 有向图#xff0c;无向图的邻接矩阵 2. 定义邻接矩阵的结构3. 定义图的结构4. 构造图G5. 特点 第六章 图
6.1 图的基本概念
图是一种非线性结构
图的特点邻接矩阵法1. 数组表示法(1) 有向图无向图的邻接矩阵 2. 定义邻接矩阵的结构3. 定义图的结构4. 构造图G5. 特点 第六章 图
6.1 图的基本概念
图是一种非线性结构
图的特点
顶点之间的关系是任意的图中任意两个顶点之间都可能相关顶点的前驱和后继个数无限制
定义图是一种数据元素间存在多对多关系的数据结构加上一组基本操作构成的抽象数据类型。
定义图G由顶点集V和边集E组成记为G(V,E),其中V(G)表示图G中顶点的有限非空集E(G)表示图G中顶点之间的关系(边)集合。若V{V1,V2,……Vn}则用|V|表示图G中顶点的个数也称图G的阶E{(u,v)|u∈V,v∈V}用|E|表示图G中边的条数。注意线性表可以是空表树可以是空树但图不可以为空即V一定是非空集。弧头和弧尾 x,y表示从顶点到顶点y的一条弧并称x为弧尾或起始点称y为弧头或终端点
无向图有向图有向图u,v其中u表示弧尾v表示弧头。简单图简单图①不存在重复边② 不存在顶点到自身的边。多重图图G中某两个结点之间的边数多于一条又允许顶点通过同一条边和自己关联则G为多重图。度入度出度① 无向图在具有n个顶点e条边的无向图中全部顶点的度的和等于边数的2倍一条边连两个顶点所以一条边两个度。②有向图度之和入度出度一条边一个出度一个入度在具有n个顶点e条边的有向图中入度出度e。路径简单路径路径长度① 在路径序列中顶点不重复出现的路径称为简单路径。②路径长度路径上边的数目简单就意味着顶点不重复。回路简单回路除第一个顶点和最后一个顶点外其余顶点不重复出现的回路称为简单回路。点到点到距离从顶点u出发到顶点v的最短路径若存在则此路径的长度称为u到v的距离。若u到v根本不存在路径则记该距离为无穷∞。连通图强连通图①若图G中任意两个顶点都是连通的则称图G为连通图无向图中的连通就是两个顶点之间路径存在有向图中的强连通是两个顶点之间存在往返的路径就是w到v和v到w都有路径强连通是有向图独有的概念否则称为非连通图。对于n个顶点的无向图G若G是连通图则至少有n-1条边就是把每个顶点都连线一个顶点就存在路径了若G是非连通图则最多可能有 C n − 1 2 C_{n-1}^{2} Cn−12,就是除去一个顶点其他顶点两两相连只要不连接最后一个顶点这个图就是不连通的最极端情况。②若图中任何一项顶点都是强连通的则称为图为强连通图。对于n个顶点的有向图G若G是强连通图则最少为n条边形成回路。连通的补充图解
连通的最少边数 不连通的最多边数 强连通的最少边数 子图不用包含所有顶点、生成子图若包含所有顶点的子图就称为生成子图。并不是任意几个点任意几条边都能构成子图例如不构成图的情况。 连通分量无向图中极大连通子图(子图必须连通且包含尽可能多的顶点和边称为连通分量。 强连通分量有向图中有极大强连通子图子图必须强连通同时保留尽可能多的边称为有向图的强连通分量。 生成树连通图的生成树是包含图中全部顶点的一个极小连通子图边尽可能的小但要保持连通若图中顶点数是n则它的生成树含有n-1条边对于生成树而言若砍去一条边则会变成非连通图若加上一条边则会形成一个回路环。 生成森林在非连通图中连通分量的生成树构成了非连通图的生成森林。 边的权带权图网 无向完全图无向图中任意两个顶点之间都存在边。 有向完全图有向图中任意两个顶点之间都存在方向相反的两条弧。 稀疏图稠密图这二者是相对的 树不存在回路且连通的无向图n个顶点的树必有n-1条边。 有向树一个顶点的入度为0其余顶点的入度均有1的有向图称为有向树。 n个顶点的图若|E|n-1,则一定有回路。
知识回顾 6.2 图的储存结构邻接矩阵法 1. 数组表示法
(1) 有向图无向图的邻接矩阵 ① 对于无向图顶点vi的度是邻接矩阵中第i行或第i列的元素之和 TDvi ∑ a[i][j]。 ② 对于有向图顶点VI的出度ODvi是邻接矩阵中第i行的元素之和顶点vi的出度IDvi是邻接矩阵中第j列的元素之和。 ③ 邻接矩阵法求顶点的度。入度。出度的时间复杂度为O(|V|)。 2. 定义邻接矩阵的结构
#define INFINITY INT_MAX
#define MAX_VERTEXT_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind;
typedef struct ArcCell{VRType adj;//对无向图用0,1表示是否相邻对于带权图为权值InfoType *info;//该弧相关信息的指针}RrcCell,AdjMatrix[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM];//邻接矩阵
3. 定义图的结构
1代码
//定义图的结构
typedef struct {VertextType exs[MAX_VERTEXT_NUM]; //顶点AdjMatrix arcs[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM]; //边的邻接矩阵int vexnum,arcnum; //个数GraphKind kind;//有向图无向图
}MGraph; 4. 构造图G
status CreateGraph(MGraph G)
{scanf(G.kind){case DG:return CreateDG(G);case DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateDGN(G);default:return ERROR;}
}
//用无向图为例status CreateUDN(MGraph G)
{scanf(G.arcnum,G.vexnum,IncInfo);//输入点数和边数//给顶点进行数字化编号for(i0;iG.vexnum;i){ scanf(G.exs[i]);//定义顶点数组如果顶点本身就是1~n的数字无需这一步}//初始化邻接矩阵for(i0;iG.vexnum;i){for(j0;jG.vexnum;j){G.arcs[i][j]{ININITY,NULL};}}//通过边数进行遍历for(k0;kG.arcnum;K){scanf(V1,V2,W);//输入邻接的连个顶点ilocatteVex(G,V1);jlocateVex(G,V2);//查找V1,V2的位置G.arcs[i][j].adjw;//给邻接矩阵赋值if(IncInfo){INPUT(*G.arcs[i][j].info);}G.arcs[j][i]G.arcs[i][j];//由于是无向图对称}return ok;
}
5. 特点
优点
无向图邻接矩阵是对称矩阵同一条边表示了两次顶点v的度等于二维数组对应行(或列)中1的个数判断两顶点v、u是否为邻接点只需判二维数组对应分量是否为1在图中增加、删除边只需对二维数组对应分量赋值1或清0占用存储空间只与它的顶点数有关与边数无关适用于边稠密的图对有向图的数组表示法可做类似的讨论’‘
缺点
不便于删除和增加顶点增删边简单不便于统计边的数目需要扫描邻接矩阵所有元素才能统计完毕时间复杂度为O( n 2 n^2 n2 )空间复杂度高对于有向图n个顶点需要 n 2 n^2 n2 个单元存储边对于无向图n(n-1)/2个单元空间复杂度为O( n 2 n^2 n2 )
