Dalam tutorial ini, Anda akan mempelajari apa itu daftar kedekatan. Juga, Anda akan menemukan contoh kerja daftar kedekatan di C, C ++, Java dan Python.
Daftar kedekatan mewakili grafik sebagai larik daftar tertaut.
Indeks dari array mewakili sebuah simpul dan setiap elemen dalam daftar tertautnya mewakili simpul lain yang membentuk sebuah sisi dengan simpul tersebut.
Representasi Adjacency List
Grafik dan representasi daftar kedekatan yang setara ditampilkan di bawah ini.
Representasi Adjacency List
Daftar kedekatan efisien dalam hal penyimpanan karena kita hanya perlu menyimpan nilai tepinya. Untuk graf renggang dengan jutaan simpul dan tepi, ini berarti banyak ruang yang dihemat.
Struktur Daftar Kedekatan
Daftar ketetanggaan yang paling sederhana membutuhkan struktur data simpul untuk menyimpan simpul dan struktur data grafik untuk mengatur simpul.
Kami tetap dekat dengan definisi dasar grafik - kumpulan simpul dan tepi (V, E). Untuk mempermudah, kami menggunakan grafik yang tidak berlabel sebagai lawan dari grafik yang berlabel yaitu simpul diidentifikasi dengan indeksnya 0,1,2,3.
Mari kita gali struktur data yang berperan di sini.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Jangan biarkan hal itu struct node** adjListsmembanjiri Anda.
Yang kami katakan adalah kami ingin menyimpan pointer ke struct node*. Ini karena kita tidak tahu berapa banyak simpul yang akan dimiliki grafik sehingga kita tidak dapat membuat larik Daftar Berantai pada waktu kompilasi.
Daftar Adjacency C ++
Ini adalah struktur yang sama tetapi dengan menggunakan struktur data STL daftar bawaan dari C ++, kami membuat struktur tersebut sedikit lebih bersih. Kami juga dapat mengabstraksi detail implementasi.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Daftar Adjacency Java
Kami menggunakan Koleksi Java untuk menyimpan Array Daftar Tertaut.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Jenis LinkedList ditentukan oleh data apa yang ingin Anda simpan di dalamnya. Untuk grafik berlabel, Anda dapat menyimpan kamus, bukan Integer
Daftar Adjacency Python
Ada alasan mengapa Python mendapatkan begitu banyak cinta. Kamus sederhana dari simpul dan tepinya adalah representasi yang cukup dari sebuah grafik. Anda dapat membuat simpul itu sendiri serumit yang Anda inginkan.
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')))
Contoh Python, Java dan C / C ++
Python Java 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); )
