Encontrar un árbol de extinción mínimo de una lista de adyacencia donde la lista de adyacencia está en una matriz de cadena usando el algoritmo primos

Question

Así que necesito ayuda para encontrar una manera de encontrar un árbol mínimo que abarca. Supongamos que tengo mi gráfica en forma de una lista de adyacencia:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

La primera letra cuenta a qué nodo está mirando, y el número dice cuántas conexiones con cualquier otro nodo hay.Por ejemplo, A tiene dos conexiones, una cada una a B y I. Después de eso, el número que sigue las letras simplemente contar el peso de un borde.B tiene peso 12 y tengo peso 25. Así que originalmente había planeado representar todo esto como una matriz de cadenas. Llamado Graph[8].Cada línea sería una ranura diferente en la matriz.Estoy teniendo dificultades para determinar cómo lograr esto con el algoritmo primos o kruskalls.

Answer 1

Supongamos que tengo mi árbol en forma de una lista de adyacencia

Es importante (para su comprensión) observar que tiene un gráfico conectado en este tipo de una lista de adyacencia, pero creo que fue solo un error tipográfico. Proponeré esto como una edición, pero solo quiero que seas consciente de ello. El hecho de que sea un gráfico y no se puede ver un árbol de esas líneas:

A 2 B 12 I 25
B 3 C 10 H 40 I 8

Aquí tienes un círculo en A-B-I:

     A
  12/_\25
   B 8 I

Tener un círculo por definición significa que no puede ser un árbol! Hay una cosa más que se puede ver desde la forma en que presenté este subgrafo: Los bordes tienen pesos, no los nodos.

---

Ahora echemos un vistazo a su ejemplo proporcionado:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

En primer lugar, podemos ver que esta lista de adyacencia es incorrecta o ya está optimizada para sus necesidades. Esta lata (por ejemplo) se ve desde las líneas

E 2 F 60 G 38
F 0

La primera línea aquí muestra un borde de E a F, pero la segunda línea dice que F tenía un grado de 0, ¡pero el grado está definido por los bordes incidentes!

Esto es cómo se vería la lista de adyacencia si estuviera "completo":

A 2 B 12 I 25
B 4 A 12 C 10 H 40 I 8
C 3 B 10 D 18 G 55
D 2 C 18 E 44
E 3 D 44 F 60 G 38
F 1 E 60
G 3 C 55 E 38 H 35
H 3 B 40 G 35 I 35

Podemos ver mucha redundancia porque cada borde ocurre dos veces, es por eso que su lista de adyacencia "optimizada" se adapta mejor a sus necesidades, ¿sería este ejemplo "completo", uno haría muchos controles inútiles? Sin embargo, debe solo confiar en esto si puede estar seguro de que todos los datos que se le otorgan a su código ya están 'optimizados' (o más bien en este formato)! Tomaré esto como un dado de ahora en adelante.

---

Hablemos de su estructura de datos. Por supuesto, puede usar su gama de cuerdas propuesta, pero para ser honesto, preferiría recomendar algo como la estructura de datos propuesta de @ Amirafghani. El uso de su enfoque facilitaría su trabajo (como lo señaló, estaría más cerca de su representación mental ) y aún más eficiente (supongo, no confíe en esta suposición;) ) Como usted estaría haciendo muchas operaciones en cadenas de otra manera. En el título que solicitó después del algoritmo de Prim, pero en su pregunta real, dijo ya sea Prim's o Kruskal's. Iré con Kruskal simplemente porque su algoritmo es más fácil y pareces aceptar ambos.

---

Algoritmo de Kruskal

El algoritmo de Kruskal es bastante simple, es básicamente:

• comienza con cada nodo, pero no hay bordes

  Repetir lo siguiente con la mayor frecuencia posible:

  • de todos los bordes no utilizados / no basados, elija el que tiene el menor peso (si hay más de uno: solo elija uno de ellos)
  • Compruebe si este borde causaría un círculo, si lo hace, marquelo como elegido y "deseche".
  • Si no causa un círculo, úselo y marquelo como se usa / elegido.

    Eso es todo. Es realmente tan simple. Sin embargo, me gustaría mencionar una cosa en este punto, creo que mejor se ajusta aquí: no hay "el árbol mínimo de expansión" en general, pero "un árbol mínimo que abarca" ya que puede haber muchos, ¡así que sus resultados pueden variar!

    ---

    Volver a la estructura de datos! Ahora puede ver por qué sería una mala idea usar una matriz de cadenas como una estructura de datos. Repetiría muchas operaciones en cadenas (por ejemplo, verificar el peso de cada borde) y las cadenas son inmutables , eso significa que no puede simplemente "tirar" uno de los bordes o Marque uno de los bordes de cualquier manera. ¡Usando un enfoque diferente, simplemente podría establecer el peso a -1, o incluso eliminar la entrada para el borde!

    ---

    Búsqueda de profundidad-First

    De lo que he visto. Creo que su problema principal es decidir si un borde causaría un círculo o no, ¿verdad? Para decidir esto, es probable que tenga que llamar a un algoritmo de búsqueda de profundidad y usar su valor de devolución. La idea básica es esto: comienza desde uno de los nodos (llamaré a este nodo la raíz)

y trate de encontrar una manera al nodo en el otro extremo del borde elegido (llamaré a este nodo el nodo de destino).(Por supuesto, en el gráfico que aún no tiene esta ventaja)

• Elija un incidente de borde no visto a su raíz
• Marque este borde elegido como lo visitó (o algo así, lo que quiera)
• Repita los últimos dos pasos para el nodo en el otro lado del borde visitado
• siempre que no haya bordes no visitados, vuelva un borde
• Si está de vuelta en su raíz y no tiene un incidente de los bordes no visitados, que se ha hecho.devuelve falso.
• Si en algún momento visita su nodo de destino, usted ha terminado.devuelve verdadero.

  Ahora, si este método devuelve true, este borde causaría un círculo.

Answer 2

Esta no es una respuesta directa a su pregunta por ejemplo (parece que está haciendo un trabajo escolar), pero creo que lo ayudará a comenzar.¿Por qué no crear una estructura de datos que coincida más estrechamente con su modelo mental y acumule desde allí?

class GraphNode { 

    final String name;
    final List<GraphEdge> adjacentNodes;

    public GraphNode(String name) { 
        this.name = name;
        adjacentNodes = new ArrayList<GraphEdge>();
    }

    public void addAdjacency(GraphNode node, int weight) { 
        adjacentNodes.add(new GraphEdge(node, weight));
    }

}

class GraphEdge {

    final GraphNode node;
    final int weight;

    public GraphEdge(GraphEdge node, int weight) {
        this.node = node;
        this.weight = weight;
    }

}