소스 노드의 트리에있는 각 노드의 레벨  


난이도 중급
자주 묻는 질문 아마존 Microsoft
폭 우선 검색 깊이 우선 검색 나무

트리 (구성 노드가 양방향 간선으로 연결된 비순환 완전 연결 그래프) 및 마디. 각 노드의 레벨을 찾으십시오. 나무 양식 소스 노드. 해당 수준의 노드가 제공됩니다. v 에 관하여 사이의 거리입니다 v.

  

소스 노드로 0을 사용하여 아래에 주어진 그래프를 고려하십시오.

소스 노드의 트리에있는 각 노드의 레벨

솔루션 유형  

  1. 깊이 우선 검색
  2. 폭 우선 검색

깊이 우선 검색  

소스 노드에서 트리의 각 노드 수준에 대한 접근 방식

소스 노드에서 그래프의 다른 모든 노드로 깊이 우선 검색 (DFS)을 수행합니다. level [] 배열은 소스 노드에 대한 그래프의 각 노드 레벨을 저장합니다. 자신에 대한 소스 노드의 레벨은 0입니다 (자체로부터 노드의 거리는 0). 현재 동안 노드 DFS 순회 고려 상단 현재의 방문하지 않은 이웃입니다. 상단 , 우리는 단순히 방문한 것으로 표시하고 다음 할당을 만듭니다. 레벨 [상단] = 레벨 [현재] + 1 . 그 후, 우리는 단순히 DFS 순회를 (재귀 적으로) 상단 소스 노드로.

참조
주어진 연결 목록의 끝에서 N 번째 노드 삭제

암호알고리즘

  1. 정점 수를 정의하고 소스 노드를 결정합니다.
  2. 주어진 그래프를 구성하십시오.
  3. create level [] 및 vis [] arrays.level []은 각 노드 wrt 소스 노드의 레벨을 저장하고 vis []는 특정 정점이 이전에 방문했는지 여부를 저장합니다.
  4. 소스 노드에서 DFS 순회를 수행합니다.
  5. 주어진 현재 DFS 순회 고려 중 노드 상단 방문하지 않은 이웃입니다 흐름. 방문시 상단 , 우리는 단순히 방문한 것으로 표시하고 다음 할당을 만듭니다. 레벨 [상단] = 레벨 [현재] + 1.
  6. 이제 다음에서 DFS 순회를 재귀 적으로 수행합니다. 상단 이웃에 대한 정점.
  7. DFS 순회는 모든 정점이 한 번 방문 될 때까지 수행됩니다. 그래프에서 노드를 방문 / 처리하면 방문한 것으로 표시합니다.
  8. 순회가 끝나면 간단히 각 노드에 저장된 레벨을 인쇄하십시오. 레벨 [] 정렬.

소스 노드의 트리에있는 각 노드의 레벨

소스 노드의 트리에있는 각 노드의 레벨

실시

C ++ 프로그램

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

/* function to link nodes u and v */
void addEdge(vector <int> graph[],int u,int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}

/* function to perform depth first search and 
evaluate level of each node w.r.t. to source node */
void DFS(int source,vector <int> graph[],vector <int> &level,vector <bool> &vis)
{
    vis[source] = true;
    for(auto i:graph[source])
    {
        if(!vis[i])
        {
            vis[i] = true;
            level[i] = level[source]+1;
            DFS(i,graph,level,vis);
        }
    }
}

int main()
{
    /* define number of vertices and 
    source vertex in the graph */
    int vertex = 7;
    int source = 0;
    
    /* construct the graph and link the nodes through edges */
    vector <int> graph[vertex];
    addEdge(graph,0,1);
    addEdge(graph,0,2);
    addEdge(graph,0,3);
    addEdge(graph,1,4);
    addEdge(graph,1,5);
    addEdge(graph,5,6);
    
    /* level[i] stores level of i-th node with respect to source node
    level of a node is distance of that node from the source node */
    vector <int> level(vertex,0);
    /* vis[] is used to check whether a node has been visited during DFS */
    vector <bool> vis(vertex,0);
    /* perform DFS of given graph from source node */ 
    DFS(source,graph,level,vis);
    
    /* output level of each node in the graph */
    cout<<"The levels of each node with respect to "<<source<<"-node is given below:"<<endl;
    cout<<"Node"<<" "<<"Level"<<endl;
    for(int i=0;i<vertex;i++)
        cout<<i<<"\t"<<level[i]<<endl;
    
    
    return 0;
}
The levels of each node with respect to 0-node is given below:
Node Level
0	0
1	1
2	1
3	1
4	2
5	2
6	3

