Skip to content

Instantly share code, notes, and snippets.

@tungurlakachakcak
Last active August 29, 2022 08:57
Show Gist options
  • Save tungurlakachakcak/59fd9b3da4afedc8821035fa2f12c351 to your computer and use it in GitHub Desktop.
Save tungurlakachakcak/59fd9b3da4afedc8821035fa2f12c351 to your computer and use it in GitHub Desktop.
DFS All paths to destination
#include <iostream>
#include <vector>
#include <math.h>
#include <unordered_map>
#include <string>
#include <fstream>
#include <stack>
using namespace std;
unordered_map<int, vector<int>> graph;
bool visited[6]{};
vector<vector<int>> paths;
vector<int> currentPath;
void dfsAllPaths(int currentVertex, int targetVertex) {
if (currentVertex == targetVertex) {
currentPath.push_back(targetVertex);
paths.push_back(currentPath);
currentPath.pop_back();
return;
}
if (!visited[currentVertex]) {
visited[currentVertex] = true;
currentPath.push_back(currentVertex);
for (int neigh : graph[currentVertex]) {
dfsAllPaths(neigh, targetVertex);
}
currentPath.pop_back();
visited[currentVertex] = false;
}
}
int main() {
graph[0] = {1, 2, 3};
graph[1] = { 0, 4, 5 };
graph[2] = { 0, 4 };
graph[3] = { 0, 4 };
graph[4] = { 2, 3, 1, 5 };
graph[5] = { 1, 4 };
dfsAllPaths(0, 1);
for (auto& path : paths) {
for (int i = 0; i < path.size(); i++) {
cout << path[i] << " ";
}
cout << endl;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment