Dalam tutorial ini, anda akan mengetahui apa itu senarai yang berdekatan. Anda juga akan mendapat contoh senarai keberanian di C, C ++, Java dan Python.
Senarai adjacency mewakili grafik sebagai susunan senarai terpaut.
Indeks array mewakili bucu dan setiap elemen dalam senarai terpautnya mewakili bucu lain yang membentuk pinggir dengan bucu.
Perwakilan Senarai Adjacency
Grafik dan perwakilan senarai jarak yang setara ditunjukkan di bawah.
Perwakilan Senarai Adjacency
Senarai adjacency adalah cekap dari segi penyimpanan kerana kita hanya perlu menyimpan nilai untuk tepi. Untuk grafik yang jarang dengan berjuta-juta bucu dan tepi, ini boleh bermakna banyak ruang yang dijimatkan.
Struktur Senarai Kecukupan
Senarai adjacency paling mudah memerlukan struktur data nod untuk menyimpan bucu dan struktur data grafik untuk mengatur nod.
Kami tetap dekat dengan definisi asas grafik - koleksi bucu dan tepi (V, E). Untuk kesederhanaan, kami menggunakan graf yang tidak berlabel berbanding dengan yang berlabel iaitu bucu yang dikenal pasti oleh indeksnya 0,1,2,3.
Mari kita menggali struktur data yang dimainkan di sini.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Jangan biarkan struct node** adjListskewalahan anda.
Yang kami katakan ialah kami ingin menyimpan penunjuk struct node*. Ini kerana kita tidak tahu berapa simpul grafik yang akan dimiliki dan oleh itu kita tidak dapat membuat susunan Daftar Terpaut pada waktu kompilasi.
Senarai Adjacency C ++
Ia adalah struktur yang sama tetapi dengan menggunakan struktur data STL senarai terbina dalam C ++, kami menjadikan strukturnya sedikit lebih bersih. Kami juga dapat mengaburkan perincian pelaksanaannya.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Senarai Adjacency Java
Kami menggunakan Koleksi Java untuk menyimpan Array of Linked Lists.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Jenis LinkedList ditentukan oleh data apa yang ingin anda simpan di dalamnya. Untuk grafik berlabel, anda boleh menyimpan kamus dan bukannya Integer
Senarai Adjacency Python
Ada sebab Python mendapat banyak cinta. Kamus simpul ringkas dan pinggirnya adalah gambaran grafik yang mencukupi. Anda boleh menjadikan bucu itu sendiri kompleks seperti yang anda mahukan.
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 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); )
