版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
图算法基础知识第1页,课件共29页,创作于2023年2月图图
G=(V,E)V=顶点的非空有限集E=边集
=VV的子集,V中顶点对,边的有限集。|E|=O(|V|2)简单图(SampleGraph)
任意两个顶点最多只有一条边,且每个点都没有连接到自身的边。完全图(CompleteGrapth)
若有n个顶点的无向图n(n-1)/2条边,则此图为完全图。第2页,课件共29页,创作于2023年2月图的扩展扩展:连通图(
connectedgraph)
从图中每一顶点都有到其它顶点的路径。无向图(
undirectedgraph):边(u,v)=边
(v,u)有向图(directed
graph):(u,v)表示从顶点u到顶点v的一条有向边,记为uv一个不含有环的有向图称为无环有向图(Directedacyclicgraphs
,DAG)。加权图(
weightedgraph)
图中不是边就是顶点与权关联,例如:公路交通图,边以距离w为权。第3页,课件共29页,创作于2023年2月图通常用边数|E|和顶点数|V|描述运行时间。无向图中
0≤|E|≤|V|(|V|-1)/2有向图中
0≤|E|≤|V|(|V|-1)若|E||V|2
,图是稠密的
dense若
|E||V|,图是稀疏的
sparse对稠密图和稀疏图使用不同的数据结构第4页,课件共29页,创作于2023年2月图的表示假设V={1,2,…,n}邻接矩阵(adjacencymatrix)
将图表示成一个
nxn
矩阵
A:A[i,j] =1若边
(i,j)E(或边的权wij)
=0若边
(i,j)E第5页,课件共29页,创作于2023年2月图:邻接矩阵Example:1243A123410110200103000040010有向图非对称矩阵第6页,课件共29页,创作于2023年2月图:邻接矩阵Example:1243adbcA1234123??4第7页,课件共29页,创作于2023年2月图:邻接矩阵Example:1243adbcA123410ad0200b030000400c0第8页,课件共29页,创作于2023年2月图:邻接矩阵Example:12435143A123410350200103000040040第9页,课件共29页,创作于2023年2月图:邻接矩阵Example:1243adbcA123410ad02a0b03db0c400c0无向图对称矩阵第10页,课件共29页,创作于2023年2月图:邻接矩阵邻接矩阵的实现
constmaxlength=100{最大顶点数}typegraph=array[1..maxlength,1..maxlength]ofinteger;
二维数组第11页,课件共29页,创作于2023年2月输入和查看一遍邻接矩阵需要多少时间?答:O(|V|2)存储一个邻接矩阵需要多少存储空间?答:O(|V|2)稀疏图(|E||V|或|E|<<|V|),邻接矩阵是稀疏矩阵,浪费空间,因此采用邻接表更有效。图:邻接矩阵第12页,课件共29页,创作于2023年2月图:邻接表邻接表:对每个顶点
vV,将v的所有邻接点存放在一个列表中。Example:Adj[1]={2,3}Adj[2]={3}Adj[3]={}Adj[4]={3}1243第13页,课件共29页,创作于2023年2月1243图:邻接表123nil23nil3nil43nil第14页,课件共29页,创作于2023年2月邻接表的实现Typepointer=↑adjnodeadjnode=record
adjvex:integer;{该点在图中的位置}
next:pointer;{指向下一个顶点的指针}
infor:…;{与边有关的信息,如权值w}Adjlist=array[1..maxlength]ofpointer;图:邻接表第15页,课件共29页,创作于2023年2月
无环有向图的拓扑排序
Directedacyclicgraphs(DAG)topologicalsort
DAG:不含回路的有向图称为无环有向图。
检查有向图中是否存在回路的方法之一,是对有向图进行拓扑排序。
如果有向图G有一个拓扑排序,则G是一个有向无环图.反之,任一有向无环图必可进行拓扑排序。第16页,课件共29页,创作于2023年2月何谓“拓扑排序”?
按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系。
由此所得顶点的线性序列称之为拓扑有序序列第17页,课件共29页,创作于2023年2月例如:对于下列有向图BDAC可求得拓扑有序序列:
ABCD
或
ACBD第18页,课件共29页,创作于2023年2月BDAC反之,对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路
{B,C,D}第19页,课件共29页,创作于2023年2月如何进行拓扑排序?一、从有向图中选取一个没有前驱的顶点,并输出之;
重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。二、从有向图中删去此顶点以及所有以它为尾的弧;第20页,课件共29页,创作于2023年2月abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念
没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减1第21页,课件共29页,创作于2023年2月拓扑排序算法Functiontopsort:boolean;P140vari,count:integer;wadj:Arr3;//用来表示图的邻接表表头数组
indeg:Arr1;//一维数组,存储每个顶点的入度
p:wpointer;//链表,邻接表
q:queue;//队列q保存入度为零且未被排序的顶点
begin//算法依次对q的出队元素进行编号
topsort:=true;count:=0;makenull(q);//清空队列qfillchar(indeg,sizeof(indeg),0);
//数组indeg存储每个顶点入度第22页,课件共29页,创作于2023年2月//通过遍历邻接表,计算所有顶点的入度Fori:=1tondobeginp:=wadj[i];//顶点i的邻接表的第一个邻接点
whilep<>nildo//依次为顶点i的所有邻接点入度加1begininc(indeg[p^.v]);p:=p^.next;end;End;第23页,课件共29页,创作于2023年2月//入度为0的顶点加入队列qFori:=1tondoifindeg[i]=0thenenqueue(i,q);//入队//队列q的队首顶点出队,与该顶点邻接的顶点的出度减1Whilenotempty(q)dobegini:=dequeue(q);inc(count);//计数器加1ord[i]:=count;//ord数组存储顶点i的排序后的序号
p:=wadj[i];
whilep<>nildo//该循环将顶点i的所有邻接点入度减1begindec(indeg[p^.v]);ifindeg[p^.v]=0thenenqueue(p^.v,q);p:=p^.next;endEnd第24页,课件共29页,创作于2023年2月//入度为0的顶点数小于n时,存在环;
否则图不存在环,且可进行拓扑排序,ord数组存储的就是排序后的序号Ifcount<nthenbeginwriteln(‘graphiscyclic’);topsort:=false;end;End;第25页,课件共29页,创作于2023年2月拓扑排序应用字母排序给定的一组字母,并在该组字母上定义偏序关系<,确定该组字母能否按此偏序关系升序排序。例如,有序序列A,B,C,D表示A<B,B<CandC<D.在该问题中,给出一形如A<B的关系集,并要求确定该序列是否有序。如果有序,输出这个序列,并输出是通过前多少关系得出的(即使之后的关系引出矛盾也不必理会)。如果存在矛盾,则输出前多少项出现的矛盾的。第26页,课件共29页,创作于2023年2月具体思路:
每输入一组偏序关系进行一次拓扑排序。如果存在回路,输出矛盾。在不存在回路的基础上,判断每次入度为0的点是否唯一,只有保证每次只有一个点入度为0,才能保证最终的序列唯一。第27页,课件共29页,创作于2023年2月Input46//n=4表示字母数,2≤n≤26,m=6表示形如A<B的偏序关系数A<B//第1个偏序关系A<CB<CC<DB<DA<B//第6
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年安庆办理客运从业资格证版试题
- 银行国际业务行业调研及投资前景分析报告
- 2024年昭通驾驶员货运从业资格证考试题
- 2024年拉萨客运资格证考试题
- 云人力资源行业发展前景及投资风险预测分析报告
- 专业医疗图书出版行业调研及投资前景分析报告
- 养殖环境控制科技行业调研及投资前景分析报告
- 新能源汽车零部件行业的消费市场分析
- 化工产品冷链物流行业市场发展趋势及投资咨询报告
- 智慧渔业行业竞争格局与投资战略研究咨询报告
- 汽车行业常用术语
- SIP范本精编版
- ZFS100002545中位放顶煤液压支架设计(含有全套CAD图纸)
- 普罗米修斯-王崧舟.ppt
- 甲状腺乳腺外科临床技术操作规范
- 如家快捷酒店硬件装修规范手册
- 可靠性设计分析试题B
- 电气系统维修保养的检修内容
- 第13章 羧酸及其衍生物
- 四年级英语上册 Unit 5 Dinner is ready试卷 人教PEP-人教PEP小学四年级上册英语试题
- 《产后出血》PPT课件
评论
0/150
提交评论