已解決430363個問題，去搜搜看，總會有你想問的

c++ 圖論數據結構不用<map>實現嗎？

關注

首頁猿問 c++...

C++ 算法與數據結構

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

看書上說可以用<map>實現圖的數據結構，而我百度了，幾乎沒找到這樣的記錄，是不好實現嗎？

查看完整描述

2 回答

叮當貓咪

TA貢獻1776條經驗獲得超12個贊

map的話，可以用一對頂點的標識（例如id或者內存地址）組成的pair作為鍵，權重數字作為值。

這類似于用二維數組建立鄰接矩陣。若鄰接矩陣比較稀疏，用map比用二維數組空間上節省一些，時間上多耗費一些。

反對回復 2018-10-29

HUX布斯

TA貢獻1876條經驗獲得超6個贊

圖論的常用算法需要的數據結構無外乎鄰接矩陣和鄰接表，鄰接矩陣肯定是數組或者Vector了，鄰接表的話用鏈表，每個元素又是數組，也可以用Vector,map的優勢只是可以給頂點取一個不是數字的序號，而直接叫A,B,C,并沒有明顯優勢。

反對回復 2018-10-29

關注

舉報

0/150

提交

取消