基本数据结构-图.ppt

ACM ICPC程序设计 基本数据结构及其在程序设计中的应用张淑平 非线性结构 树 二叉树图 数据结构课程中所要求的图 掌握图模型中数据的存储方式 图的邻接矩阵存储和邻接表存储结构 掌握图的两种遍历方法 深度优先遍历和广度优先遍历算法 理解求最小生成树 拓扑排序 求关键路径 求最短路径等算法 图的示例 图结构 基本概念图是顶点集和边集组成的二元组G V E E中每条边是V中一对顶点 u v 间的联系 如果是无序对 那么称该图为无向图 否则为有向图 顶点u v间有边 u v互为邻接点 边 u v 和顶点u和v相关联 顶点v的度是和v相关联的边的数目 有向图中 以v为头的弧的数目称为出度 以v为尾的弧的数目称为入度 连通图 强连通子图 分量 无向图的生成树 无向图及其生成树 无向图G 有向图及其强连通子图 5 4 6 图2 图2的强连通子图 图的邻接矩阵表示 图1 图1的邻接矩阵 图的邻接链表表示 b 图1的邻接链表 图1 图的算法 基本算法遍历算法求最小生成树的算法求最短路径的算法拓扑排序算法关键路径求解算法 其他算法连通性问题及求解算法匹配问题及算法网络流问题及算法 例3 Isitatree Atreeisawell knowndatastructurethatiseitherempty null void nothing orisasetofoneormorenodesconnectedbydirectededgesbetweennodessatisfyingthefollowingproperties Thereisexactlyonenode calledtheroot towhichnodirectededgespoint 入度为0 Everynodeexcepttheroothasexactlyoneedgepointingtoit 除根之外结点的入度为1 Thereisauniquesequenceofdirectededgesfromtheroottoeachnode 根到每个结点有唯一路径 例3 Isitatree a b c 例4 学校网络 Anumberofschoolsareconnectedtoacomputernetwork Agreementshavebeendevelopedamongthoseschools eachschoolmaintainsalistofschoolstowhichitdistributessoftware the receivingschools NotethatifBisinthedistributionlistofschoolA thenAdoesnotnecessarilyappearinthelistofschoolB Youaretowriteaprogramthatcomputestheminimalnumberofschoolsthatmustreceiveacopyofthenewsoftwareinorderforthesoftwaretoreachallschoolsinthenetworkaccordingtotheagreement SubtaskA 例4 学校网络 续 Asafurthertask wewanttoensurethatbysendingthecopyofnewsoftwaretoanarbitraryschool thissoftwarewillreachallschoolsinthenetwork Toachievethisgoalwemayhavetoextendthelistsofreceiversbynewmembers Computetheminimalnumberofextensionsthathavetobemadesothatwhateverschoolwesendthenewsoftwareto itwillreachallotherschools SubtaskB Oneextensionmeansintroducingonenewmemberintothelistofreceiversofoneschool a b 例4 学校网络 续 ThefirstlineofinputfilecontainsanintegerN thenumberofschoolsinthenetwork 2 N 100 TheschoolsareidentifiedbythefirstNpositiveintegers EachofthenextNlinesdescribesalistofreceivers Thelinei 1containstheidentifiersofthereceiversofschooli Eachlistendswitha0 Anemptylistcontainsa0aloneintheline sampleinput 5430500010 Yourprogramshouldwritetwolinestotheoutputfile Thefirstlineshouldcontainonepositiveinteger thesolutionofsubtaskA ThesecondlineshouldcontainthesolutionofsubtaskB 深度优先搜索DFS 深度优先遍历图的方法是 从图中某顶点v出发 1 访问顶点v 2 依次从v的未被访问的邻接点出发 对图进行深度优先遍历 直至图中和v有路径相同的顶点都被访问 3 若此时图中尚有顶点未被访问 则从一个未被访问的顶点出发 重新进行深度优先遍历 直到图中所有顶点均被访问过为止 用栈 广度优先搜索BFS 从图中某顶点vi出发 访问顶点vi 访问vi的所有未被访问的邻接点w1 w2 wk 依次从这些邻接点 在步骤 中访问的顶点 出发 访问它们的所有未被访问的邻接点 依此类推 直到图中所有访问过的顶点的邻接点都被访问 用队列 DFSVSBFS 例5 SPF 1119 Considerthetwonetworksshownbelow Assumingthatdatamovesaroundthesenetworksonlybetweendirectlyconnectednodesonapeer to peerbasis afailureofasinglenode 3 inthenetworkontheleftwouldpreventsomeofthestillavailablenodesfromcommunicatingwitheachother Nodes1and2couldstillcommunicatewitheachotherascouldnodes4and5 butcommunicationbetweenanyotherpairsofnodeswouldnolongerbepossible 例5 SPF Node3isthereforeaSinglePointofFailure SPF forthisnetwork Strictly anSPFwillbedefinedasanynodethat ifunavailable wouldpreventatleastonepairofavailablenodesfrombeingabletocommunicateonwhatwaspreviouslyafullyconnectednetwork Notethatthenetworkontherighthasnosuchnode thereisnoSPFinthenetwork Atleasttwomachinesmustfailbeforethereareanypairsofavailablenodeswhichcannotcommunicate 例5 SPF InputTheinputwillcontainthedescriptionofseveralnetworks Anetworkdescriptionwillconsistofpairsofintegers onepairperline thatidentifyconnectednodes Orderingofthepairsisirrelevant 12and21specifythesameconnection Allnodenumberswillrangefrom1to1000 Alinecontainingasinglezeroendsthelistofconnectednodes Anemptynetworkdescriptionflagstheendoftheinput Blanklinesintheinputfileshouldbeignored 125431323435012233445510 例5 SPF 1223344663255100 Input 续 outputForeachnetworkintheinput youwilloutputitsnumberinthefile followedbyalistofanySPFnodesthatexist 例5 SPF outputThefirstnetworkinthefileshouldbeidentifiedas Network 1 thesecondas Network 2 etc ForeachSPFnode outputaline formattedasshownintheexamplesbelow thatidentifiesthenodeandthenumberoffullyconnectedsubnetsthatremainwhenthatnodefails IfthenetworkhasnoSPFnodes simplyoutputthetext NoSPFnodes insteadofalistofSPFnodes Network 1SPFnode3leaves2subnetsNetwork 2NoSPFnodesNetwork 3SPFnode2leaves2subnetsSPFnode3leaves2subnets 关节点的特点 1 若深度优先生成树的根有两棵或两棵以上的子树 则此根顶点必为关节点 2 若生成树中某个非叶子结点v 存在v的某棵子树的根及该子树的其他结点均没有指向v的祖先的回边 则v是关节点 因此 以深度优先遍历为基础增加相应的处理即可 详见严蔚敏的 数据结构 掌握有关图的基本算法 遍历方法 深度优先遍历 DFS 广度优先遍历 BFS 求最短路径 Dijkstra算法 Floyd算法 Bellman Ford算法最小生成树 Prim算法 Kruskal算法关键路径关节点最大独立集 最小支配集最大匹配 最优匹配最大网络流 克鲁斯卡尔算法求最小生成树 V4 V1 V3 V2 V6 V5 6 5 1 2 6 6 5 5 3 4 V4 V1 V3 V2 V6 V5 1 2 3 4 最小代价生成树 克鲁斯卡尔算法求最小生成树 V4 V1 V3 V2 V6 V5 6 5 1 2 6 6 5 5 3 4 V4 V1 V3 V2 V6 V5 1 2 3 4 5 V3 V4依附在同一个连通分量 最小代价生成树 克鲁斯卡尔算法求最小生成树 V4 V1 V3 V2 V6 V5 6 5 1 2 6 6 5 5 3 4 V4 V1 V3 V2 V6 V5 1 2 3 4 V1 V4依附在同一个连通分量 5 最小代价生成树 克鲁斯卡尔算法求最小生成树 V4 V1 V3 V2 V6 V5 6 5 1 2 6 6 5 5 3 4 V4 V1 V3 V2 V6 V5 1 2 5 3 4 最小代价生成树 例6 QSNetwork Intheplanetw 503ofgalaxycgb thereisakindofintelligentcreaturenamedQS QScommunicatewitheachothervianetworks IftwoQSwanttogetconnected theyneedtobuytwonetworkadapters oneforeachQS andasegmentofnetworkcable PleasebeadvisedthatONENETWORKADAPTERCANONLYBEUSEDINASINGLECONNECTION ie ifaQSwanttosetupfourconnections itneedstobuyfouradapters Intheprocedureofcommunication aQSbroadcastsitsmessagetoalltheQSitisconnectedwith thegroupofQSwhoreceivethemessagebroadcastthemessagetoalltheQStheyconnectedwith theprocedurerepeatsuntilalltheQS shavereceivedthemessage 例6 QSNetwork Asampleisshownbelow AsampleQSnetwork andQSAwanttosendamessage Step1 QSAsendsmessagetoQSBandQSC Step2 QSBsendsmessagetoQSA QSCsendsmessagetoQSAandQSD Step3 theprocedureterminatesbecausealltheQSreceivedthemessage 例6 QSNetwork EachQShasitsfavoratebrandofnetworkadaptersandalwaysbuysthebrandinallofitsconnections AlsothedistancebetweenQSvary GiventhepriceofeachQS sfavoratebrandofnetworkadaptersandthepriceofcablebetweeneachpairofQS yourtaskistowriteaprogramtodeterminetheminimumcosttosetupaQSnetwork InputThe1stlineoftheinputcontainsanintegertwhichindicatesthenumberofdatasets Fromthesecondlinetherearetdatasets 例6 QSNetwork InputThe1stlineoftheinputcontainsanintegertwhichindicatesthenumberofdatasets Fromthesecondlinetherearetdatasets Inasingledataset the1stlinec