首頁(yè) 猿問 c++...

c++ 圖論數(shù)據(jù)結(jié)構(gòu)不用<map>實(shí)現(xiàn)嗎？

C++ 算法與數(shù)據(jù)結(jié)構(gòu)

慕森卡 2018-10-10 17:35:24

看書上說可以用<map>實(shí)現(xiàn)圖的數(shù)據(jù)結(jié)構(gòu)，而我百度了，幾乎沒找到這樣的記錄，是不好實(shí)現(xiàn)嗎？

查看完整描述

2 回答

叮當(dāng)貓咪

TA貢獻(xiàn)1776條經(jīng)驗(yàn) 獲得超12個(gè)贊

map的話，可以用一對(duì)頂點(diǎn)的標(biāo)識(shí)（例如id或者內(nèi)存地址）組成的pair作為鍵，權(quán)重?cái)?shù)字作為值。

這類似于用二維數(shù)組建立鄰接矩陣。若鄰接矩陣比較稀疏，用map比用二維數(shù)組空間上節(jié)省一些，時(shí)間上多耗費(fèi)一些。

反對(duì) 回復(fù) 2018-10-29

HUX布斯

TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超6個(gè)贊

圖論的常用算法需要的數(shù)據(jù)結(jié)構(gòu)無外乎鄰接矩陣和鄰接表，鄰接矩陣肯定是數(shù)組或者Vector了，鄰接表的話用鏈表，每個(gè)元素又是數(shù)組，也可以用Vector,map的優(yōu)勢(shì)只是可以給頂點(diǎn)取一個(gè)不是數(shù)字的序號(hào)，而直接叫A,B,C,并沒有明顯優(yōu)勢(shì)。

反對(duì) 回復(fù) 2018-10-29