Revision: 46841
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at May 26, 2011 14:25 by josepino
Initial Code
//////////////////////////////////////////////////////////////////////////////////////////////////////////// /* * JOSE PINO - SANTIAGO TORTORA * * * * Dado un grafo no dirigido G con el conjunto de vértices {0,1,..,V-1} y con E aristas. Denotamos con (i,j) la * conexión entre el vértice i y el vértice j y con d(i) el grado del vértice i. * * Definimos las siguientes operaciones: * - borrarArista(i,j): borrar de G la arista (i,j). * - borrarAristasIncidentes(i): borrar de G todas las d(i) aristas incidentes en el referido vértice. * * Implemente ambas funciones en el código fuente de libro de Weiss y mencione un preciso análisis del costo de * ejecución de ambos métodos. El código fuente estará disponible en Educa * * Incluya todos los archivos necesarios para las pruebas de funcionamiento. * * Para tener una mejor idea de cómo está almacenado el grafo y su diseño * consultar el libro Algoritmos y Estructuras de Datos en Java, Mark A. Weiss *Pag. 357 Addison Wesley * */ //////////////////////////////////////////////////////////////////////////////////////////////////////////// import DataStructures.*; import Supporting.*; import Exceptions.*; import java.util.StringTokenizer; import Supporting.Comparable; import java.io.*; // Graph class interface: evaluate shortest paths // // CONSTRUCTION: with no initializer // // ******************PUBLIC OPERATIONS********************** // void addEdges( String source, String dest, int cost ) // --> Add additional edge // boolean processRequest( BufferedReader in ) // --> Run a bunch of shortest path algs // ******************ERRORS********************************* // Some error checking is performed to make sure graph is ok, // parameters to processRequest represent vertices in the graph, // and to make sure graph satisfies properties needed by each algorithm /** * This class represents the basic * item in the adjacency list. */ class Edge { // First vertex in edge is implicit public int dest; // Second vertex in edge public int cost; // Edge cost public Edge( int d, int c ) { dest = d; cost = c; } } /** * This class represents the basic item * stored for each vertex. */ class Vertex { String name; // The real name List adj; // The adjacency list int dist; // Cost (after running algorithm) int prev; // Previous vertex on shortest path int scratch; // Extra variable for use in algorithm int grado; //El grado de entrada del nodo. Vertex( String nm ) { name = nm; // Share name in hash table adj = new LinkedList( ); // Make a new list } } /** * This class represents the basic entry * in the vertex dictionary. * It implements the Hashable interface by providing * hash and equals. */ class HashItem implements Hashable { public String name; /* The real name */ public int rank; /* The assigned number */ public HashItem( ) { this( null ); } public HashItem( String nm ) { name = nm; } public int hash( int tableSize ) { return ProbingHashTable.hash( name, tableSize ); } public boolean equals( Object rhs ) { return name.equals( ((HashItem) rhs).name ); } } /** * Object stored in the priority queue * for Dijkstra's algorithm */ class Path implements Comparable { int dest; // W int cost; // D(W) static Path negInf = new Path( ); // Sentinel Path( ) { this( 0 ); } Path( int d ) { this( d, 0 ); } Path( int d, int c ) { dest = d; cost = c; } public boolean lessThan( Comparable rhs ) { return cost < ( (Path) rhs ).cost; } public int compares( Comparable rhs ) { return cost < ( (Path) rhs ).cost ? -1 : cost > ( (Path) rhs ).cost ? 1 : 0; } } /** * Graph class: evaluate shortest paths. */ public class Graph { public Graph( ) { numVertices = 0; table = new Vertex[ INIT_TABLE_SIZE ]; vertexMap = new QuadraticProbingTable( ); } /** * Add the edge ( source, dest, cost ) to the graph. */ public void addEdge( String source, String dest, int cost ) { addInternalEdge( addNode( source ), addNode( dest ), cost ); } /** * Process a request; return false if end of file. */ public boolean processRequest( BufferedReader in ) { String sourceName, destName; HashItem source = new HashItem( ); HashItem dest = new HashItem( ); try { System.out.println( "Enter start node:" ); if( ( sourceName = in.readLine( ) ) == null ) return false; System.out.println( "Enter destination node:" ); if( ( destName = in.readLine( ) ) == null ) return false; } catch( IOException e ) { System.out.println( "Error: " + e ); return false; } try { source.name = sourceName; source = (HashItem) ( vertexMap.find( source ) ); dest.name = destName; dest = (HashItem) ( vertexMap.find( dest ) ); unweighted( source.rank ); printPath( dest.rank ); if( dijkstra( source.rank ) ) printPath( dest.rank ); else System.out.println( "Dijkstra fails - neg edge" ); if( dijkstraPair( source.rank ) ) printPath( dest.rank ); else System.out.println( "Dijkstra fails - neg edge" ); if( negative( source.rank ) ) printPath( dest.rank ); else System.out.println( "Negative fails - neg cycle" ); if( acyclic( source.rank ) ) printPath( dest.rank ); else System.out.println( "Acyclic fails - cycle" ); } catch( ItemNotFound e ) { System.err.println( "Vertex not in graph" ); } return true; } /** * Metodo para imprimir la est. de datos tabla que se utiliza * para representar el grafo. * Muestra el nodo de la tabla y sus adyacentes. */ public void imprimirGrafoTabla(){ int i = 0; ListItr theList; Edge theEdge; System.out.println( "Nodo\tAdyacentes"); //Recorremos la tabla mientras que no sea null while( this.table[ i ] != null ) //Analizamos cada nodo en la tabla { System.out.print( " " + this.table[ i ].name + " --> "); //Imprimimos el nodo actual //Una vez impreso el nodo actual, tenemos que revisar su lista de adyacencias theList = new LinkedListItr( this.table[ i ].adj ); theList.first(); theEdge = (Edge)theList.retrieve(); while( theEdge != null ) { System.out.print( this.table[ theEdge.dest ].name + " "); //Imprimimos theList.advance(); //Avanzamos la lista theEdge = (Edge)theList.retrieve(); } System.out.print("\n"); i++; } } /** * Metodo para borrar una arista de un nodo X a un nodo Y * La idea es ir hasta X luego ver si existe Y en la lista de X, * si existe ir hasta Y y remover en la lista de Y la ocurrencia de X, * por ultimo remover de la lista de X la ocurrencia de Y * @param X * @param Y * Costo: * -Encontrar los vertices por sus nombres: O(1) gracias a la tabla hash * -Encontrar arista en la lista de adyacencia (2 veces): O(|E|) * -Borrar las aristas de las listas de adyacencia: O(1) * -Costo total: O(|E|) * @throws ItemNotFound */ private void borrarArista(String X, String Y) throws ItemNotFound{ LinkedListItr AdjX = new LinkedListItr(table[addNode(X)].adj); AdjX.first(); LinkedListItr AdjY = new LinkedListItr(table[addNode(Y)].adj); AdjY.first(); for( ;AdjX.isInList(); AdjX.advance() ) { Edge actual = ((Edge)(AdjX.retrieve())); if( actual.dest == addNode(Y) ) { AdjX.remove(actual); } } for( ;AdjY.isInList(); AdjY.advance() ) { Edge actual = ((Edge)(AdjY.retrieve())); if( actual.dest == addNode(X) ) { AdjY.remove(actual); } } } public void borrarAristaviejo(String X, String Y) throws ItemNotFound{ int i = 0; int j = 0; ListItr theListi; Edge theEdge; ListItr theListj; Edge theEdge2; boolean continuar=true; //Recorremos la tabla while( this.table[ i ] != null && !continuar ){ //Analizamos secuencialmente cada nodo en la tabla if (this.table[i].name.equals(X)) { //Comparamos hasta encontrar X //Una vez encontrado el nodo X, tenemos que revisar su lista de adyacencias e ir hasta Y theListi = new LinkedListItr( this.table[ i ].adj ); theListi.first(); theEdge = (Edge)theListi.retrieve(); // continuar = true; while( theEdge != null ) { //Recorremos para buscar Y en la lista de X //Buscamos en la lista de X el nodo Y para desconectar if ( this.table[theEdge.dest].name.equals(Y) ){ //Verificamos si Y figura en la lista de adyacencias de X theListi.remove(theEdge); continuar=false; break;} else{ theListi.advance(); theEdge = (Edge)theListi.retrieve();} } } i++; } int posY=findPosEdge(Y); theListj = new LinkedListItr(table[posY].adj); theListj.first(); for( ;theListj.retrieve()==null; theListj.advance()){ Edge actual = ((Edge)(theListj.retrieve())); if( actual.dest == (posY)) theListj.remove(actual); } } private int findPosEdge(String edgeName){ for(int i=0; i<numVertices; i++){ if(table[i].name.equals(edgeName)) return i; } return -1; } /** * Metodo para borrar las aristas incidentes en un nodo Z * @param Z * La idea es ir hasta Z en la tabla[], luego ver sus adyacentes * primero ir sucesivamente a cada nodo adyacentes en la tabla[] del nodo Z y desconectar en donde figure Z * por ultimo eliminar todos los enlaces que figuran en la lista de adyacencia del nodo Z * Costo: * -Encontrar Z: O(|V|) * -Recorrer la lista de adyacencia, por cada elemento recorrer la otra lista de adyacencia, buscar * la arista adyacente y eliminar: O(|E|^2) * -Costo total: O(|V| + |E|^2) * @throws ItemNotFound */ /* Z es el nodo que queremos dejar libre, o sea borrar todas sus incidencias * J llamamos al nodo adyacente a Z */ public void borrarAristasIncidentes(String Z) throws ItemNotFound { int i = 0; int j = 0; boolean continuar; ListItr theList; ListItr theList2; Edge theEdge; Edge theEdge2; //Recorremos la tabla while( this.table[ i ] != null ){ //Analizamos secuencialmente cada nodo en la tabla if (this.table[i].name.equals(Z)) { //Comparamos hasta encontrar System.out.println ("Nodo " + Z + " encontrado " + "en indice: " + i); //Una vez encontrado el nodo Z, tenemos que revisar su lista de adyacencias theList = new LinkedListItr( this.table[ i ].adj ); theList.first(); theEdge = (Edge)theList.retrieve(); while( theEdge != null ) { System.out.print( this.table[ theEdge.dest ].name + " "); //Imprimimos nombre del adyacente a Z j = 0; while (this.table[j] != null) { if (this.table[j].name.equals(this.table[ theEdge.dest ].name)) { //Buscamos la posicion del adyacente a Z System.out.println (" Adyacente encontrado en indice " + j); //j contiene la posicion del adyacente a Z //Como el grafo es no dirigido, ahora tenemos que buscar en la posicion del nodo J y eliminar la referencia al nodo Z //Una vez encontrado el nodo J, tenemos que revisar su lista de adyacencias y desconectar Z theList2 = new LinkedListItr( this.table[ j ].adj ); theList2.first(); theEdge2 = (Edge)theList2.retrieve(); continuar = true; while( theEdge2 != null && continuar == true) { //Recorremos la lista del nodo J, la idea es buscar el nodo Z y desconectarlo //Buscamos en la lista de J el nodo Z para desconectar if ( this.table[i].name.equals(this.table[theEdge2.dest].name) ){ //Si Z figura en la lista de adyacencias de J eliminamos la referencia a Z continuar = false; theList2.remove(theEdge2); //Eliminamos Z de la lista de J } theList2.advance(); //Avanzamos la lista theEdge2 = (Edge)theList2.retrieve(); } } j++; } theList.advance(); //Avanzamos la lista theEdge = (Edge)theList.retrieve(); } System.out.print("\n"); //Una vez que se ha desconectado todos los nodos que apuntaban a Z, ahora limpiar la lista de Z para que Z apunte a ninguno theList.first(); //Nos colocamos nuevamente en la posicion primera de la lista de Z theEdge = (Edge)theList.retrieve(); while( theEdge != null ) { //Avanzamos y vamos limpiando la lista de Z theList.remove(theEdge); //Eliminamos el nodo theList.advance(); //Avanzamos la lista theEdge = (Edge)theList.retrieve(); } } i++; } } private LinkedList findCycle () throws ItemNotFound { boolean hay_ciclo = false; LinkedList Cycle = new LinkedList(); for( int i=0; i<this.numVertices && !hay_ciclo; i++ ) { ListItr adyacentes = new LinkedListItr(table[i].adj); for( ;adyacentes.isInList(); adyacentes.advance() ) { this.unweighted(i); //Si hay un camino entre un vertice adyacente y el propio vertice if( table[i].dist != INFINITY ) { //entonces hay un ciclo hay_ciclo=true; //System.out.println("Hay un ciclo: "); pathToList( ((Edge)(adyacentes.retrieve())).dest, Cycle); LinkedListItr aux = new LinkedListItr(Cycle); aux.first(); aux.insert( table[((Edge)(adyacentes.retrieve())).dest].name ); break; } } } return Cycle; } private LinkedList pathToList(int destino, LinkedList Path) throws ItemNotFound { Path.makeEmpty(); LinkedListItr Itr = new LinkedListItr(Path); Itr.zeroth(); int actual = destino; while( actual!=NULL_VERTEX ) { Itr.insert(table[actual].name); actual = table[actual].prev; } return Path; } /** * Main modificado con llamada a los metodos de impresion, borrado de aristas y borrado de incidentes * A main routine that: * 1. Prompts for a file containing edges; * 2. Forms the graph; * 3. Repeatedly prompts for two vertices and * runs shortest path algorithms. * The data file is a sequence of lines of the format * source destination cost. * @throws ItemNotFound */ public static void main( String [ ] args ) throws ItemNotFound { System.out.println( "ALGORITMOS Y EST. DE DATOS III - TAREA 7 - GRAFOS" ); System.out.println( "Ingrese la ruta completa y el nombre del archivo graph1.txt:" ); System.out.println( "Ejemplo -> C:\\graph1.txt" ); System.out.println(); // Get the file BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) ); FileReader fin; String fileName= ""; try { fileName = in.readLine( ); fin = new FileReader( fileName ); } catch( Exception e ) { System.err.println( e ); return; } BufferedReader graphFile = new BufferedReader( fin ); Graph g = new Graph( ); // Read the edges and insert try { String line; while( ( line = graphFile.readLine( ) ) != null ) { StringTokenizer st = new StringTokenizer( line ); try { if( st.countTokens( ) != 3 ) throw new Exception( ); String source = st.nextToken( ); String dest = st.nextToken( ); int cost = Integer.parseInt( st.nextToken( ) ); g.addEdge( source, dest, cost ); } catch( Exception e ) { System.err.println( "Error: " + line ); } } } catch( Exception e ) { System.err.println( "Error: " + e ); } /*Llamada original while( g.processRequest( in ) ) ; */ /////////////////////////////// METODOS AGREGADOS y PRUEBAS ////////////////////////////////// /* OJO: Ya que es un grafo no dirigido, en el archivo donde estan los nodos y sus costos deben estar * en ambos sentidos Ejemplo, para un Edge con costo 10 entre A y B: * A B 10 * B A 10 * Se podria optimizar agregando metodos, pero como WEISS ya implementa este tipo de caso, simplemente * modificar como el ejemplo hara que funcione bien para un grafo no dirigido. */ System.out.println( "\n---------------------\n" ); System.out.println( "\nEstado de la tabla:\n" ); g.imprimirGrafoTabla(); //Imprimimos el estado actual System.out.println( "\n---------------------\n" ); LinkedList ciclo = g.findCycle(); LinkedListItr cicloITR = new LinkedListItr(ciclo); if(ciclo.isEmpty()) System.out.println("El grafo es acÃclico"); else{ System.out.println("El grafo tiene un ciclo:"); for( ;cicloITR.isInList(); cicloITR.advance()){ System.out.print( (String)(cicloITR.retrieve()) + " " ); } System.out.println(); } System.out.println( "\nBorramos la arista A-D a modo de ejemplo:\n" ); g.borrarArista( "A", "D"); //Borramos la arista de A a D System.out.println( "\nEstado de la tabla despues de borrar la arista A-D:\n" ); g.imprimirGrafoTabla(); //Imprimimos el estado actual System.out.println( "\nBorramos las aristas incidentes en un nodo A a modo de ejemplo:\n" ); g.borrarAristasIncidentes( "A" ); //Borramos las aristas incidentes System.out.println( "\nEstado de la tabla despues de los metodos llamados:\n" ); g.imprimirGrafoTabla(); //Imprimimos nuevamente el estado System.out.println( "\nLista de sitios web ordenados segun la cantidad de enlaces que llegan a él:\n" ); g.imprimirOrdenado(); /////////////////////////////////////////////////////////////////////////////////////////////// } private static final int INIT_TABLE_SIZE = 50; private static final int NULL_VERTEX = -1; private static final int INFINITY = 2147483647 / 3; private HashTable vertexMap; // Gets internal # private Vertex [ ] table; // The table array private int numVertices; // Current # vertices read /** * Double the table array; usual stuff. */ private void doubleTableArray( ) { Vertex[ ] oldArray = table; table = new Vertex[ oldArray.length * 2 ]; for( int i = 0; i < oldArray.length; i++ ) table[ i ] = oldArray[ i ]; } /** * If vertexName is an already seen vertex, return its * internal number. Otherwise add it as a new vertex, * and return its new internal number. */ private int addNode( String vertexName ) { HashItem hashV = new HashItem( vertexName ); HashItem result; try { result = (HashItem) vertexMap.find( hashV ); return result.rank; } catch( ItemNotFound e ) { // Newly seen vertex hashV.rank = numVertices; hashV.name = new String( vertexName ); vertexMap.insert( hashV ); if( numVertices == table.length ) doubleTableArray( ); table[ numVertices ] = new Vertex( hashV.name ); return numVertices++; } } /** * Add an edge given internal numbers of its vertices. */ private void addInternalEdge( int source, int dest, int cost ) { ListItr p = new LinkedListItr( table[ source ].adj ); try { p.insert( new Edge( dest, cost ) ); table[dest].grado ++;} catch( ItemNotFound e ) { } // Cannot happen } /** * Initialize the table. */ private void clearData( ) { for( int i = 0; i < numVertices; i++ ) { table[ i ].dist = INFINITY; table[ i ].prev = NULL_VERTEX; table[ i ].scratch = 0; } } /** * Recursively print the shortest path to DestNode * (specified by its internal number) * printPath is the driver routine */ private void printPathRec( int destNode ) { if( table[ destNode ].prev != NULL_VERTEX ) { printPathRec( table[ destNode ].prev ); System.out.print( " to " ); } System.out.print( table[ destNode ].name ); } /** * Driver routine to handle unreachables and print total * cost. It calls recursive routine to print shortest path * to destNode after a shortest path algorithm has run. */ private void printPath( int destNode ) { if( table[ destNode ].dist == INFINITY ) System.out.println( table[ destNode ].name + " is unreachable" ); else { printPathRec( destNode ); System.out.println( " (cost is " + table[ destNode ].dist + ")" ); } System.out.println( ); } // Various short)est path algorithms that // require an internal number for start-up /** * Compute the unweighted shortest path. */ private void unweighted( int startNode ) { int v, w; Queue q = new QueueAr( ); clearData( ); table[ startNode ].dist = 0; q.enqueue( new Integer( startNode ) ); try { while( !q.isEmpty( ) ) { v = ( (Integer) q.dequeue( ) ).intValue( ); ListItr p = new LinkedListItr( table[ v ].adj ); for( ; p.isInList( ); p.advance( ) ) { w = ( (Edge) p.retrieve( ) ).dest; if( table[ w ].dist == INFINITY ) { table[ w ].dist = table[ v ].dist + 1; table[ w ].prev = v; q.enqueue( new Integer( w ) ); } } } } catch( Underflow e ) { } // Cannot happen } /** * Dijkstra's Algorithm using binary heap. * Return false if negative edge detected. */ private boolean dijkstra( int startNode ) { int v, w; PriorityQueue pq = new BinaryHeap( Path.negInf ); Path vrec; clearData( ); table[ startNode ].dist = 0; pq.insert( new Path( startNode, 0 ) ); try { for( int nodesSeen = 0; nodesSeen < numVertices; nodesSeen++ ) { do { if( pq.isEmpty( ) ) return true; vrec = (Path) pq.deleteMin( ); } while( table[ vrec.dest ].scratch != 0 ); v = vrec.dest; table[ v ].scratch = 1; ListItr p = new LinkedListItr( table[ v ].adj ); for( ; p.isInList( ); p.advance( ) ) { w = ( (Edge) p.retrieve( ) ).dest; int cvw = ( (Edge) p.retrieve( ) ).cost; if( cvw < 0 ) return false; if( table[ w ].dist > table[ v ].dist + cvw ) { table[ w ].dist = table[ v ].dist + cvw; table[ w ].prev = v; pq.insert( new Path( w, table[ w ].dist ) ); } } } } catch( Underflow e ) { } // This cannot happen return true; } /** * Dijkstra's Algorithm using pairing heap * Return false if negative edges detected. */ private boolean dijkstraPair( int startNode ) { int v, w; PairHeap pq = new PairHeap( ); Path vrec; PairNode [ ] heapPositions = new PairNode[ numVertices ]; clearData( ); for( int i = 0; i < numVertices; i++ ) heapPositions[ i ] = null; table[ startNode ].dist = 0; pq.insert( new Path( startNode, 0 ) ); try { while( !pq.isEmpty( ) ) { vrec = (Path) pq.deleteMin( ); v = vrec.dest; ListItr p = new LinkedListItr( table[ v ].adj ); for( ; p.isInList( ); p.advance( ) ) { w = ( (Edge) p.retrieve( ) ).dest; int cvw = ( (Edge) p.retrieve( ) ).cost; if( cvw < 0 ) return false; if( table[ w ].dist > table[ v ].dist + cvw ) { table[ w ].dist = table[ v ].dist + cvw; table[ w ].prev = v; Path newVal = new Path( w, table[ w ].dist ); if( heapPositions[ w ] == null ) heapPositions[ w ] = pq.addItem( newVal ); else pq.decreaseKey( heapPositions[ w ], newVal ); } } } } catch( Exception e ) { } // This cannot happen return true; } /** * Run shortest path algorithm; * Negative edge weights are allowed. * Return false if negative cycle is detected */ private boolean negative( int startNode ) { int v, w; Queue q = new QueueAr( ); int cvw; clearData( ); table[ startNode ].dist = 0; q.enqueue( new Integer( startNode ) ); table[ startNode ].scratch++; try { while( !q.isEmpty( ) ) { v = ( (Integer) q.dequeue( ) ).intValue( ); if( table[ v ].scratch++ > 2 * numVertices ) return false; ListItr p = new LinkedListItr( table[ v ].adj ); for( ; p.isInList( ); p.advance( ) ) { w = ( (Edge) p.retrieve( ) ).dest; cvw = ( (Edge) p.retrieve( ) ).cost; if( table[ w ].dist > table[ v ].dist + cvw ) { table[ w ].dist = table[ v ].dist + cvw; table[ w ].prev = v; // Enqueue only if not already on queue if( table[ w ].scratch++ % 2 == 0 ) q.enqueue( new Integer( w ) ); else table[ w ].scratch++; // In effect, adds 2 } } } } catch( Underflow e ) { } // Cannot happen return true; } /** * Run shortest path algorithm; * Linear-time algorithm, works only for acyclic graphs. * Return false if cycle is detected */ private boolean acyclic( int startNode ) { int v, w, iterations = 0; Queue q = new QueueAr( ); clearData( ); table[ startNode ].dist = 0; try { // Compute the indegrees for( v = 0; v < numVertices; v++ ) { ListItr p = new LinkedListItr( table[ v ].adj ); for( ; p.isInList( ); p.advance( ) ) table[ ( (Edge) p.retrieve( ) ).dest ].scratch++; } // Enqueue vertices of indegree zero for( v = 0; v < numVertices; v++ ) if( table[ v ].scratch == 0 ) q.enqueue( new Integer( v ) ); for( iterations = 0; !q.isEmpty( ); iterations++ ) { v = ( (Integer) q.dequeue( ) ).intValue( ); ListItr p = new LinkedListItr( table[ v ].adj ); for( ; p.isInList( ); p.advance( ) ) { w = ( (Edge) p.retrieve( ) ).dest; if( --table[ w ].scratch == 0 ) q.enqueue( new Integer( w ) ); if( table[ v ].dist == INFINITY ) continue; int cvw = ( (Edge) p.retrieve( ) ).cost; if( table[ w ].dist > table[ v ].dist + cvw ) { table[ w ].dist = table[ v ].dist + cvw; table[ w ].prev = v; } } } } catch( Underflow e ) { } // Cannot happen return iterations == numVertices; } private void imprimirOrdenado (){ clearData(); int posMayor; int mayor; for( int i=0; i<this.numVertices; i++){ int j; for(j=0; j<this.numVertices; j++){ if( table[j].scratch == 0 ){ break; } } mayor=table[j].grado; posMayor=j; for(; j<numVertices; j++) { if(table[j].scratch==0 && table[j].grado>mayor ){ posMayor = j; mayor = table[j].grado; } } table[posMayor].scratch = 1; System.out.println(table[posMayor].name + "\t" + table[posMayor].grado); } } }
Initial URL
Initial Description
Initial Title
Operaciones con Grafos - Operating with Graphs
Initial Tags
Initial Language
Java