public void BFS(int s) { boolean visited[] = new boolean[graph.getQuantityNodes()]; LinkedList queue = new LinkedList (); visited[s] = true; queue.add(s); while (!queue.isEmpty()) { s = queue.poll(); System.out.print(s + " "); Iterator i = graph.getAdjacent(s).listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) { visited[n] = true; queue.add(n); } } } } *********************************** public void DFS(int v) { boolean visited[] = new boolean[graph.getQuantityNodes()]; DfsUtil(v, visited); } public void DfsUtil(int v, boolean[] visited) { visited[v] = true; System.out.println(v + " "); Iterator i = graph.getAdjacent(v).listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) { DfsUtil(n, visited); } } } *********************************** public void resolverDijkstra(String origin) { int originId = getCityId(origin); queue.add(new Node (originId, 0)); distance[originId] = 0; int current, adj, weight; while (!queue.isEmpty()) { current = queue.poll().id; if (visited[current]) { continue; } visited[current] = true; for (Node node : adjList.get(current)) { adj = node.id; weight = node.weigth; if (!visited[adj]) { if (distance[current] + weight < distance[adj]) { distance[adj] = distance[current] + weight; previous[adj] = current; queue.add(new Node (adj, distance[adj])); } } } } } public void calculateShortestPath(String destination) { int id = getCityId(destination); if (previous[id] != -1) { calculateShortestPath(getCityName(previous[id])); } this.shortestPath.add(destination); } ********************************* private void colorear() { int color = 1; int nodo; int j; this.colorMax = 1; for (int i = 0; i < this.graph.V; i++) this.nodosColoreados[i] = 0; nodosColoreados[this.graph.vertices.get(0).node] = color; // coloreo el primer nodo de la lista for (int i = 1; i < this.graph.V; i++) { nodo = this.graph.vertices.get(i).node; this.nodosColoreados[nodo] = color; j = 0; while (j < this.graph.V) { if (nodo != j) { if((this.graph.vertices.get(j).neighbors.contains(nodo) || this.graph.vertices.get(nodo).neighbors.contains(j)) && this.nodosColoreados[nodo] == this.nodosColoreados[j]) { color++; if (color > colorMax) colorMax = color; this.nodosColoreados[nodo] = color; j = -1; } } j++; } color = 1; } } ***************************** prim *********** // A Java program for Prim's Minimum Spanning Tree (MST) algorithm. // The program is for adjacency matrix representation of the graph import java.util.*; import java.lang.*; import java.io.*; class MST { // Number of vertices in the graph private static final int V = 5; // A utility function to find the vertex with minimum key // value, from the set of vertices not yet included in MST int minKey(int key[], Boolean mstSet[]) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v < V; v++) if (mstSet[v] == false && key[v] < min) { min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST stored in // parent[] void printMST(int parent[], int graph[][]) { System.out.println("Edge Weight"); for (int i = 1; i < V; i++) System.out.println(parent[i] + " - " + i + " " + graph[i][parent[i]]); } // Function to construct and print MST for a graph represented // using adjacency matrix representation void primMST(int graph[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in cut int key[] = new int[V]; // To represent set of vertices not yet included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i < V; i++) { key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. key[0] = 0; // Make key 0 so that this vertex is // picked as first vertex parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (int count = 0; count < V - 1; count++) { // Pick thd minimum key vertex from the set of vertices // not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the adjacent // vertices of the picked vertex. Consider only those // vertices which are not yet included in MST for (int v = 0; v < V; v++) // graph[u][v] is non zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) { parent[v] = u; key[v] = graph[u][v]; } } // print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution t.primMST(graph); } } **** floyd *** /** Numero de nodos del grafo */ private int numNodos; /** Matriz de adyacencia, para almacenar los arcos del grafo */ private int[][] arcos = new int[TAM][TAM]; /** Matriz de Camino (Warshall - Path) */ private boolean[][] warshallC = new boolean[TAM][TAM]; public void warshall() { int i, j, k; // Obtener la matriz de adyacencia en P for (i = 0; i < numNodos; i++) for (j = 0; j < numNodos; j++) warshallC[i][j] = (arcos[i][j] != INFINITO); // Iterar for (k = 0; k < numNodos; k++) for (i = 0; i < numNodos; i++) for (j = 0; j < numNodos; j++) warshallC[i][j] = (warshallC[i][j] || (warshallC[i][k] && warshallC[k][j])); }