使用adjaceny矩陣來解決圖形問題

我只是想知道如何使用和鄰接矩陣來解決圖形問題。使用adjaceny矩陣來解決圖形問題

例如對於我的程序我有兩個項目的匯率。

輸入來構建有向圖：6件襯衫15個襪子輸入來構建有向圖：2個襪子1個內衣

向圖：

球衣 - （6/15） - 襪 - - （2/1） - 內衣

所以從襯衫到襪子邊緣6，從襪子邊緣到襯衫是15，襪子內衣是2和內衣襪子是1

輸入到比較：襪子襯衫 Soluti於：15個襪子6件襯衫

輸入比較：襯衫內衣 Soltuion：12件襯衫15衣褲

我的問題是我怎麼能代表這與鄰接矩陣，並能夠得到它的重量來解決問題。

我正在考慮有一個鄰接矩陣，看起來像這樣的上述問題。

  shirts socks underwear 
shirts [ 0  6  0 ] 
socks  [ 15  0  2 ] 
underwear [ 0  1  0 ]

這是一個好的開始？我試圖在代碼之前獲得邏輯。

只是尋找更多的信息，如何做到更大的規模與更多的項目和單獨的圖表。

來源

2012-03-27 Claud

我可能會誤解手邊的問題，但我在這裏看不到圖表。你的頂點是什麼？襪子和襯衫？你的邊緣是什麼？你想應用哪種圖形算法？ – amit 2012-03-27 16:35:15

@amit：我認爲OP想要把它看作一個雙色圖，頂點的顏色是襯衫，顏色是襪子。 – Cam 2012-03-27 16:40:55

@amit說什麼。你想要構建什麼樣的圖形？說實話，我什至不明白你現在要解決什麼問題。您可能需要更清晰的示例來顯示您想要解決的問題以及如何使用鄰接矩陣。 – blahman 2012-03-27 16:41:29

我會給你一個關於什麼是鄰接圖的基本提示。解決你的問題是你的功課，所以我做不到。

設想以下圖：

A-----B 
/\ | \ 
/ \ | \ 
/ \ | \ 
C-------D-----E

鄰接矩陣告訴這在圖形節點被連接到：

A B C D E 
A [ 0 1 1 1 0 ] 
B [ 1 0 0 1 1 ] 
C [ 1 0 0 1 0 ] 
D [ 1 1 1 0 1 ] 
E [ 0 1 0 1 0 ]

例如條目（d，E）示出了d和E （A，E）顯示A和E不是。請注意，此矩陣是對稱的，因爲圖形是無向的。

如果矩陣如下進行加權：

A--3--B 
/\ | \ 
    5 3 2 1 
/ \ | \ 
C---2---D--7--E

然後鄰接矩陣顯示被連接以怎樣的重量（假設0顯示沒有連接）：

A B C D E 
A [ 0 3 5 3 0 ] 
B [ 3 0 0 2 1 ] 
C [ 5 0 0 2 0 ] 
D [ 3 2 2 0 7 ] 
E [ 0 1 0 7 0 ]

在你的情況，你的圖是一堆節點有邊緣的一堆節點。你的鄰接矩陣看起來與你已經提出的非常相似，但是這些值可能不正確。值應該是相同的，彼此相反，或者相反，取決於你的算法將會是什麼。

來源

2012-03-27 16:46:28 Shahbaz

我認爲我的問題我使用有向圖，這是我有6/15的原因，因爲從襯衫到襪子的邊緣是6，從襪子到襯衫的邊緣將是15. – Claud 2012-03-27 16:57:47

我不知道你的問題，這些權重代表什麼或者你需要計算什麼，所以我不能確定應該在哪些值。這將成爲我猜想的家庭作業解決方案的一部分。 – Shahbaz 2012-03-27 17:02:25

我想要計算的是匯率，所以6件襯衫價值15雙襪子。你的圖表無論如何幫助我。如果我想比較襯衫和襪子之間的匯率，那麼6件襯衫就會價值15雙襪子。如果我想要襪子和襯衫之間的匯率，那麼15雙襪子價值6件襯衫。我不知道這是否有道理，但正如我所說的那樣，您的答案迄今爲止都有幫助。 – Claud 2012-03-27 17:09:02

This是我之前寫的關於如何使用鄰接矩陣或鄰接表來描述圖的文章。

它討論瞭解決Minimum Spanning Tree圖問題和哪個數據結構適合於解決問題。我不確定你在圖表問題上想要完成什麼，但這將是您代表圖表的一個起點。如果您添加更多信息，我會嘗試編輯我的答案。

來源

2012-03-27 16:45:08 blahman

使用adjaceny矩陣來解決圖形問題

回答

相關問題