Grafo conexo java
Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 19,82 KB
Un grafo 
es 
un conjunto formado por 
vértices y un conjunto de arcos o aristas (edges en inglés) que son un conjunto de duplas 
Definición:
Un grafo es dirigido si hay un arco de
a 
pero no de a para algún 
. Es decir, si los arcos “tienen flechas”.
es adyacente de si 
.
a 
si 
con todos los . Un camino es simple si no se repite ningún vértice en el trayecto de ese camino.
a . Un ciclo es simple si no se repite ningún vértice excepto el primero y el último.
es subgrafo de otro grafo 
si 
y 
.Inconvenientes de la lista de adyacencia: Es difícil medir el grado de entrada de un nodo.
COLA.Recorrido de profundidad. PILA.
y desencolarlo.Encolar adyacentes de no visitados.Meter adyacentes de en visitados.
y desapilarlo.Apilar adyacentes de no visitados.Meter adyacentes de en visitados.Aplicamos el siguiente código:Void Dijkstra (tabla T){Vértices V,W;While (algún vértice no vistado){V=vértice no visitado con 
mas pequeñaT[V].Visitado=1;For (cada W adyacente de V){If(T[V].D + peso < t[w].D){t[w].D="">Definición:
Una ordenación topológica en un grafo necesariamente dirigido y acíclico es una ordenación de los nodos del grafo que cumple lo siguiente:
es un conjunto formado por vértices y un conjunto de arcos o aristas (edges en inglés) que son un conjunto de duplas Definición:Un grafo es dirigido si hay un arco de
a pero no de a para algún . Es decir, si los arcos “tienen flechas”.Definición
Un vértice es adyacente de si .Definición
Existe un camino de a si con todos los . Un camino es simple si no se repite ningún vértice en el trayecto de ese camino.Definición
La longitud de un camino es el número de arcos que hay que tomar para llegar al último vértice desde el primero.Definición
Un ciclo es un camino de a . Un ciclo es simple si no se repite ningún vértice excepto el primero y el último.Definición
Un grafo es conexo si existe un camino entre cada par de nodos.Definición
Un grafo es completo si existe un arco entre cada par de nodos.Definición
El grado de un nodo es el número de arcos que entran o salen del nodo. Surgen dos conceptos de la definición:Grado de entrada: El número de arcos que van hacia el nodo en cuestión.Grado de salida: El número de arcos que salen del nodo en cuestión.Definición
Un grafo ponderado es ponerle a cada arco de un grafo un valor.Definición
Un grafo es subgrafo de otro grafo si y .Inconvenientes de la lista de adyacencia: Es difícil medir el grado de entrada de un nodo.Definición
Un recorrido es una manera sistemática de visitar todos los nodos del grafo. Hay dos tipos de recorrido:Recorrido de anchura. COLA.Recorrido de profundidad. PILA.Algoritmo de recorrido de anchura
Recibimos un grafo y elegimos un vértice que llamaremos inicial.Meter el vértice inicial en “visitados”.Encolar el vértice inicial.Repetir los pasos 4) a 6) hasta vaciar la cola.Imprimir el primero de la cola al que llamamos y desencolarlo.Encolar adyacentes de no visitados.Meter adyacentes de en visitados.Algoritmo de recorrido de profundidad
Recibimos un grafo y elegimos un vértice que llamaremos inicial.Meter el vértice inicial en “visitados”.Apilar el vértice inicial.Repetir los pasos 4) a 6) hasta vaciar la pila.Imprimir la cima de la pila al que llamamos y desapilarlo.Apilar adyacentes de no visitados.Meter adyacentes de en visitados.Aplicamos el siguiente código:Void Dijkstra (tabla T){Vértices V,W;While (algún vértice no vistado){V=vértice no visitado con mas pequeñaT[V].Visitado=1;For (cada W adyacente de V){If(T[V].D + peso < t[w].D){t[w].D="">Definición:Una ordenación topológica en un grafo necesariamente dirigido y acíclico es una ordenación de los nodos del grafo que cumple lo siguiente:
Si hay un camino de 
a 
entonces en el orden se cumple que aparece antes que .