Generando el powerset en c -- ampo con programming-challenge campo con combinatorics campo con depth-first-search camp codereview Relacionados El problema

Generating the powerset in C


10
vote

problema

Español

Estoy resolviendo otra problema en leetcode .

Dado un conjunto, genere todos los subconjuntos del conjunto.

Entrada: [1,2,3]
Salida: [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

Se acepta la solución, pero me gustaría mejorar en mi estilo de codificación C. He creado un tipo 99887766655443333 para encapsular los datos relacionados con cada subconjunto. Podría haber una forma menos detallada de hacer esto. Dos métodos populares para resolver este problema parecen ser:

  1. retroceso
  2. Un subconjunto es igual al número binario â ¤ n donde n es el conteo de elementos.
  #include <stdio.h> #include <stdlib.h> #include <string.h>   typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t;  node_t* alloc_node() {     return (node_t*)malloc(sizeof(node_t)); }  void free_node(node_t *node) {     free(node); } #define SIZE 3  void print_one(int *one) {     printf("%d ", *one); } void print_1d_array(int *array, int size) {     for(int i = 0; i < size; i++) {         print_one(&array[i]);     }     printf(" "); } void print_2d_array(int **array, int *col_sizes, int size) {     for (int i = 0; i < size; i++) {         print_1d_array(array[i], col_sizes[i]);     } } int** create_solution_array(node_t *head, int ans_size, int **column_sizes) {     int **ans = (int**)malloc(sizeof(int*)*ans_size);      node_t *iter;     iter = head->next;     int idx = 0;     while(iter) {         ans[idx] = iter->array;         (*column_sizes)[idx] = iter->size;         idx++;         iter = iter->next;     }     return ans; }  void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) {     if (idx == num_size) {         node_t *new_node = alloc_node();         if (cur_size) {             new_node->array = (int *) malloc(sizeof(int) * cur_size);             new_node->size = cur_size ;             memcpy(new_node->array, cur, cur_size*sizeof(int));         }         (*iter_node)->next = new_node;         *iter_node = new_node;         (*ans_size)++;         return;     }      gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);     *(cur + cur_size) = num[idx];     gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size); }  int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {     node_t  *head = alloc_node();     node_t  *iter = head;     int     *cur = (int*)malloc(sizeof(int)*numsSize);     gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);     return create_solution_array(head, *returnSize, columnSizes); }   int main () {     int *nums = (int*)malloc(sizeof(int)*SIZE);     for (int i = 0; i < SIZE; i++) {         nums[i] = i+1;     }     int *col_sizes = (int*)malloc(sizeof(int)*SIZE);     int ans_size;     int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);     print_2d_array(ans, col_sizes, ans_size);     return 0; }   
Original en ingles

I am solving another problem in leetcode.

Given a set, generate all the subsets of the set.

Input: [1,2,3]
Output: [ [3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

The solution is accepted but I would like to improve on my C coding style. I have created a node_t type to encapsulate the data related each subset. There could be less verbose ways to do this. Two popular methods of solving this problem seem to be:

  1. backtracking
  2. a subset equals to binary number xe2x89xa4 n where n is element count.
#include <stdio.h> #include <stdlib.h> #include <string.h>   typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t;  node_t* alloc_node() {     return (node_t*)malloc(sizeof(node_t)); }  void free_node(node_t *node) {     free(node); } #define SIZE 3  void print_one(int *one) {     printf("%d ", *one); } void print_1d_array(int *array, int size) {     for(int i = 0; i < size; i++) {         print_one(&array[i]);     }     printf("\n"); } void print_2d_array(int **array, int *col_sizes, int size) {     for (int i = 0; i < size; i++) {         print_1d_array(array[i], col_sizes[i]);     } } int** create_solution_array(node_t *head, int ans_size, int **column_sizes) {     int **ans = (int**)malloc(sizeof(int*)*ans_size);      node_t *iter;     iter = head->next;     int idx = 0;     while(iter) {         ans[idx] = iter->array;         (*column_sizes)[idx] = iter->size;         idx++;         iter = iter->next;     }     return ans; }  void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) {     if (idx == num_size) {         node_t *new_node = alloc_node();         if (cur_size) {             new_node->array = (int *) malloc(sizeof(int) * cur_size);             new_node->size = cur_size ;             memcpy(new_node->array, cur, cur_size*sizeof(int));         }         (*iter_node)->next = new_node;         *iter_node = new_node;         (*ans_size)++;         return;     }      gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);     *(cur + cur_size) = num[idx];     gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size); }  int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {     node_t  *head = alloc_node();     node_t  *iter = head;     int     *cur = (int*)malloc(sizeof(int)*numsSize);     gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);     return create_solution_array(head, *returnSize, columnSizes); }   int main () {     int *nums = (int*)malloc(sizeof(int)*SIZE);     for (int i = 0; i < SIZE; i++) {         nums[i] = i+1;     }     int *col_sizes = (int*)malloc(sizeof(int)*SIZE);     int ans_size;     int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);     print_2d_array(ans, col_sizes, ans_size);     return 0; } 
           
 
 

Lista de respuestas

8
 
vote

Solo trabajaré a través de esto desde la parte superior:

  #include <stdio.h> #include <stdlib.h> #include <string.h>   

se ve bien; Necesitamos estos.


  typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t;   

Es habitual usar la misma etiqueta de estructura que el nombre TyPENAME vamos a usar: struct node_t .

Si size es el número de elementos en la matriz, un tipo más natural puede ser 9988777665544334 .


  node_t* alloc_node() {     return (node_t*)malloc(sizeof(node_t)); }   

Todo lo que hace es asignar la memoria. Considere la inicialización de los valores de los miembros a SANE, también:

  node_t* alloc_node() {     node_t *n = malloc(sizeof *n);     if (n) {         n->array = NULL;         n->size = 0;         n->next = NULL;     }     return n; }   

Estamos escribiendo C, por lo que es no se recomienda fundar el resultado de malloc() . ¡Pero no podemos asumir que sucede!

Es un buen hábito usar la variable asignada en el argumento de sizeof , en lugar de su tipo; que nos ahorra el trabajo mental de tener que verificar que el tipo realmente coincide. Es por eso que he usado sizeof *n en lugar de typedef struct node_s { int *array; int size; struct node_s *next; } node_t; 0 aquí; Verá simplemente seguir un ejemplo en el que estamos más lejos de la Declaración y este idioma tiene más beneficios.

Es posiblemente una buena idea crear la matriz al mismo tiempo:

  typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t; 1  

  typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t; 2  

Suponiendo que el nodo posee su matriz, debemos liberar eso también:

  typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t; 3  

¿El nodo posee su typedef struct node_s { int *array; int size; struct node_s *next; } node_t; 4 también? Si es así, necesitamos liberar eso, o tal vez devolverlo.


  typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t; 5  

¿Por qué está esto en el medio aquí? Debería tener razón al principio (o quizás justo antes de typedef struct node_s { int *array; int size; struct node_s *next; } node_t; 6 ).


  typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t; 7  

No estoy convencido de que hay mucho beneficio de encapsular esto como una función.


  typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t; 8  

Deberíamos usar typedef struct node_s { int *array; int size; struct node_s *next; } node_t; 9 para el conteo aquí:

  struct node_t0  

  struct node_t1  

OTRO struct node_t2 (está bien, dejaré de mencionar esto ahora).


  struct node_t3  

Aparte de los puntos desde antes, ese struct node_t4 BOOP tiene una inicialización y un avance, por lo que es realmente un bucle

  struct node_t6  

  struct node_t7  

struct node_t8 normalmente está escrito struct node_t9 .

Necesitamos verificar si nuestras asignaciones tuvieron éxito:

  size0  

  size1  

de nuevo, compruebe que size2 sucedió, y compruebe que size3 sucedió.


  size4  

Tener cuidadosamente creado size5 , nos olvidamos completamente de usarlo. Valgrind revela una fuga sustancial debido a esto. Tenemos que liberar la otra memoria asignada, también.

 

I'll just work through this from the top:

#include <stdio.h> #include <stdlib.h> #include <string.h> 

Looks good; we need these.


typedef struct node_s {     int *array;     int  size;     struct node_s *next; } node_t; 

It's usual to use the same structure tag as the typename we're going to use: struct node_t.

If size is the number of elements in the array, a more natural type might be size_t.


node_t* alloc_node() {     return (node_t*)malloc(sizeof(node_t)); } 

All this does is to allocate the memory. Consider initialising the members to sane values, too:

node_t* alloc_node() {     node_t *n = malloc(sizeof *n);     if (n) {         n->array = NULL;         n->size = 0;         n->next = NULL;     }     return n; } 

We're writing C, so it's not advised to cast the result of malloc(). But we can't assume it succeeds!

It's a good habit to use the assigned-to variable in the argument of sizeof, rather than its type; that saves us the mental work of having to check that the type actually matches. That's why I've used sizeof *n in place of sizeof (node_t) here; you'll see just following an example where we're further from the declaration and this idiom has more benefit.

It's possibly a good idea to create the array at the same time:

node_t* alloc_node(size_t array_count) {     node_t *n = malloc(sizeof *n);     if (n) {         n->array = malloc(sizeof *n->array * array_count);         n->size = n->array ? array_count : 0;         n->next = NULL;     }     return n; } 

void free_node(node_t *node) {     free(node); } 

Assuming that the node owns its array, we need to free that, too:

void free_node(node_t *node) {     if (node) {         free(node->array);     }     free(node); } 

Does the node own its next as well? If so, we need to free that, or perhaps return it.


#define SIZE 3 

Why is this in the middle here? It should be right at the beginning (or perhaps just before main()).


void print_one(int *one) {     printf("%d ", *one); } 

I'm not convinced there's much benefit to encapsulating this as a function.


void print_1d_array(int *array, int size) {     for(int i = 0; i < size; i++) {         print_one(&array[i]);     }     printf("\n"); } 

We should use size_t for the count here:

void print_1d_array(int *array, size_t size) {     for (size_t i = 0;  i < size;  ++i) {         printf("%d ", array[i]);     }     printf("\n"); } 

void print_2d_array(int **array, int *col_sizes, int size) {     for (int i = 0; i < size; i++) {         print_1d_array(array[i], col_sizes[i]);     } } 

Another size_t (okay, I'll stop mentioning these now).


int** create_solution_array(node_t *head, int ans_size, int **column_sizes) {     int **ans = (int**)malloc(sizeof(int*)*ans_size);      node_t *iter;     iter = head->next;     int idx = 0;     while(iter) {         ans[idx] = iter->array;         (*column_sizes)[idx] = iter->size;         idx++;         iter = iter->next;     }     return ans; } 

Aside from points from earlier, that while loop has an initialisation and an advancement, so it's really a for loop:

int** create_solution_array(node_t *head, size_t ans_size, size_t **column_sizes) {     int **ans = malloc(sizeof *ans * ans_size);      if (ans) {         int idx = 0;         for (node_t *iter = head->next;  iter;  iter = iter->next) {             ans[idx] = iter->array;             (*column_sizes)[idx] = iter->size;             ++idx;         }     }     return ans; } 

void gen_powerset(int *num, int num_size, int idx, int cur_size, int *cur, node_t **iter_node, int *ans_size) {     if (idx == num_size) {         node_t *new_node = alloc_node();         if (cur_size) {             new_node->array = (int *) malloc(sizeof(int) * cur_size);             new_node->size = cur_size ;             memcpy(new_node->array, cur, cur_size*sizeof(int));         }         (*iter_node)->next = new_node;         *iter_node = new_node;         (*ans_size)++;         return;     }      gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size);     *(cur + cur_size) = num[idx];     gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size); } 

*(cur + cur_size) is normally written cur[cur_size].

We need to check whether our allocations succeeded:

/* true if successful, false on any error (e.g. out of memory) */ bool gen_powerset(int *num, size_t num_size, size_t idx,                   size_t cur_size, int *cur, node_t **iter_node,                   size_t *ans_size) {     if (idx == num_size) {         node_t *new_node = alloc_node(cur_size);         if (!new_node || new_node->size != cur_size) {             return false;         }         if (cur_size) {             memcpy(new_node->array, cur, sizeof *cur * cur_size);         }         (*iter_node)->next = new_node;         *iter_node = new_node;         ++*ans_size;         return true;     }      cur[cur_size] = num[idx];      return gen_powerset(num, num_size, idx + 1, cur_size, cur, iter_node, ans_size)         && gen_powerset(num, num_size, idx + 1, cur_size + 1, cur, iter_node, ans_size); } 

int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize) {     node_t  *head = alloc_node();     node_t  *iter = head;     int     *cur = (int*)malloc(sizeof(int)*numsSize);     gen_powerset(nums, numsSize, 0, 0, cur, &iter, returnSize);     return create_solution_array(head, *returnSize, columnSizes); } 

Again, check that malloc() succeeded, and check that gen_powerset() succeeded.


int main () {     int *nums = (int*)malloc(sizeof(int)*SIZE);     for (int i = 0; i < SIZE; i++) {         nums[i] = i+1;     }     int *col_sizes = (int*)malloc(sizeof(int)*SIZE);     int ans_size;     int ** ans = subsets(nums, SIZE, &col_sizes, &ans_size);     print_2d_array(ans, col_sizes, ans_size);     return 0; } 

Having carefully created free_node(), we completely forgot to use it. Valgrind reveals a substantial leak due to this. We need to free the other allocated memory, too.

 
 
 
 
5
 
vote

Me suscribo a todo @tobyspeight dijo.

También creo que podría hacer que su código sea más claro (y su estilo de codificación mejor) obedeciendo algunas reglas importantes:

En caso de duda, elija el algoritmo más simple

Representación binaria de números entre 0 y el tamaño del POTERSET son la herramienta más sencilla para calcular los subconjuntos del POTERSET; 0 significa la ausencia, 1 la presencia de un elemento del conjunto inicial:

  // {1, 2, 3} // 000 -> {} // 001 -> {3} // 010 -> {2} // ... // 111 -> {1,2,3}   

Dado que el tamaño del POTERSET es 2^N , donde 9988776655544332 es la cardinalidad del conjunto y se le da una función que toma el conjunto original y un número para devolver el subconjunto Se caracteriza por este número, una matriz simple y un simple 998877765555443333 es suficiente para lograr nuestro objetivo:

  for (int i = 0; i < pow(2, set.size); ++i)     powerset[i] = subset(set, i);   

que es bastante más sencillo que los nodos vinculados, etc.

en caso de duda, agrupe lo que va bien

Fuera de casos especiales, como la cadena C, un puntero sin un tamaño no será de mucho uso para representar un rango. Por lo tanto, mantenga el puntero y el tamaño juntos, en lugar de tener matrices de punteros y matrices de tamaños de lado a lado, como en su función subsets :

  typedef struct {   int* items;   size_t size; } Set;  typedef struct {   Set* subsets;   size_t size; } Powerset;   

Si desea llenarlos, imprímelos, libere, deberá tener ambas informaciones, porque no puede deducir uno de la otra.

Un ejemplo de trabajo:

  #include <stdio.h> #include <stdlib.h> #include <math.h>  typedef struct {   int* items;   size_t size; } Set;  typedef struct {   Set* subsets;   size_t size; } Powerset;  int is_bit_on(int n, int pos) {   return (n >> pos) & 1; }  int set_bits(int n) {   // any set bits counting function will do fine   // this one is gcc only   return __builtin_popcount(n);   // but you could have to write your own;   // see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer }  Set subset(Set set, int step) {   int* subset = malloc(sizeof(int) * set_bits(step));   if (subset == NULL) {     Set failure = { .items = NULL, .size = 0 };     return failure;   }   int elem_n = 0;   for (; set.size > 0; --set.size) {     if (is_bit_on(step, set.size - 1))       subset[elem_n++] = set.items[set.size-1];   }   Set ret = { .items = subset, .size = elem_n };   return ret; }  Powerset powerset(Set set) {   size_t powerset_size = pow(2, set.size);   Powerset powerset = {     .subsets = malloc(sizeof(Set) * powerset_size),     .size  = powerset_size   };   Powerset failure = { .subsets = NULL, .size = 0 };   if (powerset.subsets == NULL) return failure;    for (size_t i = 0; i < powerset_size; ++i) {     powerset.subsets[i] = subset(set, i);     if (powerset.subsets[i].items == NULL) {       for (size_t j = 0; j < i; ++j) {         free(powerset.subsets[j].items);       }       return failure;     }   }   return powerset; }  void free_powerset(Powerset powerset) {   for (size_t i = 0; i < powerset.size; ++i) {     free(powerset.subsets[i].items);   }   free(powerset.subsets); }  void print_array(Set array) {   for (size_t i = 0; i < array.size; ++i)     printf("%d, ", array.items[i]);   printf(" "); }   int main(void) {   int items[] = {1, 2, 3};    Set set = { .items = items, .size = 3};   Powerset test = powerset(set);    if (test.subsets == NULL) {     printf("Bad allocation");     return 1;   }    for (size_t i = 0; i < test.size; ++i)     print_array(test.subsets[i]);    free_powerset(test);   return 0; }   
 

I subscribe to everything @TobySpeight said.

I also believe that you could make your code a lot clearer (and your coding style better) by obeying a few important rules:

When in doubt, choose the simplest algorithm

Binary representation of numbers between 0 and the size of the powerset are the simplest tool to compute the subsets of the powerset; 0 means the absence, 1 the presence of an element of the initial set:

// {1, 2, 3} // 000 -> {} // 001 -> {3} // 010 -> {2} // ... // 111 -> {1,2,3} 

Since the size of the powerset is 2^N, where N is the cardinality of the set, and given a function taking the original set and a number to return the subset characterized by this number, a simple array and a simple for loop are enough to achieve our objective:

for (int i = 0; i < pow(2, set.size); ++i)     powerset[i] = subset(set, i); 

That is quite simpler than linked nodes etc.

When in doubt, bundle together what goes together well

Outside of special cases, like the C-string, a pointer without a size won't be of much use to represent a range. So keep the pointer and the size together, rather than having arrays of pointers and arrays of sizes side by side, as in your subsets function:

typedef struct {   int* items;   size_t size; } Set;  typedef struct {   Set* subsets;   size_t size; } Powerset; 

Whether you want to fill them, print them, free them, you'll need to have both informations, because you can't deduce one from the other.

A working example:

#include <stdio.h> #include <stdlib.h> #include <math.h>  typedef struct {   int* items;   size_t size; } Set;  typedef struct {   Set* subsets;   size_t size; } Powerset;  int is_bit_on(int n, int pos) {   return (n >> pos) & 1; }  int set_bits(int n) {   // any set bits counting function will do fine   // this one is gcc only   return __builtin_popcount(n);   // but you could have to write your own;   // see https://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer }  Set subset(Set set, int step) {   int* subset = malloc(sizeof(int) * set_bits(step));   if (subset == NULL) {     Set failure = { .items = NULL, .size = 0 };     return failure;   }   int elem_n = 0;   for (; set.size > 0; --set.size) {     if (is_bit_on(step, set.size - 1))       subset[elem_n++] = set.items[set.size-1];   }   Set ret = { .items = subset, .size = elem_n };   return ret; }  Powerset powerset(Set set) {   size_t powerset_size = pow(2, set.size);   Powerset powerset = {     .subsets = malloc(sizeof(Set) * powerset_size),     .size  = powerset_size   };   Powerset failure = { .subsets = NULL, .size = 0 };   if (powerset.subsets == NULL) return failure;    for (size_t i = 0; i < powerset_size; ++i) {     powerset.subsets[i] = subset(set, i);     if (powerset.subsets[i].items == NULL) {       for (size_t j = 0; j < i; ++j) {         free(powerset.subsets[j].items);       }       return failure;     }   }   return powerset; }  void free_powerset(Powerset powerset) {   for (size_t i = 0; i < powerset.size; ++i) {     free(powerset.subsets[i].items);   }   free(powerset.subsets); }  void print_array(Set array) {   for (size_t i = 0; i < array.size; ++i)     printf("%d, ", array.items[i]);   printf("\n"); }   int main(void) {   int items[] = {1, 2, 3};    Set set = { .items = items, .size = 3};   Powerset test = powerset(set);    if (test.subsets == NULL) {     printf("Bad allocation");     return 1;   }    for (size_t i = 0; i < test.size; ++i)     print_array(test.subsets[i]);    free_powerset(test);   return 0; } 
 
 
       
       

Relacionados problema

7  Árboles binarios equivalentes (un recorrido por go)  ( Equivalent binary trees a tour of go ) 
Cualquier sugerencia sobre cómo mejorar el código que se muestra a continuación para la Ejercicio de go-tour ? < / p> Descripción del ejercicio: Puede ha...

12  Método de búsqueda de primera profundidad para buscar todos los "superpalindromos" cuyos factores primos son todos <= n  ( Depth first search method for searching for all superpalindromes whose prime f ) 
Se solicitó una pregunta en math.se ( aquí ) sobre si hay o no infinitamente muchosDerromas de superpalindros. Voy a reformular la definición a uno más adecua...

6  BFS / DFS Web Crawler  ( Bfs dfs web crawler ) 
He construido un rastreador web que comienza en una URL de origen y rastrea la web con un método BFS o DFS. Todo está funcionando bien, pero la actuación es h...

9  Rango de hackers: viaje a la luna (teoría del gráfico)  ( Hacker rank journey to the moon graph theory ) 
Estoy intentando completar el problema "Viaje a la luna" Descrito a continuación: Hay n astronautas entrenados numerados de 0 a N-1. Pero aquellos en E...

2  Un generador de laberinto Scala en estilo funcional  ( A scala maze generator in functional style ) 
Me pregunto si hay más que puedo hacer para incorporar más principios de programación de Scala y funcionales idiomáticos. Sé que el laberinto es silencioso, p...

4  Profundidad Primera búsqueda usando Stack en Python  ( Depth first search using stack in python ) 
He implementado una primera búsqueda de profundidad usando una pila (en una clase separada). Cualquier sugerencia por favor en las mejoras para el siguiente c...

8  Profundidad-Primera búsqueda en Python  ( Depth first search in python ) 
Escribí este DFS en Python y me preguntaba si es correcto. De alguna manera, parece demasiado simple para mí. Cada nodo es una clase con atributos: vis...

1  Algoritmo de Minesweeper que funciona dentro de O (1) complejidad espacial  ( Minesweeper algorithm that works within o1 space complexity ) 
Para el algoritmo de minasweeper, en lugar de la solución BFS o DFS más obvia, quiero una solución espacial O (1). En primer lugar, le explicaré cómo funcio...

5  HEURRÍSTICAS DEL PARE CERCANO, GRÁFICO CON MATRIX DE ADJUSTAJE EN C ++ 17  ( Closest pair heuristics graph with adjacency matrix in c17 ) 
Estaba tratando de resolver un problema que se mencionó brevemente al comienzo del "Manual de diseño del algoritmo" por Steven Skiena (CH 1, Problema 26). M...

2  Implementación dirigida al gráfico en Java  ( Directed graph implementation in java ) 
Aquí he adjuntado mi implementación de Java de un gráfico dirigido. He usado un mecánico de lista de adyacencia modificada para utilizar un mapa en lugar de u...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos