5 Teoría de Grafos 5.3 Algoritmos de Recorridos y Búsqueda ALGORITMOS DE RECORRIDOS Y BÚSQUEDA. A* es un algoritmo informático que se utiliza en la búsqueda de caminos y el recorrido del grafo, proceso de trazar un camino transitable de manera eficiente entre los dos puntos, llamados nodos. 5.3.1 ALGORITMOS DE RECORRIDO Y BÚSQUEDA EL CAMINO MAS CORTO El problema del camino más corto es encontrar un camino entre dos vértices de tal manera que la suma de los pesos de las aristas sea mínima, para esto se utilizara el algoritmo de DIJKSTRA que es el siguiente: 1. Inicializar todas las distancias en D con un valor infinito relativo ya que son desconocidas al principio, exceptuando la de x que se debe colocar en 0 debido a que la distancia de x a x sería 0. 2. Sea a = x (tomamos a como nodo actual). 3. Recorremos todos los nodos adyacentes de a, excepto los nodos marcados, llamaremos a estos vi 4. Si la distancia desde x hasta va guardada en D es mayor que la...
Entradas
5 Teoría de Grafos 5.2 Representación de Los Grafos Representación por incidencia Lista de incidencia El grafo está representado por un arreglo de aristas, identificadas por un de pares de vértices, que son los que conecta esa arista. Matriz de incidencia El grafo está representado por una matriz de A (aristas) por V (vértices), donde [arista, vértice] contiene la información de la arista (conectado o no conectado). Representación por adyacencia Listas de adyacencia El grafo está representado por un arreglo de listas de adyacencia. Para un vértice i, la lista de adyacencia está formada por todos los vértices adyacentes a i. Puede construirse en tiempo lineal, y las inserciones pueden hacerse al principio de cada lista, con lo que se asegura tiempo constante. Matriz de adyacencia Una matriz de adyacencia es una matriz M de dimensión n*n, en donde n es el número de vértices que almacena valores booleanos, donde M[i,j] es verdadero (o contien...
5 Teoría de Grafos 5.1 Elementos, Características y componentes de los grafos Una gráfica G (V, E) consiste en un conjunto no vació V llamado conjunto de vértices (nodos, puntos) y el conjunto E de pares ordenados o no ordenados de elementos de V denominado el conjunto de aristas, tales que hay un mapeo del conjunto E al conjunto de pares ordenados o no ordenados de elementos de V. Si en la gráfica G = (V ,E) cada arista e ∈ E se asocia con un par ordenados de vértices, entonces G recibe el nombre de gráfica dirigida o diagráfica, si cada arista se asocian un par no ordenados de vértices, entonces G, se llama gráfica no dirigida. Una gráfica ( o gráfica no dirigida) G consta de un conjunto V de vértices (o nodos) y un conjunto E de aristas (arcos o lados) tales que cada arista e ∈ E queda asociada a un par no ordenado de vértices. Si existe una única arista e asociada con los vértices u y w escribimos e = (v, w) o e = ...