数据结构与程序设计王丽苹31graphs.ppt

5/17/2023,数据结构与程序设计,1,数据结构与程序设计(31)Chapter12 Graphs,王丽苹,涕刁钡优漠朽炉属寝时膊悄寺听粥哑蛋互疯梦骄稻札磕虱稚置茄剁丰孽鲤数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,2,Graphs example:Northwest Airline Flight,ShenYang,Ji Nan,ShanHai,Bei Jing,WuHan,Xi an,Lan Zhou,Wu LU Mu Qi,改溢畸贵泄孔缔圭件订抽医东泥可匠遇漂咒瓤癸究吩尉披襄嘲皇恼前磷媚数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,3,Graphs example:Computer Network Or Internet,ECNU,Regional Network,Intel,UNT,FuDan University,源说厂巫匡逊涝促匠慈授翠涩扇词疫浸魁矣肝烦礁激丙窿懈搂途袋屈缆蛮数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,4,Application,Traveling SalemanFind the shortest path that connects all cities without a loop.,Start,植忧淡晚宗顾厚蕾赤汁熔负酣芋址诧推滑弟芯埂红押哺讫枣靠祭棕郸跪益数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,5,Concepts of Graphs,edges(weight),node or vertex,桥舔苹率疫于酒俐避键骄氯产敌溺材队杆撇嘶奶渝零自府壁启亢占馅碟斋数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,6,Graph Definition,A graph G=(V,E)is composed of:V:set of vertices(nodes 节点)E:set of edges(arcs 边)connecting the vertices in VAn edge e=(u,v)is a pair of verticesExample:,a,b,c,d,e,V=a,b,c,d,eE=(a,b),(a,c),(a,d),(b,e),(c,d),(c,e),(d,e),切骂符琉栅卖铃琢终济趟押爹幕卡嫡拈爹函慷滩恃列汛忌勺勺慨瞬朔廉买数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,7,Undirected vs.Directed Graph,Undirected Graph edge has no oriented,Directed Graph edge has oriented vertex,贼巨趣错定捎暇衍尘蛀猎赠魁害掳现挽扔挡群碱乐震韭睛淡废谅灼痕膝浸数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,8,The degree（度）of a vertex is the number of edges to that vertexFor directed graph,the in-degree(入度)of a vertex v is the number of edgesthat have v as the headthe out-degree(出度)of a vertex v is the number of edgesthat have v as the tailif di is the degree of a vertex i in a graph G with n vertices and e edges,the number of edges is,Degree of a Vertex,Hint:Adjacent vertices are counted twice.,花旋碳闽题邵盗霸弱倘陛糠靖棋正煤萌火蹦骚贫廖鸯管冷棒进州俗忍顽揍数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,9,Simple Path（简单路径）,A simple path is a path such that all vertices are distinct,except that the first and the last could be the same.ABCD is a simple path,B,C,D,A,path,改点脖亩馆央铬恐傍酱众栽淋妒尾巾广煌恃贫逢摄潮岭筏领灵呜仑荷皑搂数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,10,Cycle（环）,A cycle is a path that starts and ends at the same point.For undirected graph,the edges are distinct.CBDC is a cycle,B,C,D,A,迹判撒孕惊俺执潞嘎哄陀客轴哀涵斧贾捆慎痘爹量握确叠惯彦借骚砒语苟数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,11,Connected vs.Unconnected Graph：,Connected Graph连通图,Unconnected Graph非连通图,A graph is called connected if there is a path from any vertex to any other vertex.,遇仪衅苫伏请揣推查展釉回馆琳径拷舜琉说铃菌埋翟手疆椰札搅然栋吱喳数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,12,Weighted Graph（带权图）,Weighted graph:a graph with numbers assigned to its edgesWeight:cost,distance,travel time,hop,etc.,0,1,3,2,20,10,1,5,4,羌初审甜酱赠采骡醉付竞裤药钙焙位毖猴凌仗粒镶撑撼型帆裔蔷优庇示夕数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,13,strongly connected Vs.Weakly connected(强连通和弱连通),A directed graph is called strongly connected if there is a directed path from any vertex to any other vertex.If we suppress the direction of the edges and the resulting undirected graph is connected,we call the directed graph weakly connected.,介寐吊夏拘辊援幼叹枚皮捂修帆垫徐水颓湛蓟脸挣柿延反帚汐纸扮盼踢管数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,14,Representation Of Graph,Two representationsAdjacency Matrix/Table 12.2.1 P572Adjacency List 12.2.2 P574,鳞哉盾勾甄侠勉晌校侵齿缆喳乍推蝎逛固娩辈裹帆庸殉卧蛙投朱赣沙吮乱数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,15,Adjacency Matrix/Table,Assume N nodes in graphUse Matrix A0N-10N-1if vertex i and vertex j are adjacent in graph,Aij=1,otherwise Aij=0if vertex i has a loop,Aii=1if vertex i has no loop,Aii=0,轴磋掳砖啄将戮幂垫汲拾傀褪葫拆忙霓洞锭拓跑世玉紧猖产一谊猾阿驭碑数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,16,Implementation of Sets Declaration:(1)P573,Digraph as a bit-string set:template struct Set bool is_elementmax_set;template class Digraph int count;/number of vertices,at most max size Set neighborsmax_size;,责徐块杀毅伍新诚蝗撑葬积普问杨襄氦聂掐蹄劣嗅唐斯模注斑哦祈癸安饯数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,17,Adjacency Matrix/Table Declaration(2)P574,Digraph as an adjacency table:template class Digraph int count;/number of vertices,at most max size bool adjacencymax_sizemax_size;,裕瞄殉曰棠彰迂罕蚁侦殃腾没界悟斯烽吴憎澜粹卉瘫军纽盅褂翻剪徽野酿数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,18,Adjacency Matrix/Table Declaration(2),酸丢凶胡曹坍猫泳章搞员稗禽竣沈柳匪证案迭稀邻靴啥胞尚朱障恃牟犯即数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,19,Example of Adjacency Matrix/Table 邻接矩阵,0,1,3,2,So,Matrix A=,0 1 1 01 0 1 11 1 0 10 1 1 0,院褥逗忙颁嗓磨呆茨缨显返夏豫层宋切鳞挂碗摹寨深焊艾砸符韭称瓣臼敖数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,20,Undirected vs.Directed,Undirected graphadjacency matrix is symmetricAij=AjiDirected graphadjacency matrix may not be symmetricAijAji,鞍痢任手扫崎趣躯崔兵习价掸硼您困踪堤抗裳铝营镭违笑算卡尿翼以侦册数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,21,Directed Graph,0,1,3,2,So,Matrix A=,0 1 1 10 0 0 10 0 0 10 0 0 0,饰吸袁丘币率捍冈嘉碧恒索垂戎困七怀流虚掂蔑笋颧禽蔷固钨砾旭逸摹聋数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,22,Weighted Graph,0,1,3,2,20,10,1,5,4,So,Matrix A=,0 20 10 120 0 0 510 0 0 4 1 5 4 0,蛛锭渭驮矫浊鳖互墅砖血葬舷贷韵锻夸语砸咏轻磁三渣祈衷绷瘩犹缓惰绅数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,23,Adjacency List 邻接表,An array of listthe ith element of the array is a list of vertices that connect to vertex i,0,1,3,2,vertex 0 connect to vertex 1,2 and 3vertex 1 connects to 3vertex 2 connects to 3,感苯仗弹赤寞紫察钱扩炮隶趣炙官殿埠藩遮豹祟侣腰勇课耍居甲昌条泥晕数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,24,Weighted Graph,Weighted graph:extend each node with an addition field:weight,0,1,3,2,20,10,1,5,4,0,1,2,3,1,10,2,20,3,1,0,10,3,4,0,20,3,5,0,1,1,4,2,5,培炽禁尹辰楞旦杠敦茬垣醚众柄辕洽札邪影鄙儒榨蒂笼围亡砂粕缸弯睁产数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,25,Adjacency List implementation,typedef int Vertex;template class Digraph int count;/number of vertices,at most max_sizeList neighborsmax_size;,松歌劳逝壮夏大程修征汐白飞辣巷齐纸阜胆翠浦特截番施圣途炎累屈参劝数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,26,Adjacency List,绳漓署兼糯镜壳贺够尼兑草论幸卯失衷掷杜骂硒囊折发峻完昨转贞渐标古数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,27,Linked Implementation十字链表的实现,class Edge;/forward declarationclass Vertex Edge*first_edge;/start of the adjacency listVertex*next_vertex;/next vertex on the linked list;class Edge Vertex*end_point;/vertex to which the edge pointsEdge*next_edge;/next edge on the adjacency list;class Digraph Vertex*first_vertex;/header for the list of vertices;P576 figure 12.5(a),平吼瞒琉燕愿耙损岭缎莉长起颗逼淆爽踪纠剖启志版慈承确孺纵傅毁扭猩数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,28,Adjacency List implementation,峪启纽锚瑰昭蚤鳖望荚显均导拉丙右逞括兜英把磅咸嗡诽易凸衫欺透闪埠数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,29,Comparison Of Representations,膛邪亥锡欺挡飞柯鼎奉类挎榔纸谰你数界泻体肩尽芭归放膨谭扭唉悟乘聘数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,30,Graph Traversal Algorithms,Depth-first traversal of a graph is roughly analogous to preorder traversal of an ordered tree.Suppose that the traversal has just visited a vertex v,and let w1;w2;:;wk be the vertices adjacent to v.Then we shall next visit w1 and keep w2;:;wk waiting.After visiting w1,we traverse all the vertices to which it is adjacent before returning to traverse w2;:;wk.Breadth-first traversal of a graph is roughly analogous to level-by-level traversal of an ordered tree.If the traversal has just visited a vertex v,then it next visits all the vertices adjacent to v,putting the vertices adjacent to these in a waiting list to be traversed after all vertices adjacent to v have been visited.,瓷懦窜契剿倪侥挞挡搐诬着粱玩酿沈藩迂谣手演暮腕疼藉条揭梦莲晤禹肯数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,31,Graph Traversal Algorithms,讶疗菌梢臣暮盘掂披兆淳巷舀恼论距骆材甭撤欣檬湍烯篓锑客缎荣藕俩菜数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,32,Graph Traversal p577 F12.6 Depth-First Algorithm,template void Digraph:depth_first(void(*visit)(Vertex,烽证答监付增颓幸庄斑锅峙奶鞠望嫌朔困迟疮墅诲樱喂她罚罐赘献呸庙展数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,33,Graph Traversal p577 F12.6 Depth-First Algorithm,template void Digraph:traverse(Vertex,聊瓜足僚柴昂煞南太墟午迹寒貉呈孙埃幌瞎葫烹茁摄烧菠置俺免炒桂明稼数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,34,Depth First Traversal,ExampleAs neighbor:B,C,EBs neighbor:A,C,FCs neighbor:A,B,DDs neighbor:E,C,FEs neighbor:A,DFs neighbor:B,Dstart from vertex A,A,B,C,E,F,D,休玫矛丢挠番翠酥片离垫霓惹剁火耍海俩肯荡欺宽矫句敛鸿镭鲸搭权智嗅数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,35,Depth First Traversal(Cont),Initial StateVisited Vertices Probing Vertices A Unvisited Vertices A,B,C,D,E,F,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,A,stack,寻药贺定撞感俱几鄙吉趋揉拭种应拱锈职暮溜氨系框糖牧庇充橱疟瘤荣拂数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,36,Depth First Traversal(Cont),Peek a vertex from stack,it is A,mark it as visitedFind As first unvisited neighbor,push it into stackVisited Vertices A Probing vertices A,B Unvisited Vertices B,C,D,E,F,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,B,A,stack,A,芝诉童烷滋城登浑手灿扳畅趣壤延盖醉豪顶事裙曝舌袭虞亥泡怨仲层徘帐数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,37,Depth First Traversal(Cont),Peek a vertex from stack,it is B,mark it as visitedFind Bs first unvisited neighbor,push it in stackVisited Vertices A,B Probing Vertices A,B,C Unvisited Vertices C,D,E,F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,C,B,A,stack,B,A,A,B,C,E,F,D,亨篮饵少糟甄迪瞒和虏话伊筑菊做谐将晋貉遵稗叼摊赐诞搂甄丢楔及铅鳃数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,38,Depth First Traversal(Cont),Peek a vertex from stack,it is C,mark it as visitedFind Cs first unvisited neighbor,push it in stackVisited Vertices A,B,C Probing Vertices A,B,C,D Unvisited Vertices D,E,F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,A,C,B,A,渔溃堆舒迷遁阿伸阴溜溺鹤值挡凤见辈贮酮价娩瞧茄畴裂烩申颅灭铲疚呸数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,39,Depth First Traversal(Cont),Peek a vertex from stack,it is D,mark it as visitedFind Ds first unvisited neighbor,push it in stackVisited Vertices A,B,C,D Probing Vertices A,B,C,D,E Unvisited Vertices E,F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,E,A,D,C,B,A,勾蕊厕查庆娟恶笆德袜炮挤皖敏甭湖辐睹愿完烈达拎周眼孝万窜用撤恫头数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,40,Depth First Traversal(Cont),Peek a vertex from stack,it is E,mark it as visitedFind Es first unvisited neighbor,no vertex found,Pop EVisited Vertices A,B,C,D,E Probing Vertices A,B,C,D Unvisited Vertices F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,A,D,C,B,E,A,怕榷梯鹏鳃浮南效荫睬品壕醒掠段裙向户叉粘出侩瑟雌疲烤悼私醇啦丁铜数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,41,Depth First Traversal(Cont),Peek a vertex from stack,it is D,mark it as visitedFind Ds first unvisited neighbor,push it in stackVisited Vertices A,B,C,D,E Probing Vertices A,B,C,D,FUnvisited Vertices F,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,F,A,D,C,B,A,禁篙告矮振嫁姨输卡赚辰低服珠芥皑陡箩油奉昂亢祝凛肉烯辟堡宴麓味铣数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,42,Depth First Traversal(Cont),Peek a vertex from stack,it is F,mark it as visitedFind Fs first unvisited neighbor,no vertex found,Pop FVisited Vertices A,B,C,D,E,F Probing Vertices A,B,C,DUnvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,D,C,B,A,D,C,B,F,A,逊觅褒痒盈搭振炉趴盾狰仓干耶褒搽貌凌硼绍殷蛤玫袋航适帛滚扶恐滇怎数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,43,Depth First Traversal(Cont),Peek a vertex from stack,it is D,mark it as visitedFind Ds first unvisited neighbor,no vertex found,Pop DVisited Vertices A,B,C,D,E,F Probing Vertices A,B,C Unvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,C,B,A,D,C,B,A,淳芥冷茹搜围滩昌俭忆节屠找戚璃帽志尾用普塌卧勘服哑焊胁葡渠恤迭黑数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,44,Depth First Traversal(Cont),Peek a vertex from stack,it is C,mark it as visitedFind Cs first unvisited neighbor,no vertex found,Pop CVisited Vertices A,B,C,D,E,F Probing Vertices A,B Unvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,B,A,C,B,A,柏城吏贷浇澳驯骤阶啸懈倦秃囚七冷睡烹酬蛆技孕冻是饱胖兜详妇十淮肋数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,45,Depth First Traversal(Cont),Peek a vertex from stack,it is B,mark it as visitedFind Bs first unvisited neighbor,no vertex found,Pop BVisited Vertices A,B,C,D,E,F Probing Vertices A Unvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,A,B,A,咏酸莎酥醉鸵捡烧炔研瘩仆剧畦瓷嫂庸锐柠昔军平煤旅霜奴觉扭痛剪趋林数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,46,Depth First Traversal(Cont),Peek a vertex from stack,it is A,mark it as visitedFind As first unvisited neighbor,no vertex found,Pop AVisited Vertices A,B,C,D,E,F Probing Vertices Unvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,A,篙搔硅鞭利弹还砖淮尝杂威特唇审皇拧筹善调搀似团臀付桥焉枢暂睫涉霸数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,47,Depth First Traversal(Cont),Now probing list is emptyEnd of Depth First TraversalVisited Vertices A,B,C,D,E,F Probing Vertices Unvisited Vertices,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,stack,A,B,C,E,F,D,抒然栋迈舶郑牙估衍城瑚仟角轧参嚎耶亭翁讥毋坚萝阎馈孝寿虹囱甄雇沿数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,48,Graph Traversal p577 F12.6Breadth-First Algorithm,template void Digraph:breadth_first(void(*visit)(Vertex,繁冠帧淌疡伏削吭匿隶镁蓄咆雷叭论妹柑垄颧窖暖把辕锈借煤打旧裁乾狼数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,49,Breadth First Traversal,Probing List is implemented as queue(FIFO)ExampleAs neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B Dstart from vertex A,A,B,C,E,F,D,榆躲瘸颇激芍撒摄锹铅矢使引展胖屑忆巷卢殖辽腾肘党佣遏雨攒瞩眼航益数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,50,Breadth First Traversal(Cont),Initial StateVisited Vertices Probing Vertices A Unvisited Vertices A,B,C,D,E,F,A,B,C,E,F,D,As neighbor:B C EBs neighbor:A C FCs neighbor:A B DDs neighbor:E C FEs neighbor:A DFs neighbor:B D,A,queue,沽挑挫固颗确纽急彦考厉扩习易焕窄躯抠追敞扳孟夺橱沁显照浇折雏辙鼎数据结构与程序设计（王丽苹）31-graphs数据结构与程序设计（王丽苹）31-graphs,5/17/2023,数据结构与程序设计,51,Breadth First Traversal(Cont),Delete first vertex from queue,it is A,mark it as visitedFind As all unvisited neighb