如何在图中找到先决条件的总数

Question

我有以下图形节点：

这些节点代表视频游戏中角色的技能。第0^个节点是所有角色开始的基础技能。第1^st节点是需要第0^th节点作为前提的技能。同样，第2^nd节点需要第1^st节点作为技能，这就需要第0^th节点作为技能。但是，当一个技能学会了，就不需要再学了。

我得到一个数组 T，它是 [0,0,1,1] 和一个数组 A，它是 [2]。只有学习了T[k]^th技能才能学习第K技能。 0 是根，因此无需任何其他技能即可学习。上面的数组解释如下：T[0] = 0、T[1]=0、T[2]=1、T[3]=1，因此 T=[0,0,1,1]。数组 A 告诉我我想学习的技能。我的输出需要是我需要学习技能 2 的技能总数。在上面的例子中，答案是 3

示例 2

在 2^nd 图中，答案是 5，因为我被要求学习 2、5、6，所以我将学习 0、2、3、5 和6. 我的输入是：T=[0,0,0,0,2,3,3] 和 A = [2,5,6]

我一直在想怎么解决这个问题。这是一个改进我的图论的编码练习。但是我不知道如何在算法上关联T列表和A列表。

示例 3

在上面的例子中T = [0,3,0,0,5,0,5]和A = [4,2,6,1,0]。我创建了 X = [0,1,2,3,4,5,6] 来将 T 映射到它的连接。

我知道什么？

0 已经总是学习所以 count = 1
学习4.

为了学4，我必须学5，所以这让我学了0（已经学会了）。计数 = 1 + 2 = 3
学习2.

要学2，就得学0。count = 3 + 1 = 4
学习6.

要学6，我得学5（已经学过），这让我学了0（已经学过）。计数 = 4 + 1 = 5
学习1.

要学1，就得学3，这让我学了0（已经学了）。计数 = 5 + 2 = 7

所以我要return这个数，也就是7

我的代码

到目前为止，这是我所拥有的：

def sol(T,A):
    count = 1
    x = [i for i in range(len(T))]

    if 0 in A:
       A.remove(0)

    for i in range(0, len(A)):
        indx = x.index(A[i])
        if T[indx]==0:
           count += 1
           break
        else:
           # nothing yet

Answer 1

您确实可以使用递归作为深度优先遍历的实现（广度优先遍历也可以）。使用 set 来跟踪您已经访问过的节点。对于更大的输入，这将比调用 index.

更有效

这是一个递归算法。请注意，我使用 itertools 将多个结果合并为一个。还有许多其他方法可以做到这一点：

import itertools

def sol(tree, needed):
    visited = set()

    def dfs(node):
        if node in visited:
            return []
        visited.add(node)
        return dfs(tree[node]) + [node] if node else [0]

    return list(itertools.chain(*map(dfs, needed)))

这会输出需要学习的技能，所以你只需要慢慢来，就能得到想要的答案。但是，获取此列表可能会有用：它也会按照您可以学习这些技能的顺序返回，始终从 0 开始，并确保在您坚持该顺序时满足先决条件。

Answer 2

正如@Nuclearman 在评论中所说，您想找到通往您需要学习的所有技能的最短路径。

您还需要知道的是，这是图论中的标准问题，使用 Dijkstra 算法可以最有效地解决该问题。您可以找到该算法的大量描述和实现它的示例代码。

但为什么要重新发明轮子呢？任何图形库都将提供经过良好测试的高效实现。我使用升压图。

算法：

read input
Run Dijsktra
loop over required skills
   loop over path to required skill (from Dijsktra run )
       if not skill already learned
           record new skill
display skills learnt

我使用 PathFinder C++ wrapper 作为 boost 图形库

输入

t 0 0 0 0 2 3 3
a 2 5 6

输出

skill 2 needs 0 2
skill 5 needs 0 2 5
skill 6 needs 0 3 6
Total skills needed 5 ( 0 2 3 5 6  )

输入例如3

t 0 3 0 0 5 0 5
a 4 2 6 1 0

输出

skill 4 needs 0 5 4
skill 2 needs 0 2
skill 6 needs 0 5 6
skill 1 needs 0 3 1
Total skills needed 7 ( 1 3 2 0 4 5 6  )

密码

void doPreReqs()
{
    cPathFinder finder,
    cPathFinderReader reader( finder );
    std::set<int> setSkillsNeeded;

    // read input. va are the required skills
    auto va = reader.singleParentTree();

    // starting node
    finder.start("0");

    // paths to all end nodes
    finder.end(-1);

    // run Dijsktra
    finder.path();

    // loop over required skills
    for (auto &a : va)
    {
        // skill 0 does not need to be learned
        if( a == "0" )
            continue;

        //skills needed to get required skill
        auto path = finder.pathPick(finder.find(a));

        std::cout << "skill " << a << " needs ";
        for (int s : path)
            std::cout << finder.nodeName(s) << " ";
        std::cout << "\n";

        //loop over prerequsites
        for (auto s : path)
        {
            //record skill if not already learned
            setSkillsNeeded.insert(s);
        }
    }

    std::cout << "Total skills needed "
              << setSkillsNeeded.size() << " ( ";
    for (int s : setSkillsNeeded)
        std::cout << finder.nodeName(s) << " ";
    std::cout << " )\n";
}

我已将此作为图形用户界面中的一个选项添加到探路者。 Documentation.

Answer 3

您可以通过迭代方法使用 collections.deque：

from collections import deque
def earn_skill(T, A):
   a, r = deque(A), [0]
   while a:
      if not T[(n:=a.popleft())] or any(j in r for j in T[:n]):
         r.extend([T[n], n])
      else:
         return
   return len(set(r))

vals = [([0,0,1,1], [2]), ([0,0,0,0,2,3,3], [2,5,6]), ([0,3,0,0,5,0,5], [4,2,6,1,0])]
r = [earn_skill(t, a) for t, a in vals]

输出：

[3, 5, 7]

如何在图中找到先决条件的总数

How to find the total of prerequisites in a graph

python

algorithm

graph-theory

示例 2

示例 3

我的代码