Neste tutorial, você aprenderá o que é uma lista de adjacências. Além disso, você encontrará exemplos funcionais de lista de adjacência em C, C ++, Java e Python.
Uma lista de adjacência representa um gráfico como uma matriz de listas vinculadas.
O índice da matriz representa um vértice e cada elemento em sua lista vinculada representa os outros vértices que formam uma aresta com o vértice.
Representação da lista de adjacências
Um gráfico e sua representação de lista de adjacência equivalente são mostrados abaixo.
Representação da lista de adjacências
Uma lista de adjacências é eficiente em termos de armazenamento, pois só precisamos armazenar os valores das arestas. Para um gráfico esparso com milhões de vértices e arestas, isso pode significar muito espaço economizado.
Estrutura da Lista de Adjacência
A lista de adjacência mais simples precisa de uma estrutura de dados de nó para armazenar um vértice e uma estrutura de dados de grafo para organizar os nós.
Ficamos próximos da definição básica de um gráfico - uma coleção de vértices e arestas (V, E). Para simplificar, usamos um gráfico não rotulado em oposição a um rotulado, ou seja, os vértices são identificados por seus índices 0,1,2,3.
Vamos examinar as estruturas de dados em jogo aqui.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Não deixe o struct node** adjListsoprimir você.
Tudo o que estamos dizendo é que queremos armazenar um ponteiro para struct node*. Isso ocorre porque não sabemos quantos vértices o gráfico terá e, portanto, não podemos criar um array de Listas Vinculadas em tempo de compilação.
Lista de Adjacência C ++
É a mesma estrutura, mas usando as estruturas de dados STL de lista embutida do C ++, tornamos a estrutura um pouco mais limpa. Também podemos abstrair os detalhes da implementação.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Usamos coleções Java para armazenar a matriz de listas vinculadas.
class Graph ( private int numVertices; private LinkedList adjLists(); )
O tipo de LinkedList é determinado pelos dados que você deseja armazenar nela. Para um gráfico rotulado, você pode armazenar um dicionário em vez de um inteiro
Lista de Adjacência Python
Há uma razão pela qual Python recebe tanto amor. Um dicionário simples de vértices e suas arestas é uma representação suficiente de um gráfico. Você pode tornar o próprio vértice tão complexo quanto desejar.
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')))
Exemplos de Python, Java e 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); )
