tareas estructiras









Tarea
Listas encadenadas, matriz de adyacencia, puntero, nodo, programa con método burbuja, ordenamiento y búsqueda




ASIGNATURA: estructura de datos

PROFESOR: Armando Gamboa

ESTUDIANTE: Navarrete Tiburcio Luis Alberto

CARRERA: Ingeniería en Tecnologías de la Información y Comunicaciones

FECHA:

CALIFICACION:COMENTARIOS:_______________________________________________________________________________________________________________________________________________________________________________________________________________

Matriz de adyacencia

Un grafo se puede representar mediante una matriz. Es la forma más sencilla de representar un grafo. A esta matriz se le denomina matriz de adyacencia.
Esta matriz consiste en un arreglo bidimensional de tamaño “n”, donde “n”es la máxima cantidad de nodos en el grafo. Cada casilla de la matriz se carga con valores verdadero “V” o falso “F” en caso de que posea un camino de un nodo o fila con columna. En caso de los grafos no dirigidos la matriz será simétrica.
Esto no ocurre en los dígrafos, donde se considera la dirección de cada uno de los arcos. Para el caso de los grafos ponderados, la matriz podrá ser cargada conel peso asociado a cada uno de los arcos.
La ventaja principal es su simplicidad, dado que facilita las operaciones que puedan realizarse sobre el grafo. La desventaja es que se limita a un número máximo de nodos en el grafo, lo que provoca que sea imposible almacenar más información en la matriz.
Si la matriz es muy grande para representar un grafo pequeño, se desperdicia el espacio dealmacenamiento de la matriz y de la memoria. Para un grafo no dirigido, el desperdicio será mayor porque al ser simétrica la matriz, su información se duplicaría.

Grafo representado por la matriz de adyacencia

En esta figura se muestra un grafo representado mediante una matriz de adyacencia. Se observa que cada camino une dos nodos.
Ejemplo: de “A” hacia “C” existe un camino por lo que el valor de lacasilla es “V” (verdadero), de la misma forma de “A” hacia “B” no existe un camino, por lo que el valor de la casilla de la matriz es “F” (falso).

Ejemplo de Matriz de Adyacencia

Para hacer la matriz de adyacencia a un grafo se debe sacar lo siguientes grafos:
 La matriz de adyacencia para el Grafo A:

Comprobaremos cada elemento de la matriz Aij (i=Fila j=Columna)
A11 ¿arista del v1 al v1? Siexistiese pondríamos 2 ya que sería un bucle pero como no es el caso 0.
A12 ¿arista del v1 al v2? Si, ¿cuántas? 1
A13 ¿arista del v1 al v3? Si, ¿cuántas? 1

Y así lo haremos con cada fila y con cada columna quedando la matriz así:
| 0 1 1 |
| 1 0 0 |
| 1 0 2 |
Al tratarse de un grafo no dirigido obtenemos una matriz simétrica, por lo que si usamos cada fila o cada columna obtendremos el grado de cadavértice.

 La matriz de adyacencia para el Grafo B:

Se comprueba exactamente igual que el grafo A, con la diferencia que los arcos tienen una dirección. El resultado es:
| 0 0 1 |
| 1 0 0 |
| 0 0 1 |

Al tratarse de un grafo dirigido si sumamos las columnas obtenemos el grado de entrada y si sumamos las filas el grado de salida.

Otro Ejemplo de una Matriz de Adyacencia


 




Listaencadenada
Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo, donde el orden de los mismos se establece mediante punteros.
La idea básica es que cada componente de la lista incluya un puntero que indique donde puede encontrarse el siguiente componente por lo que el orden relativo de estos puede serfácilmente alterado modificando los punteros lo que permite, a su vez, añadir o suprimir elementos de la lista. El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista.
El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.
Listas Enlazadas frente a...