Selles õpetuses saate teada, mis on külgnevuste loend. Samuti leiate toimivaid näiteid külgnevuste loendist C, C ++, Java ja Python.
Külgnevusloend tähistab graafikut lingitud loendite massiivina.
Massiivi indeks tähistab tippu ja iga tema lingitud loendis olev element esindab teisi tippe, mis moodustavad tipuga serva.
Adjacency List esindus
Graafik ja selle ekvivalentne külgnevuste loendi esitus on toodud allpool.
Adjacency List esindus
Kõrvalnimekiri on ladustamise seisukohast tõhus, kuna peame salvestama ainult servade väärtused. Miljonite tippude ja servadega hõreda graafiku jaoks võib see tähendada palju kokkuhoitud ruumi.
Adjacency nimekirja struktuur
Lihtsaim külgnevuste loend vajab tipu salvestamiseks sõlmede andmekonstruktsiooni ja sõlmede korrastamiseks graafiku andmestruktuuri.
Hoiame lähedal graafi põhimääratlusele - tippude ja servade kogumile (V, E). Lihtsuse huvides kasutame sildistamata graafikut erinevalt sildistamata graafi, st tipud identifitseeritakse nende indeksitega 0,1,2,3.
Uurigem siin mängivates andmestruktuurides.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Ära lase end struct node** adjListsüle jõu käia.
Kõik, mida me ütleme, on see, et soovime salvestada kursori struct node*. Selle põhjuseks on asjaolu, et me ei tea, mitu tippu graafil on ja seetõttu ei saa me kompileerimise ajal luua lingitud loendite massiivi.
Piirangute loetelu C ++
See on sama struktuur, kuid kasutades C ++ sisseehitatud loendi STL andmestruktuure, muudame struktuuri natuke puhtamaks. Samuti saame abstraktselt teostuse üksikasjad.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Lingitud loendite massiivi salvestamiseks kasutame Java kollektsioone.
class Graph ( private int numVertices; private LinkedList adjLists(); )
LinkedListi tüüp määratakse selle järgi, milliseid andmeid soovite sinna salvestada. Märgistatud graafiku jaoks võiksite täisarvu asemel salvestada sõnaraamatu
Adjacency List Python
On põhjus, miks Python saab nii palju armastust. Graafi piisav esitus on lihtne tippude ja selle servade sõnastik. Võite teha tipu ise nii keeruliseks kui soovite.
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')))
Pythoni, Java ja C / C ++ näited
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); )
