数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学查找C++中从源点出发长度大于k的路径
概念
对于给定的图，图中的源顶点和一个数字k（这里k表示源顶点和目标顶点之间图的路径长度），我们的任务是确定是否存在从给定源点开始到任何其他顶点（即目标顶点）结束的简单路径（没有任何环路）。图如下所示：
输入
Source s = 0, k = 64
输出
True
存在一条简单路径0 -> 7 -> 1 -> 2 -> 8 -> 6 -> 5 -> 3 -> 4，总距离为68公里，大于64。
输入
Source s = 0, k = 70
输出
False
在上图中，最长的简单路径距离为69（0 -> 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8），因此对于任何大于69的输入，输出都应为false。
方法
需要注意的是，简单的执行广度优先搜索 (BFS) 或深度优先搜索 (DFS) 并选择每一步的最长边是行不通的。原因是较短的边可以通过连接到它的权重较高的边产生更长的路径。
现在，核心概念是实现回溯算法。在这种情况下，我们从给定的源点开始；遍历当前顶点的所有路径。在这里，我们跟踪当前与源点的距离。如果距离超过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
更新于：2020年7月24日
浏览量：109
广告