Download Manejo de Pilas y Colas. 2 año `94 mejorado

FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Licenciatura en Sistemas de Información
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 6
Fecha:09/10/2012
TEMA: Grafos.
Objetivos: Que los alumnos logren…
 Habilidad para identificar las distintas estructuras de tipo recursivas y capacidad para utilizar el
concepto de recursión.
 Capacidad para comprender como funciona la estructura de datos Grafos e identificar sus
operaciones básicas.
 Capacidad para utilizar diagramas UML básicos.
 Capacidad para resolver problemas con estructuras de datos :Grafos
 Capacidad para verificar la solución de algoritmos desarrollados usando POO

Capacidad para usar, en forma eficiente, los distintos métodos de clasificación y de búsqueda.

Destreza en el uso del entorno de desarrollo Netbeans y el lenguaje de programación Java.

Capacidad para implementar correctamente las soluciones algorítmicas, en lenguaje de
programación Java
Fecha de presentación: 1 semana a partir de la fecha del práctico.
Consideraciones Generales:
1. Este trabajo práctico debe realizarse en forma individual.
2. La presentación implicará la entrega del material abrochado, o en una carpeta, contando con los
siguientes ítems:
o Carátula. Identificación completa del trabajo práctico con todos los datos del alumno y la
asignatura, año, carrera, etc.
o Desarrollo del práctico con hojas numeradas e identificadas, que deberá incluir:
3. Los algoritmos deben estar completamente desarrollados, de manera prolija, e
incluyendo las descripciones necesarias para su mejor seguimiento (identificación,
variables utlizadas y sus funciones, etc.), cumpliendo las indicaciones relativas a la
diagramación estructurada y modular.
o El Código de las aplicaciones solicitadas deberá enviarse al correo de la materia
[email protected]. El nombre del código deberá estar conformado de acuerdo al
siguiente esquema: carrera_ ApellidoNomdelAlumno_NumPrac_NumEjerc.
Resolver los siguientes problemas de tipo teórico, practico y experimental
1. Un grafo dirigido A consiste en un conjunto de vértices v y un conjunto de arcos a. Los vértices se
denominan también puntos o nodos, los arcos pueden llamarse arcos dirigidos o líneas dirigidas.
Para el siguiente grafo dirigido:
2
3
1
6
4
a)
b)
c)
d)
e)
f)
5
Identificar arcos considerando en cada uno
90 de ellos la cola y la cabeza del arco.
Identificar los adyacentes de los vértices802 y 4.
Indique todos los caminos simples que llevan
desde el vértice 1 al vértice 5.
70
60 de salida de cada vértice del grafo.
Determinar el grado de entrada y el grado
50 e indique su longitud.
Este
Existen ciclos en este grafo? Identifíquelos
40
Representar el grafo con su matriz de adyacencias.
Oeste
30
Norte
20
2. Dado el grafo A del ejercicio anterior se establece10la matriz de pesos a continuación:
0
A=
0
0
0
0
0
0
30
0
10
0
0
0
0
0
0
25
0
21
20
5
0
0
0
0
0
9
33
17
0
0
0
0
0
0
40
0
1er
trim.
2do
trim.
3er
trim.
4to
trim.
a) Identificar los caminos entre cada nodo del
grafo y sus pesos considerando la matriz de
pesos.
b) Identificar el camino de menor costo entre
los vértices 1 y 6.
Pag:1
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Licenciatura en Sistemas de Información
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 6
Fecha:09/10/2012
3. El siguiente grafo dirigido representa la trayectoria de tráfico (arcos) entre las ciudades (vértices). Cada
uno de los arcos se etiqueta con la distancia entre un par de ciudades interconectadas expresadas en
centenares de kilometros.
6
4
2
2
4
1
6
5
1
6
5
3
6
a) Ejemplifique un camino que permita conectar por lo menos 4 ciudades.
b) Realice la representación del grafo dirigido utilizando matriz de adyacencias.
c) Realice el recorrido del grafo en profundidad partiendo del nodo 1, grafique el recorrido y el
seguimiento de la pila de nodos visitados.
d) Realice el recorrido en amplitud del grafo partiendo desde el nodo 1, grafique el recorrido y el
seguimiento de la cola de nodos visitados.
4. Dado el siguiente grafo dirigido encontrar los componentes conexos y fuertemente conexos.
1
2
3
7
4
5
6
5. Considere las clases desarrolladas en la referencia bibliográfica 1 (“Estructuras de datos en
Java”.Capitulo 15) respecto a Grafos. Dé entrada al código que permite la representación de grafos
mediante matriz de adyacencia, verifique su ejecución dando entrada al grafo del ejercicio 3.
 Expresar el algoritmo solución en diagramas de flujo, para cada uno de los métodos.
 Codificar y ejecutar el algoritmo solución en lenguaje Java, utilizando el entorno de desarrollo (IDE)
Netbeans.
Recursos Bibliograficos
1. JOYANES AGUILAR LUIS ZAHONERO MARTINEZ IGNACIO. “Estructuras de Datos en Java”. Mc
Graw Hill - 2008.
2. JOYANES AGUILAR LUIS ZAHONERO MARTINEZ IGNACIO. “Estructuras de Datos”.Algoritmos,
abstracción y objetos. Mc Graw Hill – 2003
3. CAIRO, OSVALDO. Estructuras de datos. Mc Graw Hill - 2006.
4. MARY S. LOOMIS. Estructura de Datos y Organización de Archivos. Hall Hispanoamericana S.A. –
1991.
Recursos de Software
 Entorno de Desarrollo NetBeans versión 7.1
 Java 2EE.
Pag:2
FACULTAD DE CIENCIAS EXACTAS Y TECNOLOGIAS
CARRERA: Licenciatura en Sistemas de Información
ASIGNATURA: Estructura de Datos y Programación
TRABAJO PRÁCTICO Nº 6
Fecha:09/10/2012
Anexo
Algoritmo de ordenación topológica
La codificación del algoritmo depende de la representación del grafo, con matriz o lista de adyacencia.
La siguiente codificación es un grafo representado con matriz de adyacencia.
// clase Grafo
public class Grafo {
vertice [] V;
int [][]Matriz;
int mv=5;
Scanner ingreso;
int AI[];
Cola Q;
public Grafo(){
Q=new Cola();
Matriz=new int [mv][mv];
V=new vertice[mv];
ingreso = new Scanner(System.in);
AI=new int[mv];
}
//****************
public void CalculaGradoEntrada(){
for(int j=0;j<mv;j++){
for(int i=0;i<mv;i++){
if(Matriz[i][j]==1){
AI[j]=AI[j]+1;
}
}
}
}
public void ProcesarVectorAdya(int AI[]){
for(int i=0;i<mv;i++){
if(AI[i]==0){
Q.insertar(i);
}
}
}
public void RecorrerCola(){
while(!Q.vacia()){
nodoc elem = Q.quitar();
System.out.println(" "+elem.getDato());
EliminarAristas(elem.getDato(),AI);
}
}
public void EliminarAristas(int x,int AI[] ){
for(int j=0;j<mv;j++){
if(Matriz[x][j]==1){
Matriz[x][j]=0;
AI[j]=AI[j]-1;
if(AI[j]==0){
Q.insertar(j);
}
}
}
}
public void OrdenacionTopologica(){
System.out.println("Ordenacion Topologica");
CalculaGradoEntrada();
ProcesarVectorAdya(AI);
RecorrerCola();
}
Ademas debe crear las clase Cola, nodoc.
Pag:3