您所在位置: 网站首页 / 文档列表 / 图形图像 / 文档详情
GRAPH ALGORITHMS.doc 立即下载
上传人:yy****24 上传时间:2024-09-03 格式:DOC 页数:36 大小:239KB 金币:16 举报 版权申诉
预览加载中,请您耐心等待几秒...

GRAPH ALGORITHMS.doc

GRAPHALGORITHMS.doc

预览

免费试读已结束,剩余 26 页请下载文档后查看

16 金币

下载文档

如果您无法下载资料,请参考说明:

1、部分资料下载需要金币,请确保您的账户上有足够的金币

2、已购买过的文档,再次下载不重复扣费

3、资料包下载后请先用软件解压,在使用对应软件打开

GRAPHALGORITHMSDefinitions(background):Graph:nodes/vertices,andedges/arcsaspairsofnodes.{V,E}e12=(v1,v2,l12)Thethirdterml12,ifpresent,couldbealabelortheweightofanedge.Directedgraph:edgesareorderedpairsofnodes.Weightedgraph:eachedge(directed/undirected)hasaweight.Pathbetweenapairofnodesvi,vk:sequenceofedgeswithvi,vkatthetwoends.Simplepath:coversnonodeinittwice.Loop:apathwiththesamestartandendnode.Pathlength:numberofedgesinit.Pathweight:totalwtofalledgesinit.Connectedgraph:thereexistsapathbetweeneverynode,nonodeisdisconnected.Completegraph:edgebetweeneverypairofnodes[NUMBEROFEDGES?].Acyclicgraph:agraphwithnocycles.Etc.Graphsareoneofthemostusedmodelsofreal-lifeproblemsforcomputer-solutions.Representations:Adjacencylist(alinklistoranarrayofdirectlyconnectednodesforeachnode),andmatrixaretworepresentations.MatrixisO(N^2)forNnodesbuteasytoaccess,whileadjacencylistisgoodforsparsegraph(sparselydistributededges,lessconnected).Problemsizeincludesboth|V|(numberofnodesN),and|E|(numberofedges,intheworstcaseO(N2)forcompletegraph,butnot“fair”forasparsegraph).Also,withmatrixrepresentation|E|isalwaysN2,becauseonehastogooverallthepairsofnodestocheckwhichonesareinE.Algorithm1:ForeachnodevinVdo-Steps-//(|V|)Algorithm2:ForeachnodevinVdoForeachedgeinEdo-Steps-//(|V|*|E|)Algorithm3:ForeachnodevinVdoForeachedgeeofvdo-Steps-//(|E|)withadjacencylist,but(|V|*|V|)formatrixrepres.Algorithm4:ForeachnodevinVdoForeachnodewadjacenttovdo-Steps-//again,(|E|)withadjacencylistAlgorithm5:ForeachnodevinVdo-steps-Foreachedgeeofvdo-Steps-//(|V|+|E|)or(max{|V|,|E|})TOPOLOGICALSORTInput:directedacyclicgraphOutput:sequentiallyorderthenodeswithoutviolatinganyarcordering.Note:youmayhavetocheckforcycles-dependingontheproblemdefinition(input:directedgraph).Example:coursepre-requisitegraph,findalinearorderingofcourses.Animportantdata:indegreeofeachnode-numberofarcscomingin(#coursespre-requisiteto"this"course).Afirst-passstra
单篇购买
VIP会员(1亿+VIP文档免费下)

扫码即表示接受《下载须知》

GRAPH ALGORITHMS

文档大小:239KB

限时特价:扫码查看

• 请登录后再进行扫码购买
• 使用微信/支付宝扫码注册及付费下载,详阅 用户协议 隐私政策
• 如已在其他页面进行付款,请刷新当前页面重试
• 付费购买成功后,此文档可永久免费下载
年会员
99.0
¥199.0

6亿VIP文档任选,共次下载特权。

已优惠

微信/支付宝扫码完成支付,可开具发票

VIP尽享专属权益

VIP文档免费下载

赠送VIP文档免费下载次数

阅读免打扰

去除文档详情页间广告

专属身份标识

尊贵的VIP专属身份标识

高级客服

一对一高级客服服务

多端互通

电脑端/手机端权益通用

手机号注册 用户名注册
我已阅读并接受《用户协议》《隐私政策》
已有账号?立即登录
我已阅读并接受《用户协议》《隐私政策》
已有账号?立即登录
登录
手机号登录 微信扫码登录
微信扫一扫登录 账号密码登录

首次登录需关注“豆柴文库”公众号

新用户注册
VIP会员(1亿+VIP文档免费下)
年会员
99.0
¥199.0

6亿VIP文档任选,共次下载特权。

已优惠

微信/支付宝扫码完成支付,可开具发票

VIP尽享专属权益

VIP文档免费下载

赠送VIP文档免费下载次数

阅读免打扰

去除文档详情页间广告

专属身份标识

尊贵的VIP专属身份标识

高级客服

一对一高级客服服务

多端互通

电脑端/手机端权益通用