Šioje pamokoje sužinosite, kas yra gretimybių sąrašas. Taip pat rasite veikiančių gretimybių sąrašo pavyzdžių C, C ++, Java ir Python.
Gretimybių sąrašas rodo grafiką kaip susietų sąrašų masyvą.
Masyvo indeksas žymi viršūnę, o kiekvienas jo susieto sąrašo elementas žymi kitas viršūnes, kurios sudaro viršūnės kraštą.
Adjacency sąrašo atstovavimas
Grafikas ir jo atitikmuo gretimybių sąraše pateikiami žemiau.
Adjacency sąrašo atstovavimas
Gretimybių sąrašas yra efektyvus saugojimo požiūriu, nes mums reikia saugoti tik kraštų vertes. Retam grafikui su milijonais viršūnių ir kraštų tai gali reikšti daug sutaupytos vietos.
Adjacency sąrašo struktūra
Paprasčiausiam gretimybių sąrašui reikia mazgo duomenų struktūros, kad būtų galima laikyti viršūnę, ir diagramos duomenų struktūros, kad sutvarkytų mazgus.
Laikomės arti pagrindinio grafiko apibrėžimo - viršūnių ir briaunų rinkinio (V, E). Kad būtų paprasčiau, mes naudojame nežymėtą grafiką, o ne pažymėtą, ty viršūnės identifikuojamos pagal jų indeksus 0,1,2,3.
Panagrinėkime čia žaidžiamas duomenų struktūras.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Neleisk jūsų struct node** adjListsužgožti.
Viskas, ką sakome, yra tai, kad norime išsaugoti rodyklę struct node*. Taip yra todėl, kad mes nežinome, kiek viršūnių turės grafikas, todėl kompiliavimo metu negalime sukurti susietų sąrašų masyvo.
Papildomas sąrašas C ++
Tai yra ta pati struktūra, tačiau naudodami C ++ integruotas sąrašo STL duomenų struktūras, mes padarome struktūrą šiek tiek švaresnę. Mes taip pat galime abstrahuoti įgyvendinimo detales.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Mes naudojame „Java“ kolekcijas susietų sąrašų masyvui saugoti.
class Graph ( private int numVertices; private LinkedList adjLists(); )
„LinkedList“ tipą lemia tai, kokius duomenis norite jame laikyti. Norėdami pažymėti grafiką, vietoj sveikojo skaičiaus galite laikyti žodyną
„Adjacency List Python“
Yra priežastis, kodėl „Python“ gauna tiek daug meilės. Paprastas viršūnių ir jo kraštų žodynas yra pakankamas grafiko atvaizdavimas. Pačią viršūnę galite padaryti tokią sudėtingą, kiek norite.
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“ ir „C / C ++“ pavyzdžiai
„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); )
