Pregunta Cantidad de componentes conectados en un gráfico no dirigido


Estoy repasando algunos algoritmos gráficos (esto no es tarea Solo estoy actualizando algoritmos y estructuras de datos) y tengo una pregunta. Supongamos que tengo el siguiente gráfico no dirigido:

var graph = {
    9: [19, 26],
    13: [19, 5],
    17: [],
    26: [11, 18],
    18: [9],
    19: [],
    23: [24],
    24: [],
    11: [],
    18: []
};

El gráfico básicamente se ve así:

enter image description here

¿Cuántos componentes conectados hay en este gráfico? Solo mirando el gráfico, parece que hay 3 componentes. Pero si realmente implemento el algoritmo (iterando sobre cada vértice, y haciendo un bfs usando ese vértice como punto de partida Si ese vértice no está descubierto. Además, el bfs marcará cualquier vértice que encuentre, como se descubrió).

Si comienzo con 9, Termino descubriendo los siguientes nodos: [19, 26, 11, 18]. Sin embargo, 13 No se descubre porque no está en. 19Lista de adyacencias. Sin embargo, 19 es en 13lista de adyacencia. Es por esto que termino con un componente extra.

¿Es esto correcto? ¿Hay realmente 4 componentes separados y, de ser así, mi comprensión de los componentes conectados es incorrecta?


5
2018-04-07 01:42


origen


Respuestas:


El problema es que para las representaciones de la lista de adyacencia de no dirigido gráficos, tienes que o bien

(1) use listas de adyacencia simétrica, es decir, al poner en un nuevo borde ab, agregar b a adjlist[a]  y viceversa

o

(2) recorra todas las listas de adyacencias de vértices cada vez que busque la existencia de un borde.

Dado que (2) es terriblemente ineficiente, generalmente irías con (1). Esta es también la convención para las listas adj utilizadas en general. Si me presentaran su lista adjunta, asumiría que el gráfico fue dirigido.


4
2018-04-07 01:45



Puede cambiar la representación de su lista de adyacencia, su representación está 'dirigida' pero su imagen no está dirigida. Para el borde (a, b) gráfico {a: [b], b: [a]}


3
2018-04-07 01:46