У цьому підручнику ви дізнаєтесь, що таке список суміжності. Крім того, ви знайдете робочі приклади списку суміжності в C, C ++, Java та Python.
Список суміжності представляє графік як масив пов’язаних списків.
Індекс масиву представляє вершину, і кожен елемент у зв’язаному списку представляє інші вершини, які утворюють ребро з вершиною.
Представлення списку суміжності
Графік та його еквівалентне представлення списку суміжності наведені нижче.
Представлення списку суміжності
Список суміжностей є ефективним з точки зору зберігання, оскільки нам потрібно зберігати лише значення для країв. Для розрідженого графіка з мільйонами вершин і ребер це може означати багато заощадженого місця.
Структура списку суміжності
Найпростіший список суміжностей потребує структури даних вузла для зберігання вершини та структури даних графіка для організації вузлів.
Ми залишаємось поруч з основним визначенням графіка - сукупністю вершин і ребер (V, E). Для простоти ми використовуємо немічений графік на відміну від міченого, тобто вершини ідентифікуються за їх індексами 0,1,2,3.
Давайте заглибимося в структуру даних, яка тут грає.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Не дозволяйте struct node** adjListsперевантажити вас.
Все, що ми говоримо, це те, що ми хочемо зберегти вказівник struct node*. Це тому, що ми не знаємо, скільки вершин буде мати графік, і тому ми не можемо створити масив пов’язаних списків під час компіляції.
Список суміжності C ++
Це та сама структура, але, використовуючи вбудований список даних даних STL на C ++, ми робимо структуру трохи чистішою. Ми також можемо абстрагувати деталі реалізації.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Список суміжності Java
Ми використовуємо колекції Java для зберігання масиву зв’язаних списків.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Тип LinkedList визначається тим, які дані ви хочете в ньому зберігати. Для позначеного графіка ви можете зберігати словник замість цілого числа
Список суміжності Python
Є причина, чому Пітон отримує стільки любові. Простий словник вершин та його ребер є достатнім поданням графа. Ви можете зробити саму вершину настільки складною, на скільки хочете.
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 та 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); )
