algorithm - 图:使用包含通配符的节点列表查找子图

Question

下面的问题有名字吗？是否有解决它的算法？ :给定一个图，无论是否有向，找到所有满足给定规范的路径

1. 确切节点列表，或
2. '*?'仅表示“任何节点或根本没有节点”，或者
3. '*{n}'表示'任何n个连续连接的节点'

例如

A -> B -> *? -> D which results in ABXD and ABYD and ABD etc.

或

A -> *{1} -> D -> *? -> E which results in ABXDZE and ABYDZE and ABDZE etc. etc.

谢谢

附注有谁知道在 R 或 perl 或 C 中执行此操作的图形库？

Answer 1

我不知道有什么库，但你必须把它分成两部分:

• 用户查询解析
• 找到你要找的东西的算法

对于解析，我让你找到你需要做什么(使用解析库或你自己)

关于算法部分，我建议您定义一个特殊结构(如链表)来表示您的查询，其中每个元素可以表示一个真实节点、x 个节点或无限数量的节点。

你的算法的唯一问题是找到从节点 A 到节点 B 的所有路径，使用无限数量或有限数量的中间节点。您可以使用动态规划或搜索算法(例如 DFS 或 BFS)来执行此操作。