Este proyecto intentara crear una red de usuarios de XO, para que esten comunicados de varias formas posibles, utilizando tecnologías estándares.
De la lista seleccionamos "svn:externals".
DFS(int inicio, Grafo g, int*& visitados){
visitados[inicio] = 1;
listaAdyacentes = obtenerListaAdyacentes(g, inicio);
while(!esVacia(listaAdyacentes){
w = listaPrimero(listaAdyacentes);
listaAdyacentes = listaResto(listaAdyacentes);
if(!visitados[w]){
!visitados[w] = 1;
DFS(w, g);
}
}
}
void Recorrido_DFS(Grafo g){
int n = cantidadNodos(g);
for(i=0; i
}
for(i=0; i
DFS(i, g, visitados);
{
}
}
BFS(grafo G, nodo_fuente s)
{
// recorremos todos los vértices del grafo inicializándolos a NO_VISITADO,
// distancia INFINITA y padre de cada nodo NULL
for u ∈ V[G] do
{
estado[u] = NO_VISITADO;
distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */
padre[u] = NULL;
}
estado[s] = VISITADO;
distancia[s] = 0;
Encolar(Q, s);
while !vacia(Q) do
{
// extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes
u = extraer(Q);
for v ∈ adyacencia[u] do
{
if estado[v] == NO_VISITADO then
{
estado[v] = VISITADO;
distancia[v] = distancia[u] + 1;
padre[v] = u;
Encolar(Q, v);
}
}
}
}
El algoritmo de Prim
Es un algoritmo de la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.PRIM (Grafo G, nodo_fuente s)
// inicializamos todos los nodos del grafo. La distancia la ponemos a infinito
// y el padre de cada nodo a NULL
for each u ∈ V[G] do
distancia[u] = INFINITO
padre[u] = NULL
distancia[s]=0
//encolamos todos los nodos del grafo
Encolar(cola, V[G])
while cola != 0 do
// OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición
// de Cola de prioridad
u = extraer_minimo(cola)
for v ∈ adyacencia[u] do
if ((v ∈ cola) && (distancia[v] > peso(u, v)) do
padre[v] = u
distancia[v] = peso(u, v)
