[工學(xué)]基本數(shù)據(jù)結(jié)構(gòu)-圖-文庫吧資料
2024-10-22 18:29本頁面
【正文】 connected subs that remain when that node fails. If the work has no SPF nodes, simply output the text “No SPF nodes” instead of a list of SPF nodes. Network 1 SPF node 3 leaves 2 subs Network 2 No SPF nodes Network 3 SPF node 2 leaves 2 subs SPF node 3 leaves 2 subs 1 3 4 5 2 1 3 4 5 2 1 3 4 5 2 6 關(guān)節(jié)點的特點： (1) 若深度優(yōu)先生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關(guān)節(jié)點； (2) 若生成樹中某個非葉子結(jié)點 v， 存在 v的某棵子樹的根及該子樹的其他結(jié)點均沒有指向 v的祖先的回邊，則 v是關(guān)節(jié)點。 1 2 and 2 1 specify the same connection. All node numbers will range from 1 to 1000. A line containing a single zero ends the list of connected nodes. An empty work description flags the end of the input. Blank lines in the input file should be ignored. 1 2 5 4 3 1 3 2 3 4 3 5 0 1 2 2 3 3 4 4 5 5 1 0 1 3 4 5 2 1 3 4 5 2 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 there is no SPF in the work. At least two machines must fail before there are any pairs of available nodes which cannot municate. 1 3 4 5 2 1 3 4 5 2 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 Engineering, Xidian University, China 例 5： SPF(1119) Consider the two works shown below. Assuming that data moves around these works only between directly connected nodes on a peertopeer basis, a failure of a single node, 3, in the work on the left would prevent some of the still available nodes from municating with each other. Nodes 1 and 2 could still municate with each other as could nodes 4 and 5, but munication between any other pairs of nodes would no longer be possible. 1 3 4 5 2 1 3 4 5 2 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問； (用隊列 ) 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 Engineering, Xidian University, China 深度優(yōu)先搜索 DFS V3 V2 V4 V1 V6 V5 V3 V2 V4 V1 V6 V5 ? 深度優(yōu)先遍歷圖的方法是，從 圖中某頂點 v出發(fā)： (1)訪問頂點 v； (2)依次從 v的未被訪問的鄰接點出發(fā)，對圖進(jìn)行深度優(yōu)先遍歷；直至圖中和 v有路徑相同的頂點都被訪問 (3)若此時圖中尚有頂點未被訪問，則從一個未被訪問的頂點出發(fā)，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點均被訪問過為止 (用棧 ) 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 Engineering, Xidian University, China 例 4：學(xué)校 網(wǎng)絡(luò) (續(xù) ) 4 3 1 As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the work. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school. 4 3 1 (a) (b) 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science amp。 Engineering, Xidian University, China 例 3： Is it a tree? 7 3 4 5 6 8 1 9 2 8 3 4 5 6 2 3 4 1 2 1 8 9 3 7 5 2 6 4 (a) (b) (c) 西安電子科技大學(xué)計算機(jī)學(xué)院 School of Computer Science
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1