做竞价网站需要什么样的空间,彩页设计教程,做百度关键词网站,可以做本地生活服务的有哪些网站6.图 回顾#xff1a;数据的逻辑结构 集合——数据元素间除 “同属于一个集合” 外#xff0c;无其他关系。 线性结构——一个对一个#xff0c;如线性表、栈、队列 树形结构——一个对多个#xff0c;如树 图形结构——多个对多个#xff0c;如图 6.1图的定义和术语
图:…6.图 回顾数据的逻辑结构 集合——数据元素间除 “同属于一个集合” 外无其他关系。 线性结构——一个对一个如线性表、栈、队列 树形结构——一个对多个如树 图形结构——多个对多个如图 6.1图的定义和术语
图: G(V,E)V:顶点数据元素的有穷非空集合 E:边的有穷集合。无向图每条边都是无方向的
有向图每条边都是有方向的。 完全图任意两个点都有一条边相连。 无向完全图n 个顶点n(n-1)/2条边 有向完全图n 个顶点n(n-1)条边 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NdIzTjfy-1691238142116)(https://ts1.cn.mm.bing.net/th/id/R-C.bf9aad94a55a06758f0d0d4a2aa083bf?rikVscqICD0R7hR%2fAriuhttp%3a%2f%2fdata.biancheng.net%2fuploads%2fallimg%2f190103%2f2-1Z103210110O8.gifehkOi7hLl6AEIQ%2f1UfWj%2fAO6riRvAKN51BTFvzwxhq%2bGSE%3drislpidImgRawr0)]
稀疏图有很少边或弧的图enlogn。
稠密图有较多边或弧的图。
网边/弧带权的图。
邻接有边/弧相连的两个顶点之间的关系。
存在vi,vj则称vi和vj互为邻接点
存在 vi,vj则称vi邻接到vjvj邻接到vi
关联依附边/弧与顶点之间的关系。
存在vi,vj/ vi,vj则称该边/弧关联于vi和vj
顶点的度与该顶点相关联的边的数目记为TD(v)
在有向图中顶点的度等于该顶点的入度与出度之和。
顶点v的入度是以v为顶点的有向边的条数记作ID(v)
顶点v的出度是以v为始点的有向边的条数记作OD(v) 问当有向图中仅1个顶点的入度为0其余顶点的入度均为1此时是何形状 答是树而且是一棵有向树 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-rztk0NIk-1691238142118)(https://ts1.cn.mm.bing.net/th/id/R-C.4f3bd2363f037cff739f8e388db9b321?rikW0cQmZrsrYAcEAriuhttp%3a%2f%2fivr-ahnu.cn%2flectures%2fos%2fimages%2f24.jpgehkrL%2blBOSUE1GCU30Sl09HWmQqTnbVhZDKEDVVUvJxi1U%3drislpidImgRawr0)]
路径接续的边构成的顶点序列。
路径长度路径上边或弧的数目/权值之和。
回路环第一个顶点和最后一个顶点相同的路径。
简单路径除路径起点和终点可以相同外其余顶点均不相同的路径。
简单回路简单环除路径起点和终点相同外其余顶点均不相同的路径。 连通图强连通图
在无有向图G(V,{E})中若对任何两个顶点v、u都存在从v到u的路径则称G是连通图强连通图。 权与网
图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。
带权的图称为网。
子图
设有两个图G(V,{E})、G1(V1,{E1})若V1⊆V,E1⊆E则称G1是G的子图。
例bc是a的子图 连通分量强连通分量 无向图G的极大连通子图称为G的连通分量。 极大连通子图意思是该子图是G连通子图将G的任何不在该子图中的顶点加入子图不再连通。 有向图G的极大强连通子图称为G的强连通分量。 极大强连通子图意思是该子图是G的强连通子图将D的任何不在该子图中的顶点加入子图不再是强连通的。 极小连通子图该子图是G的连通子图在该子图中删除任何一条边子图不再连通。 生成树包含无向图G所有顶点的极小连通子图。 生成森林对非连通图由各个连通分量的生成树的集合。
6.2图的存储结构
图的逻辑结构多对多 图没有顺序存储结构但可以借助二维数组来表示元素间的关系。 6.2.1邻接矩阵
1、数组邻接矩阵表示法
建立一个顶点表记录各个顶点信息和一个邻接矩阵表示各个顶点之间关系。 设图A(V,E)有 n 个顶点。图的邻接矩阵是一个二维数组。
无向图的邻接矩阵表示法
存在关系记为1没有关系记为0 分析1无向图的邻接矩阵是对称的。
分析2顶点 i 的度 第 i 行列中1的个数。
特别完全图的邻接矩阵中对角元素为0其余为1。
有向图的邻接矩阵表示方法 注在有向图的邻接矩阵中 第 i 行含义以结点vi为尾的弧即出度边 第 i 列含义以结点vi为头的弧即入度边。 分析1有向图的邻接矩阵可能是不对称的。
分析2顶点的出度 第i行元素之和
顶点的入度 第i列元素之和
顶点的度 第i行元素之和 第i列元素之和
网即有权图的邻接矩阵表示法 邻接矩阵存储表示用两个数组分别存储顶点表和邻接矩阵。
#define MaxInt 32767
#define MVNum 100 //最大顶点数
typedef char VerTexType;//设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
typedef struct{VerTexType vexs[MVNum];//顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum,arcnum;
}AMGraph;2、采用邻接矩阵表示法创建无向网
算法思想
输入总顶点数和总边数。依次输入点的信息存入顶点表中。初始化邻接矩阵使每个权值初始化为最大值。构造邻接矩阵。
Status CreateUDN(AMGraph G){cinG.vexnumG.arcnum;//输入总顶点数总边数for(i0;iG.vexnum;i)cinG.vexs[i];//依次输入点的信息for(i0;iG,vexnum;i)for(j0;jG.vexnum;j)G.arcs[i][j]MaxInt;//边的权值均设置为极大值for(k0;kG.arcnum;k){cinv1v2w;//输入一条边所依附的顶点及边的权值iLocateVex(G,v1);jLocateVex(G,v2);//确定v1和v2在G中的位置G.arcs[i][j]w;//边v1v2的权值置为wG.arcs[j][i]G.arcs[i][j];//置v1v2的对称边v2,v1的权值为w}return OK;
}补充算法在图中查找顶点
int LocateVex(AMGraph G,VertexType u){int i;for(i0;iG.vexnum;i)if(uG.vexs[i]) return i;return -1;
}3、邻接矩阵的优缺点 邻接矩阵有什么优点
直观、简单、好理解方便检查任意一对顶点间是否存在边方便找任一顶点的所有“邻接点”有边直接相连的顶点方便计算任一顶点的“度”从该店发出的边数为“出度”指向该点的边数为“入度” 无向图对应行或列非0元素的个数有向图对应行非0元素的个数是“出度”对应列非0元素的个数是“入度”。
邻接矩阵的缺点 不便于增加和删除顶点 浪费空间——存稀疏图点很多而边很少有大量无效元素 ——对稠密图特别是完全图还是很合算的 浪费时间——统计稀疏图中一共有多少条边。
6.2.2邻接表
1、邻接表表示法链式 顶点按编号顺序将顶点数据存储在一维数组中关联同一顶点的边以顶点为尾的弧用线性链表存储
无向图邻接表
特点 邻接表不唯一 若无向图中有n个顶点e条边则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。 无向图中顶点的度为第i个单链表中的结点数。 有向图邻接表
特点找出度易找入度难
顶点的出度就是第i个单链表中的结点个数。顶点的入度为整个单链表中邻接点域值是i-1的结点个数。 图的邻接表存储表示
顶点的结点结构
typedef struct VNode{VerTexType data;//顶点信息ArcNode *firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];//AdjList表示邻接表类型说明例如AdjList v; 相当于VNode v[MVNum];
弧边的结点结构
#define MVNum 100
typedef struct ArcNode{//边结点int adjvex;//该边所指向的顶点的位置struct ArcNode *nextarc;//指向下一条边的指针OtherInfo info;//和边相关的信息
}ArcNode;图的结构定义
typedef struct{AdjList vertices;int vexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;2、采用邻接表创建无向网
算法思想 输入总顶点数和总边数 建立顶点表 依次输入点的信息存入顶点表中 使每个表头结点的指针域初始化为NULL 创建邻接表 依次输入每条边依附的两个顶点 确定两个顶点的序号i和j建立边结点 将此边结点分别插入到vi和vj对应的两个边链表的头部
Status CreateUDG(ALGraph G){cinG.vexnumG.arcnum;//输入总顶点数总边数for(i0;iG.vexnum;i){//输入各点构造表头结点表cinG.vertices[i].data;//输入顶点值G.vertices[i].firstarcNULL;//初始化表头结点的指针域}for(k0;kG.arcnum;k){//输入各边构造邻接表cinv1v2;//输入一条边依附的两个顶点iLocateVex(G,v1);jLocateVex(G.v2);p1new ArcNode;//生成一个新的边结点*p1p1-adjvexj;//邻接点序号为jpi-nextarcG.vertices[i].firstarc;G.vertices[i].firstarcp1;//将新结点*p1插入顶点vi的边表头部p2new ArcNode;//生成另一个对称的新的边结点p2-adjvexi;p2-nextarcG.vertices[j].firstarc;G.vertices[j].firstarcp2;//将新结点*p2插入顶点vj的边表头部}return OK;
}3、邻接表特点 方便找任一顶点的所有“邻接点” 节约稀疏图的空间 需要N个头指针 2E个结点每个结点至少2个域 方便计算任一顶点的“度” 对无向图是的对有向图只能计算“出度”需要构造“逆邻接表”纯指向自己的边来方便计算“入度” 不方便检查任意一对顶点间是否存在边
6.2.3邻接矩阵与邻接表的关系 联系邻接表中每个链表对应与邻接矩阵中的一行链表中结点个数等于一行中非零元素的个数。
区别
对于任一确定的无向图邻接矩阵是唯一的行列号与顶点编号一致当邻接表不唯一链接次序与顶点编号无关。邻接矩阵的空间复杂度为O(n2)而邻接表的空间复杂度为O(ne)。
用途邻接矩阵多用于稠密图而邻接表多用于稀疏图。
6.2.4十字链表
十字链表是有向图的另一种链式存储结构。我们也可以把她看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。
有向图中的每一条弧对应十字链表中的一个弧结点同时有向图中的每个顶点在十字链表中对应有一个结点叫做顶点结点。 6.2.5邻接多重表
邻接表优点容易求得顶点和边的信息。
缺点某些操作不方便如删除一条边需找表示此边的两个结点。 邻接表中任何一条边都会出现两次
