¿Qué es el Código Prufer?
Dado un árbol (representado como un gráfico, no como un árbol con raíz) con n Nodes etiquetados con etiquetas del 1 al n, un código Prufer identifica el árbol de manera única. La secuencia tiene n-2 valores.
¿Cómo obtener el Código Prufer de un árbol?
- Inicialice el código Prufer como vacío.
- Comience con una hoja de la etiqueta más baja, digamos x. Encuentre el vértice que lo conecta con el resto del árbol, digamos y. Eliminar x del árbol y agregar y al Código Prufer
- Repita el paso 2 anterior hasta que nos queden dos Nodes.
A tree with labels from 1 to n.
5
/ \
1 4
/ \
2 3
PruferCode = {}
The lowest label leaf is 2, we remove it from tree
and add the other vertex (connecting it to the tree)
to Prufer code
Tree now becomes
5
/ \
1 4
\
3
Prufer Code becomes = {1}
The lowest label leaf is 3, we remove it from tree
and add the other vertex (connecting it to the tree)
to Prufer code
Tree now becomes
5
/ \
1 4
Prufer Code becomes = {1, 1}
The lowest label leaf is 1, we remove it from tree
and add the other vertex (connecting it to the tree)
to Prufer code
Tree now becomes
5
\
4
Prufer Code becomes = {1, 1, 5}
We have only two nodes left now, so we stop.
¿Cómo construir un árbol a partir del Código Prufer dado?
Input : (4, 1, 3, 4)
Output : Edges of following tree
2----4----3----1----5
|
6
Input : (1, 3, 5)
Output : Edges of following tree
2----1----3----5----4
Sea m la longitud del código de Prufer dado. La idea es crear un gráfico vacío de m+2 vértices. Eliminamos el primer elemento de la secuencia. Sea x el primer elemento de la secuencia actual. Luego encontramos el valor mínimo que no está presente en la secuencia dada y aún no se ha agregado al árbol. Sea este valor y. Agregamos un borde de x a y y repetimos este paso.
Entendamos el algoritmo para construir el árbol con el primer ejemplo anterior:
Input : (4, 1, 3, 4)
Step 1: First we create an empty graph of 6 vertices
and get 4 from the sequence.
Step 2: Out of 1 to 6, the least vertex not in
Prufer sequence is 2.
Step 3: We form an edge between 2 and 4.
2----4 1 3 5 6
Step 4: Next in the sequence is 1 and corresponding
vertex with least degree is 5 (as 2 has been
considered).
2----4 1----5 3 6
Step 5: Next in the sequence is 3 and corresponding
vertex with least degree is 1
(as 1 is now not part of remaining Prufer sequence)
2----4 3----1----5 6
Step 6: Next in the sequence is 4 and corresponding vertex
with least degree is 3 (as 3 has not been considered
as is not present further in sequence)
2----4----3----1----5 6
Step 7: Finally two vertices are left out from 1 to 6 (4
and 6) so we join them.
2----4----3----1----5
|
6
This is the required tree on 6 vertices.
A continuación se muestra la implementación.
C++
// C++ program to construct tree from given Prufer Code
#include <bits/stdc++.h>
using namespace std;
// Prints edges of tree represented by given Prufer code
void printTreeEdges(int prufer[], int m)
{
int vertices = m + 2;
int vertex_set[vertices];
// Initialize the array of vertices
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
cout << "\nThe edge set E(G) is :\n";
// Find the smallest label not present in
// prufer[].
int j = 0;
for (int i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
// If j+1 is not present in prufer set
if (vertex_set[j] == 0) {
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
cout << "(" << (j + 1) << ", "
<< prufer[i] << ") ";
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (int i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
cout << "(" << (i + 1) << ", ";
j++;
}
else if (vertex_set[i] == 0 && j == 1)
cout << (i + 1) << ")\n";
}
}
// Driver code
int main()
{
int prufer[] = { 4, 1, 3, 4 };
int n = sizeof(prufer) / sizeof(prufer[0]);
printTreeEdges(prufer, n);
return 0;
}
Java
// Java program to construct tree from given Prufer Code
class GFG {
// Prints edges of tree represented by given Prufer code
static void printTreeEdges(int prufer[], int m)
{
int vertices = m + 2;
int vertex_set[] = new int[vertices];
// Initialize the array of vertices
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
System.out.print("\nThe edge set E(G) is :\n");
// Find the smallest label not present in
// prufer[].
int j = 0;
for (int i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
// If j+1 is not present in prufer set
if (vertex_set[j] == 0) {
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
System.out.print("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (int i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
System.out.print("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
System.out.print((i + 1) + ")\n");
}
}
// Driver code
public static void main(String args[])
{
int prufer[] = { 4, 1, 3, 4 };
int n = prufer.length;
printTreeEdges(prufer, n);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to construct
# tree from given Prufer Code
# Prints edges of tree represented
# by given Prufer code
def printTreeEdges(prufer, m):
vertices = m + 2
# Initialize the array of vertices
vertex_set = [0] * vertices
# Number of occurrences of vertex in code
for i in range(vertices - 2):
vertex_set[prufer[i] - 1] += 1
print("The edge set E(G) is :")
# Find the smallest label not present in
# prufer.
j = 0
for i in range(vertices - 2):
for j in range(vertices):
# If j+1 is not present in prufer set
if (vertex_set[j] == 0):
# Remove from Prufer set and print
# pair.
vertex_set[j] = -1
print("(" , (j + 1),", ",prufer[i],") ",sep = "",end = "")
vertex_set[prufer[i] - 1] -= 1
break
j = 0
# For the last element
for i in range(vertices):
if (vertex_set[i] == 0 and j == 0):
print("(", (i + 1),", ", sep="", end="")
j += 1
else if (vertex_set[i] == 0 and j == 1):
print((i + 1),")")
# Driver code
prufer = [4, 1, 3, 4]
n = len(prufer)
printTreeEdges(prufer, n)
# This code is contributed by SHUBHAMSINGH10
C#
// C# program to construct tree from given Prufer Code
using System;
class GFG {
// Prints edges of tree represented by given Prufer code
static void printTreeEdges(int[] prufer, int m)
{
int vertices = m + 2;
int[] vertex_set = new int[vertices];
// Initialize the array of vertices
for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
Console.Write("\nThe edge set E(G) is :\n");
// Find the smallest label not present in
// prufer[].
int j = 0;
for (int i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
// If j+1 is not present in prufer set
if (vertex_set[j] == 0) {
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
Console.Write("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (int i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
Console.Write("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
Console.Write((i + 1) + ")\n");
}
}
// Driver code
public static void Main(String[] args)
{
int[] prufer = { 4, 1, 3, 4 };
int n = prufer.Length;
printTreeEdges(prufer, n);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to construct tree from given Prufer Code
// Prints edges of tree represented by given Prufer code
function printTreeEdges(prufer,m)
{
let vertices = m + 2;
let vertex_set = new Array(vertices);
// Initialize the array of vertices
for (let i = 0; i < vertices; i++)
vertex_set[i] = 0;
// Number of occurrences of vertex in code
for (let i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;
document.write("<br>The edge set E(G) is :<br>");
// Find the smallest label not present in
// prufer[].
let j = 0;
for (let i = 0; i < vertices - 2; i++) {
for (j = 0; j < vertices; j++) {
// If j+1 is not present in prufer set
if (vertex_set[j] == 0) {
// Remove from Prufer set and print
// pair.
vertex_set[j] = -1;
document.write("(" + (j + 1) + ", "
+ prufer[i] + ") ");
vertex_set[prufer[i] - 1]--;
break;
}
}
}
j = 0;
// For the last element
for (let i = 0; i < vertices; i++) {
if (vertex_set[i] == 0 && j == 0) {
document.write("(" + (i + 1) + ", ");
j++;
}
else if (vertex_set[i] == 0 && j == 1)
document.write((i + 1) + ")\n");
}
}
// Driver code
let prufer=[4, 1, 3, 4];
let n = prufer.length;
printTreeEdges(prufer, n);
// This code is contributed by rag2127
</script>
Producción
The edge set E(G) is : (2, 4) (5, 1) (1, 3) (3, 4) (4, 6)
Este artículo es una contribución de Nikhil Sharma . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA