V tej vadnici boste izvedeli, kaj je seznam sosednosti. Prav tako boste našli delovne primere seznama sosednosti v C, C ++, Java in Python.
Seznam sosednosti predstavlja graf kot niz povezanih seznamov.
Indeks matrike predstavlja oglišče in vsak element na povezanem seznamu predstavlja druge oglišča, ki tvorijo rob z ogliščem.
Predstavitev seznama sosedstva
Graf in njegova enakovredna predstavitev seznama sosednosti sta prikazana spodaj.
Predstavitev seznama sosedstva
Seznam sosednosti je učinkovit v smislu shranjevanja, ker moramo shraniti le vrednosti za robove. Za redek graf z milijoni točk in robovi lahko to pomeni veliko prihranjenega prostora.
Struktura seznama sosednosti
Najpreprostejši seznam sosednosti potrebuje podatkovno strukturo vozlišča za shranjevanje oglišča in podatkovno strukturo grafa za organizacijo vozlišč.
Ostajamo blizu osnovne definicije grafa - zbirke točk in robov (V, E). Za poenostavitev uporabljamo neoznačen graf v nasprotju z označenim, tj. Točke se identificirajo s svojimi indeksi 0,1,2,3.
Poglejmo v podatkovne strukture, ki se igrajo tukaj.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Ne dovolite, da struct node** adjListsvas prevzame.
Vse kar pravimo je, da želimo shraniti kazalec struct node*. To je zato, ker ne vemo, koliko točk bo imel graf, zato v času prevajanja ne moremo ustvariti polja povezanih seznamov.
Seznam sosednosti C ++
Gre za isto strukturo, vendar z uporabo vgrajenega seznama podatkovnih struktur STL v C ++ naredimo strukturo nekoliko čistejšo. Podrobnosti izvedbe smo lahko tudi abstraktni.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Zbirke Java uporabljamo za shranjevanje niza povezanih seznamov.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Tip povezanega seznama je odvisen od tega, katere podatke želite shraniti vanj. Za označeni graf lahko shranite slovar namesto Integer
Seznam sosednosti Python
Obstaja razlog, da Python dobi toliko ljubezni. Preprost slovar vrhov in njegovih robov je zadosten prikaz grafa. Sam vrh lahko naredite tako zapleten, kot želite.
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')))
Primeri Python, Java in 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); )
