Hatasız bir grafikte bağlanan bileşenlerin sayısı

Question

Bazı grafik algoritmalarına gidiyorum (bu ev ödevi değil; sadece algoritmalara ve veri yapılarına tarama yapıyorum) ve bir sorum var.

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

grafik kabaca şöyledir:

kaç bağlı bileşenler bu grafikte I aşağıdaki yönsüz grafiği var varsayalım? Sadece grafiğe bakarak, 3 bileşen var gibi görünüyor. Ancak, algoritmayı gerçekte uygularsam (her bir köşe noktası üzerinde yineleme yapar ve bu köşeyi başlangıç ​​noktasını kullanarak bir bfs yaparsanız, o köşe noktası keşfedilmez. Ayrıca, bfs, keşfedildiği gibi karşılaştığı herhangi bir köşe noktasını işaretler).

9 ile başlıyorum, aşağıdaki düğümleri keşfederek sona erer: [19, 26, 11, 18]. Ancak, 13, 19'un bitişik listesinde bulunmadığından keşfedilmemiştir. Ancak, 19, 13'un bitişik listesinde yer almaktadır. Bu yüzden fazladan bir bileşenle sonuçlanıyorum.

Bu doğru mu? Aslında 4 ayrı bileşen var mı ve eğer öyleyse, bağlı-bileşen anlayışım yanlış mı?

Answer 1

sorun yönsüz grafikler komşuluk listesi temsilleri, yeni bir kenar ab koyarak olduğunda ya da

(1) simetrik bitişiklik listeleri kullanmak, yani adjlist[a]ve için b eklemek zorunda olmasıdır tersi

veya

(2) tüm köşe bitişiklik listeleri bir kenar varlığı için ideal e everytim hareket.

(2) korkunç derecede verimsiz olduğundan, genellikle (1) ile gidersiniz. Bu aynı zamanda genel olarak kullanılan yardımcı listeler için bir sözleşmedir. Eğer kendi listenizle sunulsaydı, grafiğin yönlendirildiğini varsayardım.

Answer 2

Bitiş listesi listenizi değiştirebilirsiniz, temsiliniz 'yönlendirilir' ancak resminiz doğru değildir. Kenar (a, b) grafiği için {a: [b], b: [a]}