Вы можете найти все пути, используя DFS, как | Влад описал. Чтобы найти, какие узлы появляются в каждом пути, вы можете просто сохранить массив логических значений, который сообщает, появился ли каждый узел в каждом пути до сих пор. Когда ваша DFS найдет путь, просмотрите каждую вершину , а не в пути и установите для соответствующего значения массива значение false. Когда вы закончите, только вершины со значениями true будут теми, которые появляются на каждом пути.
псевдокод:
int source;
int sink;
int nVerts;
bool inAllPaths[nVerts]; // init to all true
bool visited[nVerts]; // init to all false
stack<int> path; // init empty
bool dfs(int u)
if (visited[u])
return;
if (u == sink)
for i = 0 to nVerts-1
if !stack.contains(i)
inAllPaths[i] = false;
return true;
else
visited[u] = true;
stack.push(u);
foreach edge (u, v)
dfs(v);
stack.pop();
visited[u] = false;
return false;
main()
dfs(source);
// inAllPaths contains true at vertices that exist in all paths
// from source to sink.
Однако этот алгоритм не очень эффективен. Например, в полном графе из n вершин (все вершины имеют ребра для всех остальных), число путей будет n! (n факториал).
Лучшим алгоритмом было бы проверять наличие в каждом пути каждой вершины отдельно. Для каждой вершины попробуйте найти путь от источника к стоку, не переходя к этой вершине. Если вы не можете его найти, это потому, что вершина появляется в каждом пути.
псевдокод:
// Using the same initialisation as above, but with a slight modification
// to dfs: change the foreach loop to
foreach edge (u, v)
if (dfs(v))
return true; // exit as soon as we find a path
main()
for i = 0 to nVerts-1
set all visited to false;
if (inAllPaths[i])
visited[i] = true;
if (dfs(source))
inAllPaths[i] = false;
visited[i] = false;
К сожалению, это все еще имеет экспоненциальный худший случай при поиске пути. Вы можете исправить это, изменив поиск на поиск в ширину. Если я не ошибаюсь, это должно дать вам производительность O (VE).