Şu anda programlama teknik bir görüşme için hazırlanıyor Steve Yegge tavsiyesi takip ediyorum: http://steve-yegge.blogspot.com/2008/03/get-that-job-at-google.html

Grafikler üzerinde, kendi bölümünde, şöyle diyor:

Üç temel yolu vardır bellekte bir grafik gösterir (nesneler ve işaretçileri, matrix, ve bitişiklik listesi), ve tanımak gerekir her gösterimi ile kendiniz ve artıları ve eksileri.

Artıları ve eksileri matris ve bitişiklik listesi sunumlarını CLRS olarak açıklanmıştır, ama bir nesne temsili için bu karşılaştıran bir kaynak bulmak mümkün olmamıştır.

Sen sadece düşünerek, bu kendimi biraz düşünebilirim, ama önemli bir şey kaçırmadım emin olmak istiyorum. Eğer birisi bu kapsamlı bir şekilde açıklamak, ya da öyle bir kaynak bana gelin varsa, çok minnettar olurum.

nesneleri ve işaretçiler

Bu hammar kenar ve köşeler gibi sınıfları ile bu temsil edeceğini Java Diğer cevap, dediğin gibi sadece temel datastructures. Örneğin bir kenar iki tepe noktaları birbirine bağlar ve her iki yönlendirilmiş veya yönlendirilmemiş olabilir ve kilo içerebilir. Bir tepe noktası NUMARASI, isim vb olabilir. Çoğunlukla her ikisi de ek özellikleri var. Onlarla grafikteki gibi inşa edebilirsiniz

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30  

Bu yaklaşım genellikle daha okunaklı ve nesne odaklı kullanıcılar;) için uygun olduğundan nesne tabanlı uygulamalar için kullanılır.

matrix

Bir matris sadece 2 boyutlu basit bir dizidir. Bu gibi int bir dizi olarak temsil edilebilir köşe KİMLİK varsayarsak:

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

Bu dizin erişim gerekli olduğu yoğun grafikler için yaygın olarak kullanılır. Bu BM/yönetmen ağırlıklı bir yapı gösterebilir.

bitişiklik listesi

Bu sadece basit datastructure bir karışımı, genellikle bu HashMap<Vertex, List<Vertex>> kullanarak uygulamak. Benzer Guava HashMultimap olabilir.

Bu yaklaşım, (1) (itfa edilmiş) köşe arama O var çünkü serin ve talep ettim bu özel köşe için bana tüm komşu noktaların bir listesini verir.

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

Bu seyrek grafikler temsil etmek için kullanılır, eğer Google'da başvuru yapıyorsanız, webgraph seyrek olduğunu bilmeli. Users bir şekilde BigTable kullanarak onlarla başa çıkabilirim.

Oh ve BTW, here fantezi resimler;) bu yazı çok güzel bir özet