Estructuras De Grafos En Java. 1b355t

Universidad Piloto de Colombia. Agudelo. Grafos

1

ESTRUCTURAS DE DATOS - GRAFOS Agudelo M., Oscar Ivan. [email protected] Universidad Piloto de Colombia 

Resumen— En este Artículo hablaremos de la Estructura de Datos denominada Grafos, la cual se diferencia de los arboles porque los nodos (vértices) se pueden relacionar con conexiones (Arcos o Aristas) de más de dos elementos. Los grafos pueden ser utilizados como modelos abstractos para resolver problemas o representación de estructuras reales tales como rutas, redes, sistemas, circuitos, enlaces, etc. Encontramos Grafos dirigidos y no dirigidos. En conclusión una estructura de grafos sería un conjunto de nodos o vértices unidos por un conjunto de conexiones relacionales. Índice de Términos— Adyacentes: Cuando dos vértices están unidos por un arco.

Árbol: Respecto a los Grafos es un Grafo sin ciclos. Bucle: Arista donde el vértice del principio y del final son el mismo.

Camino: El recorrido entre los vértices para que dos vértices sea adyacentes. Camino Simple: Cuando en el recorrido no se repiten vértices. Ciclo: un camino donde su principio y fin es el mismo vértice. Conectado: Es cuando existe un camino que une cualquiera de dos vértices Desconectado: Cuando no existe camino que una dos vértices cualquiera. Grafo Acíclico: Es un Grafo dirigido que no tiene ciclos. Grafo Denso: un grafo con una gran cantidad de vértices. Grafos Dirigidos: (Dígrafos) Cada arista está dirigida a un vértice, por tanto un vértice X seria Adyacente de Y pero Y no sería adyacente de X (en su representación gráfica se simboliza con una flecha). Grafos No Dirigidos: Cada arista no está dirigida a los vértices (en su representación gráfica se simboliza con una línea simple). Orden del Grafo: Es el número de vértices del Grafo. 

I.INTRODUCCIÓN El grafo es una Estructura no Lineal utilizada en os lenguajes de programación y desarrollo de software para la solución de problemas estructurales no lineales con cierta estructura relaciona compleja pero simplificada a un proceso de abstracción del problema en una estructura relaciona y dirigida entre varios datos. Al empezar a estudiar sobre los grafos la idea que más asociada a ellos sería la de un mapa conceptual o mapa mental para entender la atracción simplificada de los conceptos y sus relaciones. II. CONCEPTO DE GRAFOS. La Estructura de Datos no lineal de Grafos está basado precisamente en la Teoría de Grafos estudiado y desarrollado por Euler para solucionar el problema de los puentes de Königsberg el cual consistía en buscar una manera de recorrer los sietes puentes del rio Pregel, en una solo vez y volviendo al punto de inicio. Euler desarrollo un concepto generalizando los elementos y simplificando lo mejor posible la estructura del problema que desarrollaba con círculos enlazados con esa línea de enlace eran los puentes. Por el eso el ciclo que contiene todas las aristas del grafo se llama ahora ciclo de Euler porque Euler resolvió ese primer problema con que fundó la teoría de grafos, hay que anotar que el termino grafo vine de la notación grafica utilizada para la representación utilizada para los enlaces de los átomos en las moléculas. Al final resultó que el grafo del problema tenia nodos de grado impar y por eso no existía un ciclo para los puentes de Königsburg.

Universidad Piloto de Colombia. Agudelo. Grafos

2

caso donde tenemos un Grafo denso de entonces hacemos pares relacionados con una lógica de cierto y falso (booleano). Entonces sería una matriz de n elementos en donde el caso cierta seria cuando existiera un relación de adyacencia y falso en cuanto los dos vértices no la tuvieran.

En la aplicación el Grafo está definido como un conjunto denominado como G, el cual está compuesto por un conjunto de Vértices V (vertex) y un conjunto Aristas E (edge). Cada arista es un par (a,b), siendo a y b un par de vértices pertenecientes al conjunto de Vértices. Cuando este par de nodos están ordenados está representando un Grafo dirigido. A. Relaciones Tenemos la relación de incidencia, por ejemplo en un Dígrafo desde el vértice que sale la arista dirigida se dice que este vértice incide desde e incide en al vértice donde llega la dirección de la arista. En un grafo no dirigido se dice que incide sobre los dos vértices unidos por la arista desde el uno al otro en cualquier sentido.

La relación adyacente es de un solo sentido en un dígrafo decimos que un vértice a es adyacente a un vértice b pero no al contrario. En el grafo no dirigido si es de lado a lado la relación de adyacencia.

Representación A parte de la representación básica conocida de los grafos, las más utilizada es la presentación a través de Matriz de Adyacencia, utilizada en los

Esta matriz de adyacencia utiliza bastante memoria por su nivel de complejidad en cuanto a los recorridos y verificaciones. Otra representación es la Lista adyacente en donde se crea una lista con las aristas del Grafo donde se asocian cada vértice con una lista con todos los vértices adyacentes donde cada elemento de la lista se le guarda un espacio para la relación de adyacencia con cada vértice. Cuando es un Grafo dirigido se crea un arreglo con la listas de las aristas y dentro de la lista están los vértices dirigidos.

En los Grafos no dirigido se hace una dupla de vértices unidos por la arista.

B.

C.

Búsqueda.

Las búsquedas pueden ser en profundidad o a lo ancho.

Universidad Piloto de Colombia. Agudelo. Grafos

3

La búsqueda en profundidad se realiza como un recorrido en preorden del concepto de árboles, se lleva la cuenta de los vértices recorridos, varían los órdenes dependiendo en inicio del recorrido y los vértices recorridos. La búsqueda a lo ancho se realiza por niveles similar al recorrido por nivel del concepto de árbol. Este se hace iniciando por un vértice y recorriendo los vértices adyacentes a estos y así luego con los adyacentes a estos.

III. APLICACIONES La teoría de grafos y la representación de los mismos han sido utilizadas en diversos campos. A continuación veremos rápidamente diferentes aplicaciones en que se usan los Grafos.

Utilizados también en la representación de diagramas de flujo, mapas conceptuales y mentales.

En rutas o sistemas de trasporte

La estructura de una red de equipos tecnológicos.

Se utilizan también por ejemplo para circuito eléctricos un poco más complejo.

IV.

REFERENCIAS