es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Eliminar un nodo específico en una lista de adyacencia de un grafo dirigido.

01 Aug, 2023 Programación

Hola, tengo esta estructura de información:

struct Node
{
  int dest, weight;
  struct Node *next;
};

Quiero construir una función que elimine un nodo específico con un valor de distancia. Mi función principal para llamar a la función de eliminación se verá así:

int main()
{
       .
       .
       .
      struct Graph *graph;
      Node_delete(graph,x);

   .
   .
   .
}

Si x es igual a 4, entonces la función eliminará cada nodo que contenga el valor de distancia igual a 4. El nodo anterior al nodo medio estará conectado con el siguiente nodo, y si el nodo es el último, se eliminará y el nodo anterior apuntará a null, y así sucesivamente. Por lo tanto, nuestro resultado del gráfico se verá así:

enter image description here

¿Alguna sugerencia sobre cómo puedo construir la función delete_node?

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Para construir la función Node_delete que eliminará nodos con un valor de distancia específico, puedes seguir estos pasos:

    1. Recorre la lista de adyacencia de cada nodo en el grafo utilizando un bucle.
    2. Para cada nodo, recorre su lista enlazada de aristas utilizando otro bucle.
    3. Verifica el peso/distancia de cada arista en la lista enlazada.
    4. Si el peso/distancia es igual al valor objetivo x, elimina la arista ajustando los punteros.
    5. Continúa recorriendo hasta que se hayan verificado todos los nodos en el grafo.

    Aquí tienes un ejemplo de código que implementa el algoritmo anterior:

    void Node_delete(struct Graph* graph, int x) {
    int i;
    for (i = 0; i < graph->V; i++) {
        struct Node* temp = graph->array[i].head;
        struct Node* prev = NULL;

        while (temp != NULL) {
            if (temp->weight == x) {
                if (prev == NULL) {
                    // Eliminando el nodo inicial
                    graph->array[i].head = temp->next;
                } else {
                    prev->next = temp->next;
                }
                struct Node* t = temp;
                temp = temp->next;
                free(t);
            } else {
                prev = temp;
                temp = temp->next;
            }
        }
    }
}

    En este código, graph->array es un arreglo de listas de adyacencia, y graph->V es el número de vértices en el grafo. El bucle recorre cada lista de adyacencia utilizando un puntero de nodo temporal temp. Un puntero secundario prev se utiliza para realizar un seguimiento del nodo anterior en la lista enlazada, de modo que podamos ajustar correctamente los punteros.

    Si temp->weight == x, entonces hemos encontrado un nodo que debe ser eliminado. Verificamos si es el nodo inicial de la lista enlazada (lo cual requiere un manejo especial) y ajustamos los punteros en consecuencia. Luego liberamos la memoria asignada para el nodo utilizando free(t). Si el peso/distancia no es igual a x, continuamos recorriendo la lista enlazada.

    Con esta función definida, puedes llamar Node_delete(graph, 4) para eliminar todos los nodos con un valor de distancia de 4 del grafo, como se muestra en tu ejemplo.

Comments are closed.