检查两个节点是否在树中的同一路径上  


难度级别 中等
经常问 亚马逊 事实集 风筝 Samsung
深度优先搜索 图表 图遍历

问题陈述  

问题“检查两个节点是否在树中的同一路径上”指出给您一个 一元树 (有向无环图)植根于 与节点 单向 顶点之间的边缘。 您还会得到一个查询列表q。

  1. 列表q中的每个查询都包含两个顶点u和v。
  2. 您必须打印“可以”,如果节点 u&v位于同一条道路上 起源于 顶点。
  3. 其他印刷品“没有”,如果节点 u&v位于不同的路径 起源于 顶点。

使用案列  

 

检查两个节点是否在树中的同一路径上

检查两个节点是否在树中的同一路径上的方法  

这个想法是执行 DFS 低至 节点。 这种DFS遍历首先访问根的每个子树,直到最后一个深度,这意味着它访问每个唯一的线性路径,直到最后一个叶顶点,然后继续到下一个线性路径。

考虑,

–节点的intime是从根节点开始执行DFS遍历时首先访问该节点的时间, 进入时间 DFS遍历期间节点的状态。

时差 –节点的超时是指在访问完所有子节点之后访问该节点的时间,这种情况发生在沿着根节点的路径返回时,它是 退出时间 DFS遍历期间节点的状态。

参见
克鲁斯卡尔算法

如果节点u和v沿着相同的路径:

  1. 假设u是v的父代, u的时间<v的时间 &u的超时时间> v的超时时间.
  2. 或假设v是u的父代, v的时间<u的时间&v的时间> u的时间.
  3. 通常, 当两个节点位于同一条路径上时, 一个是父母,另一个是孩子。 在这种情况下,DFS遍历之后:
    • 父母的时间<子女的时间
    • 父母的超时>儿童的超时
1. Perform DFS traversal from the given root node and for each node calculate entry time and exit time using intime[ ] and outtime[ ] arrays.
2. So after the DFS traversal is complete. Process the query list q. Each query in q consists of two values u and v.
3. If intime[u] < intime[v] and also outtime[u] > outtime[v], print "YES".
4. Or if intime[v] < intime[u] and also outtume[v] > outtime[u], print "YES".
5. If conditions 3 and 4 are false, then print "NO".
6. If conditions 3 and 4 are true, this signifies that u & v lie along the same path originating from the root.
7. If condition 5 is true, then it signifies that u & v do not lie along the same path originating from the root.

该算法如下所示:

检查两个节点是否在树中的同一路径上

检查两个节点是否在树中的同一路径上

代码  

用于检查两个节点是否在树中的同一路径上的C ++程序

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

/* variable to keep track of intime 
and outtime values for each vertex */
int times = 0;

/* function to perform DFS from root nodes to all the leaves 
& calculate entry time (intime) 
& exit time (outtime) 
for each vertex */
void DFS(int root,vector <int> graph[],vector <int> &intime,vector<int> &outtime)
{
    intime[root] = ++times;
    
    for(auto i : graph[root])
        DFS(i,graph,intime,outtime);
    
    outtime[root] = ++times;
    return;
}

/* function that returns true if nodes u and v 
lie along the same path else return false */
bool query(int u,int v,vector <int> intime,vector <int> outtime)
{
    return ((intime[u] < intime[v] && outtime[u] > outtime[v]) || 
             (intime[v] < intime[u] && outtime[v] > outtime[u])); 
}

int main()
{
    /* Define
    1.number of vertices
    2.root vertex
    3.edges
    */
    int V = 9;
    int root = 0;
    vector<vector<int>> Edges = {{0,1},{1,4},{1,5},{0,2},{2,6},{6,7},{0,3},{3,8}};
    
    /* construct the graph */
    vector <int> graph[V];
    for(auto edge : Edges)
    graph[edge[0]].push_back(edge[1]);
    
    /* Define vectors that store entry time(intime) & 
    exit time(outtime) for each vertex of the tree */
    vector <int> intime(V,0);
    vector <int> outtime(V,0);
    
    /* perform DFS traversal to fill intime & outtime vectors */
    DFS(root,graph,intime,outtime);
    
    /* Define query vertices */
    vector<vector<int>> q = {{0,5},{2,7},{1,8}};
    
    for(auto i : q)
    {
        if(query(i[0],i[1],intime,outtime))
        cout<<"YES";
        else
        cout<<"NO";
        
        cout<<endl;
    }
    
    return 0;
}
YES 
YES 
NO

Java代码以查找检查两个节点是否在树中的同一路径上

import java.io.*;
import java.util.*;

class TutorialCup 
{
    /* variable to keep track of intime 
    and outtime values for each vertex */
    static int times = 0;
    
    /* function to perform DFS from root nodes to all the leaves 
    & calculate entry time (intime) 
    & exit time (outtime) 
    for each vertex */
    static void DFS(int root,ArrayList<ArrayList<Integer>> graph,int [] intime,int [] outtime)
    {
        intime[root] = ++times;
        
        Iterator itr = graph.get(root).iterator();
        
        while(itr.hasNext())
        {
            int i = (Integer)itr.next();
            DFS(i,graph,intime,outtime);
        }
        
        outtime[root] = ++times;

        return;
    }
    
    /* function that returns true if nodes u and v 
    lie along the same path else return false */
    static boolean query(int u,int v,int [] intime,int [] outtime)
    {
        return ((intime[u] < intime[v] && outtime[u] > outtime[v]) || 
                 (intime[v] < intime[u] && outtime[v] > outtime[u])); 
    }
    
    public static void main (String[] args)
    {
        /* Define
        1.number of vertices
        2.root vertex
        3.edges
        */
        int V = 9;
        int root = 0;
        int [][] Edges = {{0,1},{1,4},{1,5},{0,2},{2,6},{6,7},{0,3},{3,8}};
        
        /* construct the graph */
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0;i<V;i++)
        graph.add(new ArrayList<Integer>());
        
        for(int i=0; i<Edges.length; i++)
        graph.get(Edges[i][0]).add(Edges[i][1]);
        
        /* Define vectors that store entry time(intime) & 
        exit time(outtime) for each vertex of the tree */
        int [] intime = new int[V];
        int [] outtime = new int[V];
        
        /* perform DFS traversal to fill intime & outtime vectors */
        DFS(root,graph,intime,outtime);
        
        /* Define query vertices */
        int [][] q = {{0,5},{2,7},{1,8}};
        
        for(int i=0; i<q.length; i++)
        {
            if(query(q[i][0],q[i][1],intime,outtime))
            System.out.println("YES");
            else
            System.out.println("NO");
        }
    }
}
YES
YES
NO

复杂度分析  

时间复杂度

T(n)= O(n),n =节点数。 因为我们使用了遍历树中节点的DFS。 因此,时间复杂度是线性的。

参见
断开图的BFS

空间复杂度

A(n)= O(n),用于使用intime []和outtime []数组。 这两个数组的大小均取决于节点数。 因此,空间复杂度也是线性的。