Listas de adyacencia PDF

Preview

Summary

Download Listas de adyacencia PDF

Description

Universidad Aztlán

Investigación: Listas de adyacencia

Alumno: Ricardo Aban Tamayo

Carrera: Ing. En sistemas computacionales

Grado: Tercer cuatrimestre

Materia: Estructura de datos

Catedrático: M. en C. Manuel de la Rosa López

Fecha: 31 de julio del 2020

Lugar: Playa del Carmen, Q. Roo.

I

Introducción Como ya hemos visto en temas anteriores las estructuras de datos dinámicas se dividen en dos grandes grupos, lineales y no lineales según la forma en la cual se ordenan sus elementos. Dentro de las estructuras de datos no lineales se encuentran los árboles y los grafos los cuales nos permitan resolver problemas informáticos de gran complejidad. En la representación de grafos existen dos métodos; la matriz de adyacencia y las listas de adyacencia, esta última es en la que nos centraremos, veremos la forma en la que se representa y los beneficios que se tiene al manejar este método. La lista de adyacencia tiene muchas aplicaciones en la vida diaria, trataremos de comprender su estructura para poder realizar problemas complejos dentro del mundo de la programación. Un ejemplo de utilizar grafos son las relaciones entre entidades, donde se representan usando una red. Supongamos que queremos representar los intereses y relaciones entre personas. Una persona puede ser amigo de otra, extender su círculo social a los amigos de sus amigos, o eventualmente terminar una amistad.

II

GRAFOS Los grafos son otra estructura de datos no lineal y que tiene gran número de aplicaciones. El estudio del análisis de grafos ha interesado a los matemáticos durante siglos y representa una parte importante de la teoría combinatoria en matemáticas. Aunque la teoría de grafos es compleja y amplia, en esta sección se realizará una introducción a la teoría de grafos y a los algoritmos que permiten su solución por computadora. Los árboles binarios representan estructuras jerárquicas con limitaciones de dos subárboles por cada nodo. Si se eliminan las restricciones de que cada nodo puede apuntar a dos nodos —como máximo— y que cada nodo puede estar apuntado por otro nodo —como máximo— nos encontramos con un grafo. Ejemplos de grafos en la vida real los tenemos en la red de carreteras de un estado o región, la red de enlaces ferroviarios o aéreos nacionales, etc. En una red de carreteras los nudos de la red representan los vértices del grafo y las carreteras de unión de dos ciudades los arcos, de modo que a cada arco se asocia una información tal como la distancia, el consumo en gasolina por automóvil, etc. Los grafos nos pueden ayudar a resolver problemas como éste. Supóngase que ciertas carreteras del norte del Estado han sido bloqueadas por una reciente tormenta de nieve. ¿Cómo se puede saber si todas las ciudades de ese Estado se pueden alcanzar por carretera desde la capital o si existen ciudades aisladas? Evidentemente existe la solución del estudio de un mapa de carreteras; sin embargo, si existen muchas ciudades, la obtención de la solución puede ser ardua y costosa en tiempo. Una computadora y un algoritmo adecuado de grafos solucionarán fácilmente el problema.

III

Representación de grafos Existen dos técnicas estándar para representar un grafo G: la matriz de adyacencia (mediante arrays) y la lista de adyacencia (mediante punteros/listas enlazadas).

Lista de adyacencia Otra forma de representar un grafo es por medio de listas enlazadas. Usualmente conocido como lista de adyacencia el TDA grafo consiste en una lista simple donde cada nodo contiene a un vértice Vi y una referencia a otra lista cuyos nodos representan los arcos conectan Vi son sus vértices adyacentes. En comparación con la matriz de adyacencia esta nueva representación es más compleja pues requiere definir un TDA para cada tipo de nodo y la búsqueda de arcos toma más tiempo. Sin embargo, la lista de adyacencia tiene la ventaja de permitir usar grafos con un número indeterminado de vértices El segundo método utilizado para representar grafos es útil cuando un grafo tiene muchos vértices y pocas aristas; es la lista de adyacencia. En esta representación se utiliza una lista enlazada por cada vértice v del grafo que tenga vértices adyacentes desde él. El grafo completo incluye dos partes: un directorio y un conjunto de listas enlazadas. Hay una entrada en el directorio por cada nodo del grafo. La entrada en el directorio del nodo i apunta a una lista enlazada que representa los nodos que son conectados al nodo i. Cada registro de la lista enlazada tiene dos campos: uno es un identificador de nodo, otro es un enlace al siguiente elemento de la lista; la lista enlazada representa arcos.

IV

Un grafo no dirigido de orden N con A arcos requiere N entradas en el directorio y 2*A entradas de listas enlazadas, excepto si existen bucles que reducen el número de listas enlazadas en 1. Un grafo dirigido de orden N con A arcos requiere N entradas en el directorio y A entradas de listas enlazadas.

V

La elección de la representación depende del algoritmo particular que se vaya a implementar y si el grafo es “disperso” o “denso”. Un grafo disperso es uno en el que el número de vértices N es mucho mayor que el número de arcos. En un grafo denso el número de arcos se acerca al máximo.

VI

Cibergrafía https://libgen.is/book/index.php?md5=ABA8FC2F2E23E23E3010F515B563ADD9 (fundamentos de programación, recuperado el 8 de julio de 2020, 17:34).

VII...