Dans ce didacticiel, vous apprendrez ce qu'est une liste de contiguïté. Vous trouverez également des exemples fonctionnels de liste de contiguïté en C, C ++, Java et Python.
Une liste de contiguïté représente un graphique sous la forme d'un tableau de listes liées.
L'index du tableau représente un sommet et chaque élément de sa liste chaînée représente les autres sommets qui forment une arête avec le sommet.
Représentation de la liste d'adjacence
Un graphique et sa représentation de liste de contiguïté équivalente sont présentés ci-dessous.
Représentation de la liste d'adjacence
Une liste de contiguïté est efficace en termes de stockage car il suffit de stocker les valeurs des arêtes. Pour un graphique clairsemé avec des millions de sommets et d'arêtes, cela peut signifier beaucoup d'espace économisé.
Structure de la liste de contiguïté
La liste de contiguïté la plus simple nécessite une structure de données de nœuds pour stocker un sommet et une structure de données de graphe pour organiser les nœuds.
Nous restons proches de la définition de base d'un graphe - une collection de sommets et d'arêtes (V, E). Pour simplifier, nous utilisons un graphe non étiqueté par opposition à un graphe étiqueté c'est-à-dire que les sommets sont identifiés par leurs indices 0,1,2,3.
Explorons les structures de données en jeu ici.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Ne vous laissez pas struct node** adjListssubmerger.
Tout ce que nous disons, c'est que nous voulons stocker un pointeur struct node*. C'est parce que nous ne savons pas combien de sommets le graphique aura et que nous ne pouvons donc pas créer un tableau de listes liées au moment de la compilation.
Liste d'adjacence C ++
C'est la même structure mais en utilisant les structures de données STL de liste intégrées de C ++, nous rendons la structure un peu plus propre. Nous sommes également en mesure d'abstraire les détails de l'implémentation.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Liste d'adjacence Java
Nous utilisons des collections Java pour stocker le tableau de listes liées.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Le type de LinkedList est déterminé par les données que vous souhaitez y stocker. Pour un graphique étiqueté, vous pouvez stocker un dictionnaire au lieu d'un entier
Liste d'adjacence Python
Il y a une raison pour laquelle Python reçoit tant d'amour. Un simple dictionnaire de sommets et de ses arêtes est une représentation suffisante d'un graphe. Vous pouvez rendre le sommet lui-même aussi complexe que vous le souhaitez.
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')))
Exemples Python, Java et 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); )
