当前位置: 首页 > 資訊 >

DAY7 - 圖

之後會有幾天與圖相關的演算法,所以今天先看一下表示方式~~
https://ithelp.ithome.com.tw/upload/images/20210907/20140739ocLXxInR2H.png


1135. 最低成本联通所有城市這題所用的表示法就是
(node_a, node_b, weight)表示節點a與節點b有連接,並且邊的權重是weight,其實描述的就是邊
題目敘述部分:
conections = [[1,2,5],[1,3,6],[2,3,1]]


相鄰

802. 找到最终的安全状态這題用的表示法像是這樣
graph = [[1,2],[2,3],[5],[0],[5],[],[]]
下標0表示節點0,[1,2]表示節點0與1, 2連接


鄰接矩陣

547. 省份数量這題就用到鄰接矩陣(adjacency matrix)來表示圖的連接情形
graph =
[[1,0,0,0,0,0,1],
[1,1,0,0,0,1,1],
[1,0,1,0,1,0,1],
[1,1,0,1,0,0,1],
[1,0,1,0,1,0,1],
[1,0,1,0,0,1,1],
[1,0,0,0,0,0,1],]

graph[i][j]表示節點i, j相鄰(如果圖是無向圖,鄰接矩陣會對稱)


今天看一下圖在題目中怎麼表示,明天就可以開始做圖相關的題目了~~