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.

  • es.davy.ai/
  • Programación /
  • DFS (Búsqueda en profundidad) | BFS (Búsqueda en anchura): Verificar si existe un camino entre el nodo A y el nodo B.

DFS (Búsqueda en profundidad) | BFS (Búsqueda en anchura): Verificar si existe un camino entre el nodo A y el nodo B.

02 Aug, 2023 Programación

En un grafo bidireccional, verifica si existe un camino entre el nodo A y el nodo B.

Mi código no funciona para ciertas entradas (muestras proporcionadas a continuación). ¿Esta implementación es correcta o me he perdido algo?

bool[] visited = null;
public bool ValidPath(int n, int[][] edges, int start, int end) {
    IList<int>[] adjacencyList = new List<int>[n];
    visited = new bool[n];

    // crea la lista de adyacencia
    for(int i = 0; i < edges.Length; i++){
        int a = edges[i][0];
        int b = edges[i][1];

        if(adjacencyList[a] == null)
            adjacencyList[a] = new List<int>();
        adjacencyList[a].Add(b);

        if(adjacencyList[b] == null)
            adjacencyList[b] = new List<int>();
        adjacencyList[b].Add(a);            
    }

    return DFS(adjacencyList, start, end);
}

private bool DFS(IList<int>[] adjacencyList, int start, int end){
    if(start == end) return true;

    if(!visited[start]){
        visited[start] = true;
        foreach(var v in adjacencyList[start]){
            if(v == end) return true;
            if(!visited[v])
                DFS(adjacencyList, v, end);
        }
    }
    return false;
}

Esto funciona para los ejemplos siguientes:

Entrada: n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
Salida: verdadero

Entrada: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
Salida: falso

No funciona para el siguiente caso (el valor de retorno esperado es verdadero, pero obtengo falso):

Entrada: 10, edges = [[4,3],[1,4],[4,8],[1,7],[6,4],[4,2],[7,4],[4,0],[0,9],[5,4]], start = 5, end = 9

Tags:  , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    La implementación proporcionada está incompleta ya que solo realiza una búsqueda en profundidad (DFS) desde el nodo inicial hasta el nodo final. Para un grafo bidireccional, es necesario realizar dos búsquedas DFS, una desde el nodo inicial y otra desde el nodo final, y verificar si hay algún nodo visitado en común. Esto se debe a que los grafos bidireccionales permiten el recorrido en ambas direcciones, es decir, los nodos pueden alcanzarse desde ambas direcciones. La implementación actual solo verifica si el nodo final es alcanzable desde el nodo inicial pero no viceversa.

    Para solucionar esto, la función DFS puede ser extendida para tomar tanto el nodo inicial como el nodo final como argumentos y recorrer el grafo desde ambas direcciones hasta encontrar un nodo visitado en común. A continuación se muestra una implementación actualizada:

    bool[] visitadoDesdeInicio = null;
bool[] visitadoDesdeFin = null;

public bool RutaValida(int n, int[][] aristas, int inicio, int fin) {
    IList<int>[] listaDeAdyacencia = new List<int>[n];
    visitadoDesdeInicio = new bool[n];
    visitadoDesdeFin = new bool[n];

    // crear lista de adyacencia
    for(int i = 0; i < aristas.Length; i++){
        int a = aristas[i][0];
        int b = aristas[i][1];

        if(listaDeAdyacencia[a] == null)
            listaDeAdyacencia[a] = new List<int>();
        listaDeAdyacencia[a].Add(b);

        if(listaDeAdyacencia[b] == null)
            listaDeAdyacencia[b] = new List<int>();
        listaDeAdyacencia[b].Add(a);            
    }

    return DFS(listaDeAdyacencia, inicio, fin);
}

private bool DFS(IList<int>[] listaDeAdyacencia, int inicio, int fin){
    if(inicio == fin) return true;

    visitadoDesdeInicio[inicio] = true;
    foreach(var v in listaDeAdyacencia[inicio]){
        if(visitadoDesdeFin[v]) return true;
        if(!visitadoDesdeInicio[v])
            if(DFS(listaDeAdyacencia, v, fin))
                return true;
    }

    visitadoDesdeFin[fin] = true;
    foreach(var v in listaDeAdyacencia[fin]){
        if(visitadoDesdeInicio[v]) return true;
        if(!visitadoDesdeFin[v])
            if(DFS(listaDeAdyacencia, inicio, v))
                return true;
    }

    return false;
}

    En esta implementación actualizada, se utilizan dos arreglos de visitados separados para llevar un registro de los nodos visitados desde ambas direcciones. La función DFS ahora toma tanto el nodo inicial como el nodo final como argumentos y realiza un DFS desde ambas direcciones hasta encontrar un nodo visitado en común. Si se encuentra un nodo visitado en común, la función devuelve true, lo que indica que existe un camino entre los nodos inicial y final. De lo contrario, devuelve false. Esta implementación actualizada debería poder manejar correctamente los grafos bidireccionales.

Comments are closed.