컨셉
주어진 그래프, 그래프의 소스 정점 및 숫자 k(여기서 k는 소스 정점과 대상 정점 사이의 그래프의 경로 길이를 나타냄)와 관련하여 우리의 임무는 시작하는 단순 경로(어떤 주기도 없는)가 있는지 확인하는 것입니다. 주어진 소스에서 다른 정점(즉, 목적지)에서 끝납니다. 그래프는 다음과 같습니다 -
입력
Source s = 0, k = 64
출력
True
0 -> 7 -> 1 -> 2 -> 8 -> 6 -> 5 -> 3 -> 4의 단순 경로가 존재하는데, 총 거리는 68km로 64가 넘습니다.
입력
Source s = 0, k = 70
출력
False
위의 그래프에서 가장 긴 단순 경로의 거리가 69(0 -> 7 -> 1-> 2 -> 3 -> 4 -> 5-> 6 -> 8이므로 69보다 큰 입력에 대해서는 출력이 거짓이어야 합니다.
방법
한 가지 중요한 것은 단순히 BFS(Breadth First Search) 또는 DFS(Depth First Search)를 수행하고 모든 단계에서 가장 긴 가장자리를 선택하는 것은 작동하지 않는다는 것입니다. 그 이유는 뒤에 있는 짧은 가장자리가 그것을 통해 연결된 더 높은 가중치.
이제 개념은 Backtracking을 구현하는 것입니다. 이 경우 주어진 소스에서 시작합니다. 현재 정점에서 모든 경로를 순회합니다. 여기에서 소스로부터의 현재 거리를 추적합니다. 거리가 k 이상이면 true를 반환하는 것으로 나타났습니다. 그러나 경로가 k 거리 이상을 생성하지 않는 경우 우리는 역추적합니다.
이제 경로가 단순하고 순환하지 않는지 확인하는 방법에 대한 질문이 제기됩니다. 여기서 개념은 배열에서 현재 경로 정점의 추적을 유지하는 것입니다. 이 경우 경로에 정점을 추가할 때마다 현재 경로에 이미 존재하는지 여부를 확인합니다. 존재하는 경우 가장자리를 무시합니다.
예시
// Program to find if there is a simple path with
// weight more than k
#include<bits/stdc++.h>
using namespace std;
// iPair ==> Integer Pair
typedef pair<int, int> iPair;
// Now this class represents a dipathted graph using
// adjacency list representation
class Graph{
int V1; // Indicates no. of vertices
// In this case, in a weighted graph, we need to store vertex
// and weight pair for every edge
list< pair<int, int>> *adj1;
bool pathMoreThanKUtil(int src1, int k, vector<bool>&path1);
public:
Graph(int V1); // Shows constructor
// Shows function to add an edge to graph
void addEdge(int u1, int v1, int w1);
bool pathMoreThanK(int src1, int k);
};
// Used to return true if graph has path more than k length
bool Graph::pathMoreThanK(int src1, int k){
// Used to create a path array with nothing included
// in path
vector<bool> path1(V1, false);
// Used to add source vertex to path
path1[src1] = 1;
return pathMoreThanKUtil(src1, k, path1);
}
// Used to print shortest paths from src to all other vertices
bool Graph::pathMoreThanKUtil(int src1, int k, vector<bool>&path1){
// Now if k is 0 or negative, return true;
if (k <= 0)
return true;
//Used to get all adjacent vertices of source vertex src and
// recursively explore all paths from src.
list<iPair>::iterator i;
for (i = adj1[src1].begin(); i != adj1[src1].end(); ++i){
// Used to get adjacent vertex and weight of edge
int v1 = (*i).first;
int w1 = (*i).second;
// Now if vertex v is already there in path, then
// there is a cycle (we ignore this edge)
if (path1[v1] == true)
continue;
// Now if weight of is more than k, return true
if (w1 >= k)
return true;
// Else add this vertex to path
path1[v1] = true;
// Now if this adjacent can provide a path longer
// than k, return true.
if (pathMoreThanKUtil(v1, k-w1, path1))
return true;
// Backtrack
path1[v1] = false;
}
// Now if no adjacent could produce longer path, return
// false
return false;
}
// Used to allocates memory for adjacency list
Graph::Graph(int V1){
this->V1 = V1;
adj1 = new list<iPair> [V1];
}
//Shows utility function to an edge (u, v) of weight w
void Graph::addEdge(int u1, int v1, int w1){
adj1[u1].push_back(make_pair(v1, w1));
adj1[v1].push_back(make_pair(u1, w1));
}
// Driver program to test methods of graph class
int main(){
// Used to create the graph given in above fugure
int V1 = 9;
Graph g(V1);
// making above shown graph
g.addEdge(0, 1, 5);
g.addEdge(0, 7, 9);
g.addEdge(1, 2, 9);
g.addEdge(1, 7, 12);
g.addEdge(2, 3, 8);
g.addEdge(2, 8, 3);
g.addEdge(2, 5, 10);
g.addEdge(3, 4, 10);
g.addEdge(3, 5, 15);
g.addEdge(4, 5, 11);
g.addEdge(5, 6, 3);
g.addEdge(6, 7, 2);
g.addEdge(6, 8, 7);
g.addEdge(7, 8, 8);
int src1 = 0;
int k = 70;
g.pathMoreThanK(src1, k)? cout << "Yes\n" :
cout << "No\n";
k = 68;
g.pathMoreThanK(src1, k)? cout << "Yes\n" :
cout << "No\n";
return 0;
} 출력
No Yes