Iniciar sesiónCerrar
Correo:
Contraseña:
Entrar
Recordar sesión en este navegador
Iniciar sesiónIniciar sesiónCrear cuentaCrear cuenta
LWP » Foros » Algoritmia » algoritmo para hallar paths y walks en grafos

Algoritmia - algoritmo para hallar paths y walks en grafos

Volver
Nuevo Tema
<<>>
 
Vista:

algoritmo para hallar paths y walks en grafos

Publicado por jose (1 intervención) el 02/12/2002 21:00:20
Necesito un algoritmo que halle en un grafo no dirigido los paths de longitud K. Igualmente necesito otro que halle los walks de longitud k. GRACIAS
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder
Imágen de perfil de Alejandro

Búsqueda de paths y walks en un grafo no dirigido

Publicado por Alejandro (307 intervenciones) el 28/02/2024 00:49:18
José, aquí te proporcionaré algoritmos simples para encontrar paths y walks de longitud k en un grafo no dirigido. Vamos a asumir que el grafo está representado como una lista de adyacencia.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.ArrayList;
import java.util.LinkedList;
 
public class Grafo {
    private int vertices;
    private ArrayList<LinkedList<Integer>> listaAdyacencia;
 
    public Grafo(int vertices) {
        this.vertices = vertices;
        this.listaAdyacencia = new ArrayList<>(vertices);
 
        for (int i = 0; i < vertices; i++) {
            listaAdyacencia.add(new LinkedList<>());
        }
    }
 
    public void agregarArista(int origen, int destino) {
        listaAdyacencia.get(origen).add(destino);
        listaAdyacencia.get(destino).add(origen);
    }
 
    public void encontrarPaths(int origen, int destino, int k) {
        boolean[] visitado = new boolean[vertices];
        ArrayList<Integer> path = new ArrayList<>();
        path.add(origen);
        encontrarPathsUtil(origen, destino, k, visitado, path);
    }
 
    private void encontrarPathsUtil(int actual, int destino, int k, boolean[] visitado, ArrayList<Integer> path) {
        visitado[actual] = true;
 
        if (actual == destino && path.size() == k + 1) {
            System.out.println(path);
        }
 
        if (path.size() <= k) {
            for (int vecino : listaAdyacencia.get(actual)) {
                if (!visitado[vecino]) {
                    path.add(vecino);
                    encontrarPathsUtil(vecino, destino, k, visitado, path);
                    path.remove(path.size() - 1);
                }
            }
        }
 
        visitado[actual] = false;
    }
 
    public void encontrarWalks(int origen, int destino, int k) {
        boolean[] visitado = new boolean[vertices];
        ArrayList<Integer> path = new ArrayList<>();
        path.add(origen);
        encontrarWalksUtil(origen, destino, k, visitado, path);
    }
 
    private void encontrarWalksUtil(int actual, int destino, int k, boolean[] visitado, ArrayList<Integer> path) {
        visitado[actual] = true;
 
        if (path.size() == k + 1) {
            System.out.println(path);
        }
 
        if (path.size() <= k) {
            for (int vecino : listaAdyacencia.get(actual)) {
                if (!visitado[vecino]) {
                    path.add(vecino);
                    encontrarWalksUtil(vecino, destino, k, visitado, path);
                    path.remove(path.size() - 1);
                }
            }
        }
 
        visitado[actual] = false;
    }
 
    public static void main(String[] args) {
        Grafo grafo = new Grafo(4);
        grafo.agregarArista(0, 1);
        grafo.agregarArista(0, 2);
        grafo.agregarArista(1, 2);
        grafo.agregarArista(2, 0);
        grafo.agregarArista(2, 3);
        grafo.agregarArista(3, 3);
 
        System.out.println("Paths de longitud 2:");
        grafo.encontrarPaths(0, 2, 2);
 
        System.out.println("\nWalks de longitud 2:");
        grafo.encontrarWalks(0, 2, 2);
    }
}

Este código en Java presenta dos métodos, `encontrarPaths` y `encontrarWalks`, para buscar paths y walks de longitud k en un grafo no dirigido, respectivamente. Puedes adaptar este código según tus necesidades y la representación específica de tu grafo.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar