原文:
给定一个具有 n-1 边的不同节点 n 的树和一对节点 p 。任务是使用 找到并打印树的两个给定节点之间的路径。
input: n = 10
1
/ \
2 3
/ | \ / | \
4 5 6 7 8 9
pair = {4, 8}
output: 4 -> 2 -> 1 -> 3 -> 8
input: n = 3
1
/ \
2 3
pair = {2, 3}
output: 2 -> 1 -> 3
例如，上图中节点 5 和 3 之间的路径为 5 - > 2 - > 1 - > 3 。 节点 4 和 8 之间的路径为4->2->1->3->8。
进场:
- 其思想是从源节点运行 ，并将遍历的节点推入，直到遍历完目的节点。
- 每当发生时，从堆栈中弹出该节点。
注意:给定的一对节点之间应该有一条路径。
下面是上述方法的实现:
c
// c implementation
#include
using namespace std;
// an utility function to add an edge in an
// undirected graph.
void addedge(vector v[],
int x,
int y)
{
v[x].push_back(y);
v[y].push_back(x);
}
// a function to print the path between
// the given pair of nodes.
void printpath(vector stack)
{
int i;
for (i = 0; i < (int)stack.size() - 1;
i ) {
cout << stack[i] << " -> ";
}
cout << stack[i];
}
// an utility function to do
// dfs of graph recursively
// from a given vertex x.
void dfs(vector v[],
bool vis[],
int x,
int y,
vector stack)
{
stack.push_back(x);
if (x == y) {
// print the path and return on
// reaching the destination node
printpath(stack);
return;
}
vis[x] = true;
// if backtracking is taking place
if (!v[x].empty()) {
for (int j = 0; j < v[x].size(); j ) {
// if the node is not visited
if (vis[v[x][j]] == false)
dfs(v, vis, v[x][j], y, stack);
}
}
stack.pop_back();
}
// a utility function to initialise
// visited for the node and call
// dfs function for a given vertex x.
void dfscall(int x,
int y,
vector v[],
int n,
vector stack)
{
// visited array
bool vis[n 1];
memset(vis, false, sizeof(vis));
// dfs function call
dfs(v, vis, x, y, stack);
}
// driver code
int main()
{
int n = 10;
vector v[n], stack;
// vertex numbers should be from 1 to 9.
addedge(v, 1, 2);
addedge(v, 1, 3);
addedge(v, 2, 4);
addedge(v, 2, 5);
addedge(v, 2, 6);
addedge(v, 3, 7);
addedge(v, 3, 8);
addedge(v, 3, 9);
// function call
dfscall(4, 8, v, n, stack);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation of the above approach
import java.util.*;
class gfg
{
static vector> v = new vector>();
// an utility function to add an edge in an
// undirected graph.
static void addedge(int x, int y){
v.get(x).add(y);
v.get(y).add(x);
}
// a function to print the path between
// the given pair of nodes.
static void printpath(vector stack)
{
for(int i = 0; i < stack.size() - 1; i )
{
system.out.print(stack.get(i) " -> ");
}
system.out.println(stack.get(stack.size() - 1));
}
// an utility function to do
// dfs of graph recursively
// from a given vertex x.
static void dfs(boolean vis[], int x, int y, vector stack)
{
stack.add(x);
if (x == y)
{
// print the path and return on
// reaching the destination node
printpath(stack);
return;
}
vis[x] = true;
// if backtracking is taking place
if (v.get(x).size() > 0)
{
for(int j = 0; j < v.get(x).size(); j )
{
// if the node is not visited
if (vis[v.get(x).get(j)] == false)
{
dfs(vis, v.get(x).get(j), y, stack);
}
}
}
stack.remove(stack.size() - 1);
}
// a utility function to initialise
// visited for the node and call
// dfs function for a given vertex x.
static void dfscall(int x, int y, int n,
vector stack)
{
// visited array
boolean vis[] = new boolean[n 1];
arrays.fill(vis, false);
// memset(vis, false, sizeof(vis))
// dfs function call
dfs(vis, x, y, stack);
}
// driver code
public static void main(string[] args)
{
for(int i = 0; i < 100; i )
{
v.add(new vector());
}
int n = 10;
vector stack = new vector();
// vertex numbers should be from 1 to 9.
addedge(1, 2);
addedge(1, 3);
addedge(2, 4);
addedge(2, 5);
addedge(2, 6);
addedge(3, 7);
addedge(3, 8);
addedge(3, 9);
// function call
dfscall(4, 8, n, stack);
}
}
// this code is contributed by divyeshrabadiya07
python 3
# python3 implementation of the above approach
v = [[] for i in range(100)]
# an utility function to add an edge in an
# undirected graph.
def addedge(x, y):
v[x].append(y)
v[y].append(x)
# a function to print the path between
# the given pair of nodes.
def printpath(stack):
for i in range(len(stack) - 1):
print(stack[i], end = " -> ")
print(stack[-1])
# an utility function to do
# dfs of graph recursively
# from a given vertex x.
def dfs(vis, x, y, stack):
stack.append(x)
if (x == y):
# print the path and return on
# reaching the destination node
printpath(stack)
return
vis[x] = true
# if backtracking is taking place
if (len(v[x]) > 0):
for j in v[x]:
# if the node is not visited
if (vis[j] == false):
dfs(vis, j, y, stack)
del stack[-1]
# a utility function to initialise
# visited for the node and call
# dfs function for a given vertex x.
def dfscall(x, y, n, stack):
# visited array
vis = [0 for i in range(n 1)]
#memset(vis, false, sizeof(vis))
# dfs function call
dfs(vis, x, y, stack)
# driver code
n = 10
stack = []
# vertex numbers should be from 1 to 9.
addedge(1, 2)
addedge(1, 3)
addedge(2, 4)
addedge(2, 5)
addedge(2, 6)
addedge(3, 7)
addedge(3, 8)
addedge(3, 9)
# function call
dfscall(4, 8, n, stack)
# this code is contributed by mohit kumar
c
// c# implementation of the above approach
using system;
using system.collections;
using system.collections.generic;
class gfg
{
static list> v = new list>();
// an utility function to add an edge in an
// undirected graph.
static void addedge(int x, int y)
{
v[x].add(y);
v[y].add(x);
}
// a function to print the path between
// the given pair of nodes.
static void printpath(list stack)
{
for(int i = 0; i < stack.count - 1; i )
{
console.write(stack[i] " -> ");
}
console.writeline(stack[stack.count - 1]);
}
// an utility function to do
// dfs of graph recursively
// from a given vertex x.
static void dfs(bool []vis, int x, int y, list stack)
{
stack.add(x);
if (x == y)
{
// print the path and return on
// reaching the destination node
printpath(stack);
return;
}
vis[x] = true;
// if backtracking is taking place
if (v[x].count > 0)
{
for(int j = 0; j < v[x].count; j )
{
// if the node is not visited
if (vis[v[x][j]] == false)
{
dfs(vis, v[x][j], y, stack);
}
}
}
stack.removeat(stack.count - 1);
}
// a utility function to initialise
// visited for the node and call
// dfs function for a given vertex x.
static void dfscall(int x, int y, int n,
list stack)
{
// visited array
bool []vis = new bool[n 1];
array.fill(vis, false);
// memset(vis, false, sizeof(vis))
// dfs function call
dfs(vis, x, y, stack);
}
// driver code
public static void main(string[] args)
{
for(int i = 0; i < 100; i )
{
v.add(new list());
}
int n = 10;
list stack = new list();
// vertex numbers should be from 1 to 9.
addedge(1, 2);
addedge(1, 3);
addedge(2, 4);
addedge(2, 5);
addedge(2, 6);
addedge(3, 7);
addedge(3, 8);
addedge(3, 9);
// function call
dfscall(4, 8, n, stack);
}
}
// this code is contributed by rutvik_56
java 描述语言
output:
4 -> 2 -> 1 -> 3 -> 8
有效方法:
在这种方法中，我们将利用 (lca)的概念。
1.我们将使用 dfs 找到每个节点的级别和父节点。
2.我们将找到两个给定节点的最低共同祖先。
3.从第一个节点开始，我们将前往生命周期评价，并继续推进
路径向量中的中间节点。
4.然后，从第二个节点，我们将再次前往 lca，但这一次
我们将反转遇到的中间节点，然后将它们推入
我们的路径向量。
5.最后，打印路径向量以获得两个节点之间的路径。
c
// c implementation for the above approach
#include
using namespace std;
// an utility function to add an edge in the tree
void addedge(vector adj[], int x,
int y)
{
adj[x].push_back(y);
adj[y].push_back(x);
}
// running dfs to find level and parent of every node
void dfs(vector adj[], int node, int l,
int p, int lvl[], int par[])
{
lvl[node] = l;
par[node] = p;
for(int child : adj[node])
{
if(child != p)
dfs(adj, child, l 1, node, lvl, par);
}
}
int lca(int a, int b, int par[], int lvl[])
{
// if node a is at deeper level than
// node b
if(lvl[a] > lvl[b])
swap(a, b);
// finding the difference in levels
// of node a and b
int diff = lvl[b] - lvl[a];
// moving b to the level of a
while(diff != 0)
{
b = par[b];
diff--;
}
// means we have found the lca
if(a == b)
return a;
// finding the lca
while(a != b)
a=par[a], b=par[b];
return a;
}
void printpath(vector adj[], int a, int b, int n)
{
// stores level of every node
int lvl[n 1];
// stores parent of every node
int par[n 1];
// running dfs to find parent and level
// of every node in the tree
dfs(adj, 1, 0, -1, lvl, par);
// finding the lowest common ancestor
// of the nodes a and b
int lca = lca(a, b, par, lvl);
// stores path between nodes a and b
vector path;
// traversing the path from a to lca
while(a != lca)
path.push_back(a), a = par[a];
path.push_back(a);
vector temp;
// traversing the path from b to lca
while(b != lca)
temp.push_back(b), b=par[b];
// reversing the path to get actual path
reverse(temp.begin(), temp.end());
for(int x : temp)
path.push_back(x);
// printing the path
for(int i = 0; i < path.size() - 1; i )
cout << path[i] << " -> ";
cout << path[path.size() - 1] << endl;
}
// driver code
int main()
{
/* 1
/ \
2 7
/ \
3 6
/ | \
4 8 5
*/
// number of nodes in the tree
int n = 8;
// adjacency list representation of the tree
vector adj[n 1];
addedge(adj, 1, 2);
addedge(adj, 1, 7);
addedge(adj, 2, 3);
addedge(adj, 2, 6);
addedge(adj, 3, 4);
addedge(adj, 3, 8);
addedge(adj, 3, 5);
// taking two input nodes
// between which path is
// to be printed
int a = 4, b = 7;
printpath(adj, a, b, n);
return 0;
}
output
4 -> 3 -> 2 -> 1 -> 7
时间复杂度: o(n)
空间复杂度: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
