Re: [VB6 ] 判斷是否為樹

[yauhh (喲)]

※ 引述《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)
→ UesugiKura:因為檢查任兩點是否只有一條路連接好像不太好寫，所以
→ UesugiKura:我想到的通則是"A到B可行"和"邊數+1=節數"，這樣應該也
→ UesugiKura:可以檢測是否為樹?　　　樹的資料結構我了解一點皮毛，
→ UesugiKura:所以像這樣子有迴路，也算樹嗎?　　另外，"第一層產生
→ UesugiKura:的原則"那段我看不懂，請問可以說的詳細一點嗎@@~