图中所有可能的路径 [英] All possible path in a graph

问题描述

给定一个图 G（V，E），一个源顶点 s 和目标顶点 d ，问题是要找到所有可能的从 s 到 d 的路径，其中 G 可能包含循环和循环。我想获得所有简单的路径，不允许循环。

Given a graph G(V, E), a source vertex s and destination vertex d, the problem is to find all possible paths from s to d where G may contain loops and cycles. I want to get all simple paths, no cycle is allowed.

这个问题的复杂性是什么？

What would be the complexity of this problem?

推荐答案

此问题是NP难题，因为其输出的输入可能成指数大小。

This problem is NP-hard, since its output may have an exponential size w.r.t its input.

找到之间的最长路径两点已经是NP难点了（减少了哈密顿路径问题），所以找到所有这些点也是一样。

Finding the longest path between two points is already NP-hard (reduction to hamiltonian path problem), so finding all of them is as well.

通过查看图中两个顶点之间的路径数，可以发现此问题具有指数复杂性。

这是一个小例子：

令 G 是具有 3n + 2 顶点的图。设 V = {s，d} U {a1，...，an} U {b1，...，bn} U {c1，...，cn} 为其顶点集。
我们按以下方式构建边：

-从 s 到 a1

-对于 i在1 ... n 中，我们从 ai到bi 建立了一条优势，从 ai到ci

-对于1..n-1 中的 i，我们建立从 bi到ai + 1 的边缘，从 ci到ai + 1 的边缘。

-从 bn到d ，从 cn到d 。

如您所见，从 s 到 d 的 2 ^ n 条路径。

You can also see that this problem has an exponential complexity by seeing that there might be an exponential number of paths between two vertices in a graph.
Here is a small example:
Let G be a graph with 3n+2 vertices. Let V = {s,d} U {a1, ..., an} U {b1, ..., bn} U {c1, ..., cn} be its vertex set. We build edges as follow:
-from s to a1
- for i in 1...n, we build an edge from ai to bi, from ai to ci
- for i in 1..n-1, we build an edge from bi to ai+1, from ci to ai+1.
- from bn to d, from cn to d.
As you can see, there are about 2^n paths from s to d.

这篇关于图中所有可能的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！