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

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

數(shù)據(jù)結(jié)構(gòu)

牧羊人nacy 2018-08-11 21:14:30

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

查看完整描述

2 回答

泛舟湖上清波郎朗

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

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

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

反對(duì) 回復(fù) 2018-08-19

慕娘9325324

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

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

反對(duì) 回復(fù) 2018-08-19