Bu eğitimde, bitişiklik listesinin ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da bitişiklik listesinin çalışan örneklerini bulacaksınız.
Bitişiklik listesi, bağlantılı listeler dizisi olarak bir grafiği temsil eder.
Dizinin indeksi bir tepe noktasını temsil eder ve bağlantılı listesindeki her öğe, tepe ile bir kenar oluşturan diğer tepe noktalarını temsil eder.
Komşuluk Listesi gösterimi
Bir grafik ve eşdeğer komşu liste temsili aşağıda gösterilmiştir.
Komşuluk Listesi gösterimi
Bir bitişiklik listesi depolama açısından etkilidir çünkü sadece kenarların değerlerini saklamamız gerekir. Milyonlarca köşesi ve kenarı olan seyrek bir grafik için bu, çok fazla alan tasarrufu anlamına gelebilir.
Komşuluk Listesi Yapısı
En basit bitişiklik listesi, bir tepe noktasını saklamak için bir düğüm veri yapısına ve düğümleri düzenlemek için bir grafik veri yapısına ihtiyaç duyar.
Bir grafiğin temel tanımına yakın duruyoruz - köşeler ve kenarların bir toplamı (V, E). Basit olması için, etiketli bir grafiğin aksine etiketlenmemiş bir grafik kullanıyoruz, yani köşeler endeksleri 0,1,2,3 ile tanımlanıyor.
Burada oyundaki veri yapılarını inceleyelim.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
struct node** adjListsSeni ezmesine izin verme .
Tek söylediğimiz, bir işaretçi saklamak istediğimiz struct node*. Bunun nedeni, grafiğin kaç köşeye sahip olacağını bilmememiz ve bu nedenle derleme zamanında Bağlantılı Listeler dizisi oluşturamayız.
Komşuluk Listesi C ++
Aynı yapıdır ancak C ++ 'ın yerleşik liste STL veri yapılarını kullanarak yapıyı biraz daha temiz hale getiriyoruz. Ayrıca uygulamanın detaylarını da soyutlayabiliriz.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Bitişiklik Listesi Java
Bağlantılı Listeler Dizisini depolamak için Java Koleksiyonları kullanıyoruz.
class Graph ( private int numVertices; private LinkedList adjLists(); )
LinkedList türü, içinde saklamak istediğiniz verilere göre belirlenir. Etiketli bir grafik için Tamsayı yerine bir sözlük saklayabilirsiniz.
Bitişiklik Listesi Python
Python'un bu kadar çok sevilmesinin bir nedeni var. Basit bir köşeler sözlüğü ve kenarları, bir grafiğin yeterli bir temsilidir. Köşeyi istediğiniz kadar karmaşık hale getirebilirsiniz.
graph = ('A': set(('B', 'C')), 'B': set(('A', 'D', 'E')), 'C': set(('A', 'F')), 'D': set(('B')), 'E': set(('B', 'F')), 'F': set(('C', 'E')))
Python, Java ve C / C ++ Örnekleri
Python Java C C ++ # Adjascency List representation in Python class AdjNode: def __init__(self, value): self.vertex = value self.next = None class Graph: def __init__(self, num): self.V = num self.graph = (None) * self.V # Add edges def add_edge(self, s, d): node = AdjNode(d) node.next = self.graph(s) self.graph(s) = node node = AdjNode(s) node.next = self.graph(d) self.graph(d) = node # Print the graph def print_agraph(self): for i in range(self.V): print("Vertex " + str(i) + ":", end="") temp = self.graph(i) while temp: print(" -> ()".format(temp.vertex), end="") temp = temp.next print(" ") if __name__ == "__main__": V = 5 # Create graph and edges graph = Graph(V) graph.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(0, 3) graph.add_edge(1, 2) graph.print_agraph()
// Adjascency List representation in Java import java.util.*; class Graph ( // Add edge static void addEdge(ArrayList am, int s, int d) ( am.get(s).add(d); am.get(d).add(s); ) public static void main(String() args) ( // Create the graph int V = 5; ArrayList am = new ArrayList (V); for (int i = 0; i < V; i++) am.add(new ArrayList()); // Add edges addEdge(am, 0, 1); addEdge(am, 0, 2); addEdge(am, 0, 3); addEdge(am, 1, 2); printGraph(am); ) // Print the graph static void printGraph(ArrayList am) ( for (int i = 0; i < am.size(); i++) ( System.out.println("Vertex " + i + ":"); for (int j = 0; j " + am.get(i).get(j)); ) System.out.println(); ) ) )
// Adjascency List representation in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int); struct Graph ( int numVertices; struct node** adjLists; ); // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create a graph struct Graph* createAGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); int i; for (i = 0; i adjLists(i) = NULL; return graph; ) // Add edge void addEdge(struct Graph* graph, int s, int d) ( // Add edge from s to d struct node* newNode = createNode(d); newNode->next = graph->adjLists(s); graph->adjLists(s) = newNode; // Add edge from d to s newNode = createNode(s); newNode->next = graph->adjLists(d); graph->adjLists(d) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Vertex %d: ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createAGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 0, 3); addEdge(graph, 1, 2); printGraph(graph); return 0; )
// Adjascency List representation in C++ #include using namespace std; // Add edge void addEdge(vector adj(), int s, int d) ( adj(s).push_back(d); adj(d).push_back(s); ) // Print the graph void printGraph(vector adj(), int V) ( for (int d = 0; d < V; ++d) ( cout << " Vertex " << d << ":"; for (auto x : adj(d)) cout < " << x; printf(""); ) ) int main() ( int V = 5; // Create a graph vector adj(V); // Add edges addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 2); printGraph(adj, V); )
