Re: [VB6 ] 判斷是否為樹
※ 引述《UesugiKura (上杉倉)》之銘言：
: 在下今年要參加全國高職商科技藝競賽
: 小的不才 其中有一道模擬試題一直不能想通怎麼去寫
: 題目如下:
: ----------------------------------------------------
: 寫一個程式，讀入一圖形的資料，然後回答該圖是否為樹。
: 輸入說明：
: 第一列的數字n代表有幾組資料要測試，而n的值介於1和10之間。
: 第二列以後則是每一組測試資料。每組測試資料代表一圖形，內容為邊的資料。
: 每個邊以2個整數i,j表示，0<=i,j<=30，此2整數為節點的編號，
: 代表從i節點和j節點有邊相連。
: 0,0這個邊代表此組輸入資料結束。
: 輸出說明：
: 每組測試資料輸出一列，輸出每組測試資料以及該組測試資料是否為樹。
: T為樹，F不為樹。（輸出均為大寫）
: 輸入檔案1：【檔名：in1.txt】
: 5
......
: 3,8 6,8 6,4 5,3 5,6 8,2 2,0 0,0
樹的規則你講了一半，而重點是任二點之間「只有」一條路徑.
一方面要找迴路,另一方面要判斷整個圖是一個,沒有切分成二部份.
如果找到是以上二種情況,就不是樹.
前者,找迴路,作法基本是像以下這樣: 找5到6之間有沒有迴路,先從5開始建一個樹,
第一層 第二層 第三層
5 - { 8, 4, 6 } - {{3,6,2}, 6, {8,4}} -
第四層
{ {{5, {4,5}, 0}, {8,5}, {{3,2}, {}} }
每一層產生的原則,大概是看它上一層以及上上一層的關係,例如,第四層最後找到{},
是由第三層的最右邊節點4, "尋找與4相鄰的節點,但扣掉4上一層節點6" 這樣.
說是樹,其實為了程式好做,是抄寫成好幾列:
5, 8, 3, 5, ...
5, 8, 6, 4, ...
5, 8, 6, 5, ...
5, 8, 2, 0, ...
5, 4, 6, 8, ...
5, 4, 6, 5, ...
5, 6, 8, 3, ...
5, 6, 8, 2, ...
5, 6, 4
每一列查過去,會發現 5,8,3,5,... 和 5,4,6,5,... 是迴路.
至於第二個判斷,判斷任二點之間是否沒有連通 (以決定圖是否為一個完整單元),
不曉得是不是把圖結構做出來,並在裡頭走訪,看看如果全都走到盡頭卻碰不到目標,
則斷定圖型不是一個完整單元.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.167.50.25
※ 編輯: yauhh 來自: 118.167.50.25 (11/27 01:00)
→
11/27 09:18, , 1F
11/27 09:18, 1F
→
11/27 09:18, , 2F
11/27 09:18, 2F
→
11/27 09:19, , 3F
11/27 09:19, 3F
→
11/27 09:19, , 4F
11/27 09:19, 4F
→
11/27 09:20, , 5F
11/27 09:20, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：