鍍金池/ 問(wèn)答/HTML/ JS用什么數(shù)據(jù)類(lèi)型表示有向無(wú)環(huán)圖？

JS用什么數(shù)據(jù)類(lèi)型表示有向無(wú)環(huán)圖？

問(wèn)題描述：現(xiàn)在有一個(gè)有向無(wú)環(huán)圖，每一個(gè)節(jié)點(diǎn)上都有正數(shù)權(quán)重，現(xiàn)在希望找出一條最優(yōu)路徑，使得經(jīng)過(guò)的節(jié)點(diǎn)權(quán)重之和最大。
輸入：n個(gè)節(jié)點(diǎn)，m條路徑，起點(diǎn)
例如：
3個(gè)節(jié)點(diǎn)
A 1
B 2
C 2
3條路徑
A->B
B->C
A->C
起點(diǎn)：A
輸出：5（最優(yōu)路徑是A->B->C,權(quán)重：1+2+2=5）

問(wèn)題：用什么樣的數(shù)據(jù)結(jié)構(gòu)去表示這個(gè)圖開(kāi)始計(jì)算呢？

回答
編輯回答
情已空

權(quán)重不應(yīng)該是在邊上面的么

// 節(jié)點(diǎn)
var points = ['A', 'B', 'C']
// 邊 [點(diǎn)1,點(diǎn)2，權(quán)重]
var edges = [[0, 1, 1], [1, 2, 2], [0, 2, 2]]
2018年5月23日 07:47
編輯回答
命于你

用圖這種結(jié)構(gòu)，用鄰接表來(lái)存儲(chǔ)你的節(jié)點(diǎn)，用廣度優(yōu)先遍歷的算法解出你要的數(shù)據(jù)，當(dāng)中Map類(lèi)可以存放你的鄰接表（定點(diǎn)的名字作為鍵，鄰接頂點(diǎn)列表作為值）

2017年5月1日 22:11
編輯回答
失魂人

這是那道題
圖片描述

2018年5月10日 22:19