În acest tutorial, veți afla ce este o listă de adiacențe. De asemenea, veți găsi exemple de lucru ale listei de adiacențe în C, C ++, Java și Python.
O listă de adiacență reprezintă un grafic ca o serie de liste legate.
Indexul matricei reprezintă un vârf și fiecare element din lista sa legată reprezintă celelalte vârfuri care formează o margine cu vârful.
Reprezentarea Listei de adiacență
Un grafic și reprezentarea echivalentă a listei sale de adiacență sunt prezentate mai jos.
Reprezentarea Listei de adiacență
O listă de adiacență este eficientă în ceea ce privește stocarea, deoarece trebuie să stocăm doar valorile pentru margini. Pentru un grafic rar cu milioane de vârfuri și margini, acest lucru poate însemna mult spațiu salvat.
Structura listei de adiacență
Cea mai simplă listă de adiacență are nevoie de o structură de date nod pentru a stoca un vârf și o structură de date grafice pentru a organiza nodurile.
Rămânem aproape de definiția de bază a unui grafic - o colecție de vârfuri și muchii (V, E). Pentru simplitate, folosim un grafic neetichetat spre deosebire de unul etichetat, adică vârfurile sunt identificate prin indicii lor 0,1,2,3.
Să săpăm în structurile de date în joc aici.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Nu te lăsa să struct node** adjListste copleșească.
Tot ce spunem este că vrem să stocăm un pointer struct node*. Acest lucru se datorează faptului că nu știm câte vârfuri va avea graficul și, prin urmare, nu putem crea o matrice de liste legate în timpul compilării.
Adjacency List C ++
Este aceeași structură, dar folosind lista încorporată a structurilor de date STL ale C ++, facem structura puțin mai curată. De asemenea, suntem capabili să abstractizăm detaliile implementării.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Folosim colecțiile Java pentru a stoca matricea listelor conectate.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Tipul de LinkedList este determinat de datele pe care doriți să le stocați în el. Pentru un grafic etichetat, puteți stoca un dicționar în loc de un întreg
Lista de adiacență Python
Există un motiv pentru care Python primește atât de multă dragoste. Un dicționar simplu de vârfuri și margini este o reprezentare suficientă a unui grafic. Puteți face vertexul în sine la fel de complex pe cât doriți.
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')))
Exemple Python, Java și 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); )
