Red de conocimiento informático - Aprendizaje de código fuente - Estructura de datos: implementación de lista de adyacencia del gráfico

Estructura de datos: implementación de lista de adyacencia del gráfico

A veces no puedo comerme a un gordo de un bocado, ¿verdad? Lo mismo ocurre con la programación. Si dejas que otros te ayuden, nunca podrás mejorar. De hecho, si quieres escribir el problema que planteas, primero debes tener algunos conceptos básicos. Sólo cuando estemos muy familiarizados con los conceptos básicos podremos escribir un programa que sea verdaderamente nuestro y que nuestra programación sea cómoda. En primer lugar, necesitamos saber qué es una lista de adyacencia. En pocas palabras, una lista de adyacencia es una matriz especial. Cada elemento no vacío de la matriz representa un nodo del gráfico y almacena una lista vinculada (si). Si no sabe qué es una lista vinculada, eche un vistazo al encabezado de "Estructura de datos" publicado por Yan Weimin de la Universidad de Tsinghua. Esta lista vinculada es una colección de todos los nodos conectados a este nodo. Si aún no está claro, mire la imagen a continuación

La matriz de la izquierda es una lista de todos los puntos fijos y hay 6 listas vinculadas a la derecha

Para Por ejemplo, el nodo A está conectado a los nodos B y E. Entonces, la primera lista vinculada almacena los nodos B y E respectivamente (tenga en cuenta que los nodos B y E aquí no están marcados directamente con letras en la lista de adyacencia, sino que están representados por los subíndices de los arreglos donde se ubican los nodos B y E, por lo que son 1 nodo respectivamente y 4 nodos, lo que facilita la programación)

Bien, si entiendes qué es una lista de adyacencia, entonces ya estás a mitad de camino. éxito. Debe modificar esta lista de adyacencia abstracta para operaciones de gráficos. En segundo lugar, debemos comprender el funcionamiento de estructuras de datos como listas vinculadas y los conceptos básicos anteriores de operaciones gráficas (puede leer la versión de Yan Weimin de "Estructura de datos" si queremos explicarlos claramente, puede que nos lleve hasta el amanecer). al día siguiente. Perdóneme por no poder explicarlos uno por uno aquí, pero los programas básicos que necesita tienen códigos fuente en el libro de Yan Weimin (se recomienda no leer los códigos fuente de otras personas, será muy doloroso leer los de otras personas). pero es muy fácil escribir el tuyo propio) de). Si no está familiarizado con el funcionamiento de las listas vinculadas (principalmente punteros), primero aprenda a programar listas vinculadas. Las listas vinculadas son mucho más simples que las listas de adyacencia. Puede comenzar de manera simple y luego volverse más compleja. en el proceso de programación.

Espero que esta experiencia mía te pueda servir de algo.