자바 프로그램

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

class TutorialCup
{
    /* function to link nodes u and v */
    static void addEdge(ArrayList<ArrayList<Integer>> graph,int u,int v)
    {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    
    /* function to perform depth first search and 
    evaluate level of each node w.r.t. to source node */
    static void DFS(int source,ArrayList<ArrayList<Integer>> graph,int [] level,boolean [] vis)
    {
        vis[source] = true;
        
        Iterator it = graph.get(source).iterator();
        while(it.hasNext())
        {
            int i = (Integer)it.next();
            if(!vis[i])
            {
                vis[i] = true;
                level[i] = level[source] + 1;
                DFS(i,graph,level,vis);
            }
        }
    }
    
    public static void main (String[] args) 
    {
        /* define number of vertices and 
        source vertex in the graph */
        int vertex = 7;
        int source = 0;
        
        /* construct the graph and link the nodes through edges */
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<vertex;i++)
        graph.add(new ArrayList<Integer>());
        
        addEdge(graph,0,1);
        addEdge(graph,0,2);
        addEdge(graph,0,3);
        addEdge(graph,1,4);
        addEdge(graph,1,5);
        addEdge(graph,5,6);
        
        /* level[i] stores level of i-th node with respect to source node
        level of a node is distance of that node from the source node */
        int [] level = new int[vertex];
        /* vis[] is used to check whether a node has been visited during DFS */
        boolean [] vis = new boolean[vertex];
        /* perform DFS of given graph from source node */ 
        DFS(source,graph,level,vis);
        
        /* output level of each node in the graph */
        System.out.println("The levels of each node with respect to "+source+"-node is given below:");
        System.out.println("Node"+" "+"Level");
        for(int i=0;i<vertex;i++)
            System.out.println(i+"\t"+level[i]);
        
    }
}
The levels of each node with respect to 0-node is given below:
Node Level
0	0
1	1
2	1
3	1
4	2
5	2
6	3

소스 노드에서 트리의 각 노드 수준에 대한 복잡성 분석

  1. 시간 복잡도 : T (n) = O (V + E).
  2. 공간 복잡성 : A (n) = O (1), 재귀 적 접근.
참조
주어진 부분 배열에서 주어진 수보다 작거나 같은 요소의 수

V = 꼭지점 수.

E = 모서리 수.

폭 우선 검색  

소스 노드에서 트리의 각 노드 수준에 대한 접근 방식

소스 노드에서 그래프의 다른 모든 노드로 폭 우선 검색 (BFS)을 수행합니다. 큐 데이터 구조는 다음을 수행하는 데 사용됩니다. BFS 순회. 레벨 [] 배열은 각 노드의 레벨을 그래프 소스 노드와 관련하여. 자신에 대한 소스 노드의 레벨은 0입니다 (자체로부터 노드의 거리는 0입니다). 현재 BFS 순회 고려 중 노드 상단 현재 방문하지 않은 이웃이며 대기열 앞에 있습니다. 방문시 상단 (팝핑 후 상단 대기열에서), 방문한 것으로 표시하고 다음 할당을 수행합니다. 레벨 [상단] = 레벨 [현재] + 1. 그런 다음 방문하지 않은 모든 이웃을 추가합니다. 상단 대기열에.

큐 데이터 구조의 목적은 현재 요소의 방문하지 않은 모든 인접 정점을 저장하여 나중에 반복적으로 방문 할 수 있도록하는 것입니다.

암호알고리즘

  1. 정점 수를 정의하고 소스 노드를 결정합니다.
  2. 주어진 그래프를 구성하십시오.
  3. Create level [] 및 vis [] arrays.level []은 각 노드 wrt 소스 노드의 레벨을 저장하고 vis []는 특정 정점이 이전에 방문했는지 여부를 저장합니다.
  4. 소스 노드에서 BFS 반복 순회를 수행합니다.
  5. 순회 시작 및 노드 팝 상단 대기열에서.
  6. 방문하지 않은 이웃 n1, n2를 모두 방문하십시오…. 방문한 것으로 표시합니다.
  7. 방문하지 않은 각 이웃에 대해 다음 할당을 수행하십시오. level [n1] = 수평[상단] + 1을 입력하고 큐에 삽입합니다.
  8. 대기열에있는 각 노드에서 하나씩 BFS를 반복적으로 수행합니다.
  9. BFS 순회는 모든 정점이 한 번 방문 될 때까지 수행됩니다. 그래프에서 노드를 방문 / 처리하면 방문한 것으로 표시합니다.
  10. 순회가 끝나면 간단히 각 노드의 레벨을 인쇄하십시오. 레벨 [] 정렬.
