package grafos;
class MST
{
private static final int V=5;
int minKey(int key[], Boolean mstSet[])
{
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;
}
void printMST(int parent[], int n, int graph[][])
{
System.out.println("Edge \tWeight");
for (int i = 1; i < V; i++)
System.out.println(parent[i]+" - "+ i+"\t"+
graph[i][parent[i]]);
}
void primMST(int graph[][])
{
int parent[] = new int[V];
int key[] = new int [V];
Boolean mstSet[] = new Boolean[V];
for (int i = 0; i < V; i++)
{
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V-1; count++)
{
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v]!=0 && mstSet[v] == false &&
graph[u][v] < key[v])
{
parent[v] = u;
key[v] = graph[u][v];
}
}
printMST(parent, V, graph);
}
public static void main (String[] args)
{
/*
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
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}};
t.primMST(graph);
}
}
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
package grafos;
class ShortestPath
{
static final int V=9;
int minDistance(int dist[], Boolean sptSet[])
{
int min = Integer.MAX_VALUE, min_index=-1;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
{
min = dist[v];
min_index = v;
}
return min_index;
}
void printSolution(int dist[], int n)
{
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; i++)
System.out.println(i+" tt "+dist[i]);
}
void dijkstra(int graph[][], int src)
{
int dist[] = new int[V];
Boolean sptSet[] = new Boolean[V];
for (int i = 0; i < V; i++)
{
dist[i] = Integer.MAX_VALUE;
sptSet[i] = false;
}
dist[src] = 0;
for (int count = 0; count < V-1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v]!=0 &&
dist[u] != Integer.MAX_VALUE &&
dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
printSolution(dist, V);
}
public static void main (String[] args)
{
int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
ShortestPath t = new ShortestPath();
t.dijkstra(graph, 0);
}
}
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
package grafos;
import java.util.*;
class Graph
{
class Edge implements Comparable<Edge>
{
int src, dest, weight;
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight;
}
};
class subset
{
int parent, rank;
};
int V, E;
Edge edge[];
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[E];
for (int i=0; i<e; ++i)
edge[i] = new Edge();
}
int find(subset subsets[], int i)
{
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
void KruskalMST()
{
Edge result[] = new Edge[V];
int e = 0;
int i = 0;
for (i=0; i<V; ++i)
result[i] = new Edge();
Arrays.sort(edge);
subset subsets[] = new subset[V];
for(i=0; i<V; ++i)
subsets[i]=new subset();
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0;
while (e < V - 1)
{
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
System.out.println("Following are the edges in " +
"the constructed MST");
for (i = 0; i < e; ++i)
System.out.println(result[i].src+" -- " +
result[i].dest+" == " + result[i].weight);
}
public static void main (String[] args)
{
/*
10
0--------1
| \ |
6| 5\ |15
| \ |
2--------3
4 */
int V = 4;
int E = 5;
Graph graph = new Graph(V, E);
// add edge 0-1
graph.edge[0].src = 0;
graph.edge[0].dest = 1;
graph.edge[0].weight = 10;
// add edge 0-2
graph.edge[1].src = 0;
graph.edge[1].dest = 2;
graph.edge[1].weight = 6;
// add edge 0-3
graph.edge[2].src = 0;
graph.edge[2].dest = 3;
graph.edge[2].weight = 5;
// add edge 1-3
graph.edge[3].src = 1;
graph.edge[3].dest = 3;
graph.edge[3].weight = 15;
// add edge 2-3
graph.edge[4].src = 2;
graph.edge[4].dest = 3;
graph.edge[4].weight = 4;
graph.KruskalMST();
}
}
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
package grafos;
class BinarySearchTree
{
/* Clase que contiene el elemento secundario
izquierdo y derecho del nodo actual y el valor clave*/
class Node
{
int key;
Node left, right;
public Node(int item)
{
key = item;
left = right = null;
}
}
// Ra�z de BST
Node root;
// Constructor
BinarySearchTree()
{
root = null;
}
// Este m�todo llama principalmente a deleteRec()
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* Una funci�n recursiva para insertar una nueva clave en BST */
Node deleteRec(Node root, int key)
{
/* Caso base: Si el �rbol est� vac�o */
if (root == null) return root;
/* De lo contrario, recorrer por el �rbol */
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
// Si la clave es la misma que la de la ra�z, entonces este es el nodo.
// para ser eliminado
else
{
// nodo con un solo hijo o ning�n hijo
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// nodo con dos hijos: obtener el sucesor inorder (m�s peque�o
// en el sub�rbol derecho)
root.key = minValue(root.right);
// eliminar el sucesor in-orden
root.right = deleteRec(root.right, root.key);
}
return root;
}
int minValue(Node root)
{
int minv = root.key;
while (root.left != null)
{
minv = root.left.key;
root = root.left;
}
return minv;
}
// Este m�todo llama principalmente a insertRec()
void insert(int key)
{
root = insertRec(root, key);
}
/* Una funci�n recursiva para insertar una nueva clave en BST */
Node insertRec(Node root, int key)
{
/* si el arbol esta vacio, retorna un nuevo node */
if (root == null)
{
root = new Node(key);
return root;
}
/* recorre recursivamente el arbol hacia abajo */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* returna los punteros del arbol */
return root;
}
// This method mainly calls InorderRec()
void inorder()
{
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root)
{
if (root != null)
{
inorderRec(root.left);
System.out.print(root.key + " ");
inorderRec(root.right);
}
}
// Driver Program to test above functions
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree();
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println("Inorder traversal of the given tree");
tree.inorder();
System.out.println("\nDelete 20");
tree.deleteKey(20);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println("\nDelete 30");
tree.deleteKey(30);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
System.out.println("\nDelete 50");
tree.deleteKey(50);
System.out.println("Inorder traversal of the modified tree");
tree.inorder();
}
}
