第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題,去搜搜看,總會(huì)有你想問(wèn)的

找到從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的所有路徑

找到從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的所有路徑

慕的地6264312 2021-12-09 10:34:57
試圖找到從起始頂點(diǎn)到結(jié)束頂點(diǎn)的所有可能路徑。這是我到目前為止。def all_paths(adj_list, source, destination):paths = []for neighbour,_ in adj_list[source]:    path = [source,neighbour]    state = ['U'] * len(adj_list)    state[neighbour] = 'D'    path = finder(adj_list, neighbour, state, path, destination)    paths.append(path)return pathsdef finder(adj_list, current, state, path, end):    for neighbour,_ in adj_list[current]:        if neighbour == end:            path.append(neighbour)            return path        if state[neighbour] == 'U':            state[neighbour] = 'D'            path.append(finder(adj_list, neighbour, state, path, end))            return path狀態(tài)數(shù)組是為了確保沒(méi)有頂點(diǎn)被訪問(wèn)兩次(U 未被發(fā)現(xiàn),D 被發(fā)現(xiàn))。通過(guò)邊連接到 i (Nones 是所述邊的權(quán)重)輸入是adj_list = [[(1, None), (2, None)], [(0, None), (2, None)], [(1, None), (0, None)]]print(sorted(all_paths(adj_list, 0, 2)))預(yù)期的輸出是[[0, 1, 2], [0, 2]]我的輸出是[[0, 1, 2, [...]], [0, 2, 2, [...], [...]]]不確定我是如何得到這些點(diǎn)和第二條路徑中重復(fù)的 2 的?
查看完整描述

2 回答

?
拉丁的傳說(shuō)

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

與您的代碼非常相似的邏輯,但經(jīng)過(guò)清理,因?yàn)?Python 可以檢查項(xiàng)目是否在列表中,因此不使用單獨(dú)的 'U' 或 'D' 數(shù)組。


ajs =  [[(1, None), (2, None)], [(0, None), (2, None)], [(1, None), (0, None)]]


def paths(node, finish):

    routes = []


    def step(node, path):

        for nb,_ in ajs[node]:


            if nb == finish:

                routes.append( path + [node, nb] )


            elif nb not in path:

                step(nb, path + [node])


    step(node, [])

    return routes


print paths(0,2)


查看完整回答
反對(duì) 回復(fù) 2021-12-09
?
慕斯王

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

這是獲得所需答案的代碼變體。也就是說(shuō),這是解決問(wèn)題的一種令人困惑的方法。在我看來(lái),該算法分布在兩個(gè)函數(shù)中,而它應(yīng)該可以用單個(gè)遞歸函數(shù)解決。


def main():

    adj_list = [

        [(1, None), (2, None)],

        [(0, None), (2, None)],

        [(1, None), (0, None)],

    ]

    paths = sorted(all_paths(adj_list, 0, 2))

    print(paths)


def all_paths(adj_list, source, destination):

    paths = []

    for neighbour, _ in adj_list[source]:

        pth = [source, neighbour]

        if neighbour == destination:

            paths.append(pth)

        else:

            node = finder(

                adj_list,

                neighbour,

                ['U'] * len(adj_list),

                pth,

                destination,

            )

            paths.append(pth + [node])

    return paths


def finder(adj_list, current, state, pth, end):

    for neighbour, _ in adj_list[current]:

        if neighbour == end:

            state[neighbour] = 'D'

            return neighbour

        elif state[neighbour] == 'U':

            state[neighbour] = 'D'

            return finder(adj_list, neighbour, state, pth, end)


main()

例如,這是一個(gè)替代實(shí)現(xiàn):


def main():

    # An adjacency matrix for this example:

    #

    #    0 - 1

    #     \ /

    #      2

    #

    matrix = [

        [(1, None), (2, None)],

        [(0, None), (2, None)],

        [(1, None), (0, None)],

    ]

    # Print all paths from 0 to 2.

    paths = get_paths(matrix, 0, 2)

    for p in paths:

        print(p)


def get_paths(matrix, src, dst, seen = None):

    # Setup:

    # - Initialize return value: paths.

    # - Get an independent seen set.

    # - Add the source node to the set.

    paths = []

    seen = set(seen or [])

    seen.add(src)

    # Explore all non-seen neighbors.

    for nb, _ in matrix[src]:

        if nb not in seen:

            seen.add(nb)

            # Find the subpaths from NB to DST.

            if nb == dst:

                subpaths = [[nb]]

            else:

                subpaths = get_paths(matrix, nb, dst, seen)

            # Glue [SRC] to the those subpaths and add everything to paths.

            for sp in subpaths:

                paths.append([src] + sp)

    return paths


main()


查看完整回答
反對(duì) 回復(fù) 2021-12-09
  • 2 回答
  • 0 關(guān)注
  • 355 瀏覽
慕課專(zhuān)欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢(xún)優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)