Остовное дерево с максимальной степенью (с использованием алгоритма Крускала)
Опубликовано: 7 Января, 2022
Дан неориентированный невзвешенный связный граф, состоящий из n вершин и m ребер. Задача состоит в том, чтобы найти такое остовное дерево этого графа, чтобы максимальная степень по всем вершинам была максимально возможной. Порядок, в котором вы печатаете выходные края, не имеет значения, и край может быть напечатан в обратном порядке, то есть (u, v) также может быть напечатан как (v, u).
Примеры:
Вход:
1
/
2 5
/
3
|
4
Выход:
3 2
3 5
3 4
1 2
Максимальная степень по всем вершинам
имеет вершину 3, которая равна 3, и является
максимально возможное.
Вход:
1
/
2
/
5 3
|
4
Выход:
2 1
2 5
2 3
3 4 Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Предпосылка: алгоритм Краскала для поиска минимального связующего дерева
Approach: The given problem can be solved using Kruskal’s algorithm to find the Minimum Spanning tree.
We find the vertex which has maximum degree in the graph. At first we will perform the union of all the edges which are incident to this vertex and than carry out normal Kruskal’s algorithm. This gives us optimal spanning tree.
Java
// Java implementation of the approachimport java.util.*;public class GFG { // par and rank will store the parent // and rank of particular node // in the Union Find Algorithm static int par[], rank[]; // Find function of Union Find Algorithm static int find(int x) { if (par[x] != x) par[x] = find(par[x]); return par[x]; } // Union function of Union Find Algorithm static void union(int u, int v) { int x = find(u); int y = find(v); if (x == y) return; if (rank[x] > rank[y]) par[y] = x; else if (rank[x] < rank[y]) par[x] = y; else { par[x] = y; rank[y]++; } } // Function to find the required spanning tree static void findSpanningTree(int deg[], int n, int m, ArrayList<Integer> g[]) { par = new int[n + 1]; rank = new int[n + 1]; // Initialising parent of a node // by itself for (int i = 1; i <= n; i++) par[i] = i; // Variable to store the node // with maximum degree int max = 1; // Finding the node with maximum degree for (int i = 2; i <= n; i++) if (deg[i] > deg[max]) max = i; // Union of all edges incident // on vertex with maximum degree for (int v : g[max]) { System.out.println(max + " " + v); union(max, v); } // Carrying out normal Kruskal Algorithm for (int u = 1; u <= n; u++) { for (int v : g[u]) { int x = find(u); int y = find(v); if (x == y) continue; union(x, y); System.out.println(u + " " + v); } } } // Driver code public static void main(String args[]) { // Number of nodes int n = 5; // Number of edges int m = 5; // ArrayList to store the graph ArrayList<Integer> g[] = new ArrayList[n + 1]; for (int i = 1; i <= n; i++) g[i] = new ArrayList<>(); // Array to store the degree // of each node in the graph int deg[] = new int[n + 1]; // Add edges and update degrees g[1].add(2); g[2].add(1); deg[1]++; deg[2]++; g[1].add(5); g[5].add(1); deg[1]++; deg[5]++; g[2].add(3); g[3].add(2); deg[2]++; deg[3]++; g[5].add(3); g[3].add(5); deg[3]++; deg[5]++; g[3].add(4); g[4].add(3); deg[3]++; deg[4]++; findSpanningTree(deg, n, m, g); }} |
Python3
# Python3 implementation of the approachfrom typing import List# par and rank will store the parent# and rank of particular node# in the Union Find Algorithmpar = []rnk = []# Find function of Union Find Algorithmdef find(x: int) -> int: global par if (par[x] != x): par[x] = find(par[x]) return par[x]# Union function of Union Find Algorithmdef Union(u: int, v: int) -> None: global par, rnk x = find(u) y = find(v) if (x == y): return if (rnk[x] > rnk[y]): par[y] = x elif (rnk[x] < rnk[y]): par[x] = y else: par[x] = y rnk[y] += 1# Function to find the required spanning treedef findSpanningTree(deg: List[int], n: int, m: int, g: List[List[int]]) -> None: global rnk, par # Initialising parent of a node # by itself par = [i for i in range(n + 1)] rnk = [0] * (n + 1) # Variable to store the node # with maximum degree max = 1 # Finding the node with maximum degree for i in range(2, n + 1): if (deg[i] > deg[max]): max = i # Union of all edges incident # on vertex with maximum degree for v in g[max]: print("{} {}".format(max, v)) Union(max, v) # Carrying out normal Kruskal Algorithm for u in range(1, n + 1): for v in g[u]: x = find(u) y = find(v) if (x == y): continue Union(x, y) print("{} {}".format(u, v))# Driver codeif __name__ == "__main__": # Number of nodes n = 5 # Number of edges m = 5 # ArrayList to store the graph g = [[] for _ in range(n + 1)] # Array to store the degree # of each node in the graph deg = [0] * (n + 1) # Add edges and update degrees g[1].append(2) g[2].append(1) deg[1] += 1 deg[2] += 1 g[1].append(5) g[5].append(1) deg[1] += 1 deg[5] += 1 g[2].append(3) g[3].append(2) deg[2] += 1 deg[3] += 1 g[5].append(3) g[3].append(5) deg[3] += 1 deg[5] += 1 g[3].append(4) g[4].append(3) deg[3] += 1 deg[4] += 1 findSpanningTree(deg, n, m, g)# This code is contributed by sanjeev2552 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{ // par and rank will store the parent // and rank of particular node // in the Union Find Algorithm static int []par; static int []rank; // Find function of Union Find Algorithm static int find(int x) { if (par[x] != x) par[x] = find(par[x]); return par[x]; } // Union function of Union Find Algorithm static void union(int u, int v) { int x = find(u); int y = find(v); if (x == y) return; if (rank[x] > rank[y]) par[y] = x; else if (rank[x] < rank[y]) par[x] = y; else { par[x] = y; rank[y]++; } } // Function to find the required spanning tree static void findSpanningTree(int []deg, int n, int m, List<int> []g) { par = new int[n + 1]; rank = new int[n + 1]; // Initialising parent of a node // by itself for (int i = 1; i <= n; i++) par[i] = i; // Variable to store the node // with maximum degree int max = 1; // Finding the node with maximum degree for (int i = 2; i <= n; i++) if (deg[i] > deg[max]) max = i; // Union of all edges incident // on vertex with maximum degree foreach (int v in g[max]) { Console.WriteLine(max + " " + v); union(max, v); } // Carrying out normal Kruskal Algorithm for (int u = 1; u <= n; u++) { foreach (int v in g[u]) { int x = find(u); int y = find(v); if (x == y) continue; union(x, y); Console.WriteLine(u + " " + v); } } } // Driver code public static void Main(String []args) { // Number of nodes int n = 5; // Number of edges int m = 5; // ArrayList to store the graph List<int> []g = new List<int>[n + 1]; for (int
|