최대 노드 수를 포함하는 유향 그래프에서 시작 노드 찾기
13052 단어 datastructuregraphtutorialbeginners
NOTE: A node can have multiple edges which are pointing towards him, but only one outgoing edge
Input: N = 5
1->2, 2->1, 3->1, 4->2, 5->3
그래프 구조:
Output: 5
Explanation:
If we start from node 1 as beginning then the path is: 1 -> 2
If we start from node 2 as beginning then the path is: 2 -> 1
If we start from node 3 as beginning then the path is: 3 -> 1 -> 2
If we start from node 4 as beginning then the path is: 4 -> 2 -> 1
If we start from node 5 as beginning then path is: 5 -> 3 -> 1 -> 2
Hence, we can clearly see that if we start for 5, we cover the
maximum number of nodes in the
graph i.e. 4.
접근하다:
특정 노드에서 도달할 수 있는 노드 수를 찾기 위해 한 가지 관찰해야 할 사항은 동일한 연결 구성 요소에 있을 때만 노드 X에서 노드 Y로 도달할 수 있다는 것입니다.
그래프는 방향성이므로 연결된 구성 요소의 모든 노드는 동일한 연결된 구성 요소의 다른 노드에 연결됩니다. 따라서 특정 노드에 대해 도달할 수 있는 X 노드 수는 해당 특정 구성 요소의 노드 수입니다. 답을 찾으려면 깊이 우선 검색을 사용하십시오.
암호
다음은 코드의 구현
Java
입니다.import java.util.HashSet;
import java.util.Set;
public class Main{
static int[] graph;
// Driver Function
public static void main(String[] args) {
// Taking the number of nodes from the user
int n = 5;
// Array to store the nodes direction
graph = new int[n];
// Initializing graph
// 1->2, 2->1, 3->1, 4->2, 5->3
graph[0] = 1;
graph[1] = 0;
graph[2] = 0;
graph[3] = 1;
graph[4] = 2;
System.out.println(find(n));
}
static int find(int n) {
int max = 0; // Holds the maximum count of nodes visited
int node = 0; // Starting index of the node with maximum max count
// Considering each node one-by-one as beginning node
// Using DFS to fully explore that node
for (int i = 0; i < n; i++) {
// Finding the total number of node that can be covered by
// considering the ith node as beginning
int visits = canVisit(i);
if (visits > max) { // If ith node covers more node then
max = visits; // Store the number of nodes covered
node = i; // Store the node index
}
}
// As we are considering the indices from 0 just add 1 into the index
return node + 1; // and return it
}
// Function to perform the DFS calculating the
// count of the elements in a connected component
static int canVisit(int n) {
// This set contains the indices of the visited elements
// This will help use to make sure that we are not running
// inside a cycle in the graph
Set<Integer> set = new HashSet<>();
set.add(n); // Add the current node into the graph as it is visited
// Go to the next node in the graph towards with the current directs
int visit = graph[n];
// Hold the total number of nodes visited
// Since we at least visit the beginning node hence assign count to 1
int count = 1;
// Explore until the node repeats or we reach at the dead-end
while (!set.contains(visit)) {
set.add(visit); // Add the next visit into the set
visit = graph[visit]; // Jump to next directed node
count++; // Increment the count as one more has been explored
}
return count; // Return the total number of nodes visited
}
}
복잡성:
그래프가 내부 주기 없이 선형으로 연결된 경우 최악의 경우가 발생하여
O(N²)
가 됩니다. O(N)
의 보조 공간이 있습니다.
Reference
이 문제에 관하여(최대 노드 수를 포함하는 유향 그래프에서 시작 노드 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/sumit/find-the-starting-node-in-a-directed-graph-which-covers-the-maximum-number-of-nodes-dcg텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)