Grafos

FERLEY GALLEGO DIAZ
INGENIERIA DE SISTEMAS
QUE ES UN GRAFO
Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices,llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).
GRAFOS NO DIRIGIDOS
Son aquellos que notienen una dirección establecida.
GRAFOS DIRIGIDOS
Son aquellos que tienen una dirección establecida.
VERTICES O NODOS
Un vértice o nodo es la unidad fundamental de la que están formadoslos grafos.
ARISTAS O ARCOS
Las aristas, junto con los vértices, forman los elementos principales con los que trabaja esta disciplina, siendo consideradas las aristas las uniones entre nodos o vértices.MATRIZ DE ADYACENCIA
Sea G = (V , A) un grafo de n nodos, suponemos que los nodos V = {v1, v2,……..,vn} están ordenados y podemos representarlos por sus ordinales {1 , 2,…….,n}. La representación de losarcos se hace con una matriz A de n x n elementos aij definida:
1 si hay un arco
0 si no hay arco
LISTA DE ADYACENCIA
Las listas de adyacencia son una estructura multienlazada formada por una listadirectorio cuyos nodos representan los vértices del grafo y del que además emergen una lista enlazada cuyos nodos, a su vez , representan los arcos con vértice.
RECORRIDO DE UN GRAFO
Lasoperaciones de recorrer una estructura consisten en visitar cada uno de los nodos a partir de uno dado. Así, para recorrer un árbol se parte del nodo raíz y según el orden se visitan todos los nodos. Recorrerun grafo consiste en visitar todos los vértices alcanzables a partir de uno dado. Hay dos formas: recorrido por amplitud y recorrido por profundidad.
RECORRIDO POR AMPLITUD
Este método comienzavisitando el vértice de la partida A, para a continuación visitar los adyacentes que no estuvieron ya visitados. Así sucesivamente con los adyacentes. Este método utiliza una cola como estructura...