참조
해시 테이블에 비해 BST의 장점

실시

C ++ 프로그램

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

/* function to link nodes u and v */
void addEdge(vector <int> graph[],int u,int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}

/* function to perform breadth first search and 
evaluate level of each node w.r.t. to source node */
void BFS(int source,vector <int> graph[],vector <int> &level,vector <bool> &vis)
{
    queue <int> q;
    q.push(source);
    
    while(!q.empty())
    {
        int top = q.front();
        vis[top] = true;
        q.pop();
        
        for(auto i : graph[top])
        {
            if(!vis[i])
            {
                level[i] = level[top] + 1;
                q.push(i);
            }
        }
    }
}

int main()
{
    /* define number of vertices and 
    source vertex in the graph */
    int vertex = 7;
    int source = 0;
    
    /* construct the graph and link the nodes through edges */
    vector <int> graph[vertex];
    addEdge(graph,0,1);
    addEdge(graph,0,2);
    addEdge(graph,0,3);
    addEdge(graph,1,4);
    addEdge(graph,1,5);
    addEdge(graph,5,6);
    
    /* level[i] stores level of i-th node with respect to source node
    level of a node is distance of that node from the source node */
    vector <int> level(vertex,0);
    /* vis[] is used to check whether a node has been visited during DFS */
    vector <bool> vis(vertex,0);
    /* perform DFS of given graph from source node */ 
    BFS(source,graph,level,vis);
    
    /* output level of each node in the graph */
    cout<<"The levels of each node with respect to "<<source<<"-node is given below:"<<endl;
    cout<<"Node"<<" "<<"Level"<<endl;
    for(int i=0;i<vertex;i++)
        cout<<i<<"\t"<<level[i]<<endl;
    
    
    return 0;
}
The levels of each node with respect to 0-node is given below:
Node Level
0	0
1	1
2	1
3	1
4	2
5	2
6	3

자바 프로그램

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

class TutorialCup
{
    /* function to link nodes u and v */
    static void addEdge(ArrayList<ArrayList<Integer>> graph,int u,int v)
    {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    
    /* function to perform breadth first search and 
    evaluate level of each node w.r.t. to source node */
    static void BFS(int source,ArrayList<ArrayList<Integer>> graph,int [] level,boolean [] vis)
    {
        Queue <Integer> q = new LinkedList<>();
        q.add(source);
        
        while(!q.isEmpty())
        {
            int top = q.poll();
            vis[top] = true;
            
            Iterator it = graph.get(top).iterator();
            while(it.hasNext())
            {
                int i = (Integer)it.next();
                if(!vis[i])
                {
                    level[i] = level[top] + 1;
                    q.add(i);
                }
            }
        }
    }
    
    public static void main (String[] args) 
    {
        /* define number of vertices and 
        source vertex in the graph */
        int vertex = 7;
        int source = 0;
        
        /* construct the graph and link the nodes through edges */
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        for(int i=0;i<vertex;i++)
        graph.add(new ArrayList<Integer>());
        
        addEdge(graph,0,1);
        addEdge(graph,0,2);
        addEdge(graph,0,3);
        addEdge(graph,1,4);
        addEdge(graph,1,5);
        addEdge(graph,5,6);
        
        /* level[i] stores level of i-th node with respect to source node
        level of a node is distance of that node from the source node */
        int [] level = new int[vertex];
        /* vis[] is used to check whether a node has been visited during DFS */
        boolean [] vis = new boolean[vertex];
        /* perform DFS of given graph from source node */ 
        BFS(source,graph,level,vis);
        
        /* output level of each node in the graph */
        System.out.println("The levels of each node with respect to "+source+"-node is given below:");
        System.out.println("Node"+" "+"Level");
        for(int i=0;i<vertex;i++)
            System.out.println(i+"\t"+level[i]);
        
    }
}
The levels of each node with respect to 0-node is given below:
Node Level
0	0
1	1
2	1
3	1
4	2
5	2
6	3

소스 노드에서 트리의 각 노드 수준에 대한 복잡성 분석

  1. 시간 복잡도 : T (n) = O (V + E).
  2. 공간 복잡성 : A (n) = O (V), 사용 된 큐 데이터 구조.
참조
BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인

V = 꼭지점 수.

E = 모서리 수.

참조