Actividad 4.4 - Grafos
Enviado por anm0r • 26 de Agosto de 2023 • Resúmenes • 3.388 Palabras (14 Páginas) • 26 Visitas
TECNM
Actividad 4.4 – Grafos
Resumen y conclusión
Unidad 4
Resumen
Un grafo es un par (V,E) donde V es un conjunto de vértices y E (edges) para un conjunto de aristas.
Los grafos se pueden usar para la síntesis de circuitos secuenciales, contadores, en sistemas de apertura y también se pueden aplicar en áreas de sistemas y computación, asi como en ingeniería.
Los grafos se usan para solucionar problemáticas como: ¿Qué tarea debo hacer primero? ¿Cuál es el tiempo más corto? ¿Cuál es el más barato?
Anteriormente se dijo que un grafo es un par (V, E). Los vértices son representados como puntos, y las aristas son la conexión entre estos vértices.
[pic 1]
La representación computacional de los grafos viene siendo de dos formas, mediante matrices o arreglos unidimensionales:
- Mediante matrices: La forma más sencilla de guardar datos en nodos es usando un vector que indique los nodos, de forma que las aristas entre los nodos se puedan ver como relaciones entre los índices.
TIpoVariable[ ][ ]… [ ] NombreArray = new TipoVariable[dimensión1][dimensión2]…[dimensiónN];
- Mediante arreglos unidimensionales: Como su nombre lo dice, es un arreglo que solo posee una dimensión, está formado por un conjunto de elementos del mismo tipo de datos que se almacena bajo un nombre y se diferencia por la posición de cada uno en el arreglo que inicia desde 0. Pueden ser de 1 a n veces, donde n veces es un número de elementos del arreglo.
TipoDato nombre[] = new TipoDato[TamañoDeArreglo]
El algoritmo de Floyd-Warshall fue hecho en 1959 por Bernard Roy, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo entre grafos. Este encuentra el camino entre todos los pares de vértices en una única ejecución.
En un grafo se quiere obtener el camino de distancia mínima entre 2 vértices.
[pic 2]
| 0 | 1 | 2 | 3 | 4 |
0 | 0 | 3 | 7 | 8 | 14 |
1 | 3 7 | 0 9 | 9 0 | 5 4 | 11 8 |
2 | |||||
3 | 8 14 | 5 11 | 4 8 | 0 6 | 6 0 |
4 |
Lo que pasa es que se hace un recorrido, por ejemplo, de 0 a 0 no tenemos nada, entonces colocamos cero, de 0-1 tenemos un valor de 3, lo colocamos, de 0-2 tenemos un valor de 7, de 0-3 tenemos 2 caminos, que puede ser el de arriba (0-1-3) que nos daría 8, o el de abajo que es (0-2-3) que nos daría 9, como estamos buscando el camino más corto, elegiríamos el primero, que es 01-3 con un valor de 8 y por último, el de 0-4, sucede lo mismo con este, se elige el camino (0-1-3-4) con un valor de 14.
Ahora con matriz de adyacencia, si no hay arista entre dos vértices, se considera +∞. Se realiza igual que el anterior, solo que en este caso, solamente contando aquellos que tengan una arista directa.
[pic 3]
Como se puede observar, elementos como el 0-3 o el 0-4 tienen un +∞ debido a que no tienen una arista, como es en el caso de 0-1 o 0-2.
Solo se almacenarían los elementos por debajo de la diagonal principal, entonces:
- : [[3],
- : [7,inf],
- : [inf,5,4],
- : [inf,inf[8,6]]
Representación de un grafo:
Class MatrizCiudades: def _init_ (self, numeroCiudades) :
…. def elemento
(self, i, j):
…. def cambiaElemento (self,
I, j, n) :
…. def
numeroCiudades (self): return len(self.matriz)
El cálculo del camino más corto: suponiendo que tenemos n ciudades, numeradas desde el 0 hasta n-1, construimos una sucesión de matrices.
namespace ConsoleApp1 { internal class Program { class CaminoMasCorto { static int V = 9; int DistanciaMinima(int[] dist, bool[] set) { //Se inicia el valor minimo int min = int.MaxValue, minIndice = -1;
for (int v = 0; v < V; v++) if (set[v] == false && dist[v] <= min) { min = dist[v]; minIndice = v; }
return minIndice; }
void Imprimir(int[] dist, int n) { Console.Write("Vertice Distancia " + "del origen\n"); for (int i = 0; i < V; i++) Console.Write(i + " \t\t " + dist[i] + "\n"); } void dijkstra(int[,] grafo, int origen) { int[] dist = new int[V]; //Arreglo de salida, dist[i], tendra la distancia mas corta desde origen a i
bool[] set = new bool[V]; //Sera true si el vertice i esta incluido en la ruta mas corta o distancia mas corta desde de origen a i
for (int i = 0; i < V; i++) { dist[i] = int.MaxValue; //Se inicializa en infinito y falso las distancias set[i] = false; }
dist[origen] = 0; //La distancia del vertice origen siempre sera cero //Encuentra la ruta mas corta for (int count = 0; count < V - 1; count++) {//Agarra el vertice con la distancia minima del set de vertices no procesados int u = DistanciaMinima(dist, set); // u siempre sera nuestro origen en la primera iteracion set[u] = true; //Marca el vertice actual como procesado for (int v = 0; v < V; v++) //actualiza la distancia de los vertices adyacentes del vertice tomado
if (!set[v] && grafo[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + grafo[u, v] < dist[v]) dist[v] = dist[u] + grafo[u, v]; }
Imprimir(dist, V); }
public static void Main() { int[,] grafo = new int[,] { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, { 0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, { 0, 0, 4, 14, 10, 0, 2, 0, 0 }, { 0, 0, 0, 0, 0, 2, 0, 1, 6 }, { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, |
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; CaminoMasCorto t = new CaminoMasCorto(); t.dijkstra(grafo, 0); } } } }
|
...