DFS e BFS

gistfile1.cpp

/**
 * search.cpp
 *
 *  Created on: Nov 28, 2010
 *      Author: blabos 
 */
#include <iostream>
#include <queue>
#include <stack>


using namespace std;


const int ord   = 6;
const int white = 0;
const int gray  = 1;
const int black = 2;


typedef int adj_mat_t[ord][ord];


void print_matrix(adj_mat_t m) {
    cout << "matriz de adjacencia:" << endl;
    for (int i = 0; i < ord; i++) {
        for (int j = 0; j < ord; j++) {
            cout << " " << m[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

void print_vector(int* v, int len) {
    cout << "cores:    ";
    for (int i = 0; i < len; i++) {
        cout  << v[i] << " ";
    }
    cout << endl;
}

void print_stack(stack<int> s) {
    cout << "pilha:    ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

void print_queue(queue<int> q) {
    cout << "fila:     ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

/**
 * Meu grafo:
 * 
 *          0
 *         / \ 
 *        5   1
 *        |   |
 *        4   2
 *         \ /
 *          3
 *          
 */
void init_graph(adj_mat_t graph) {
    for (int i = 0; i < ord; i++) {
        for (int j = 0; j < ord; j++) {
            graph[i][j] = 0;
        }
    }
    
    graph[0][1] = 1;
    graph[0][5] = 1;
    graph[1][0] = 1;
    graph[1][2] = 1;
    graph[2][1] = 1;
    graph[2][3] = 1;
    graph[3][2] = 1;
    graph[3][4] = 1;
    graph[4][3] = 1;
    graph[4][5] = 1;
    graph[5][4] = 1;
    graph[5][0] = 1;
}


/**
 * Depth first search
 */
bool dfs(adj_mat_t graph, int start, int target) {
    int color[ord];
    stack<int> aux_stack;
    
    for (int i = 0; i < ord; i++) {
        color[i] = white;
    }
    
    print_vector(color, ord);
    
    color[start] = gray;
    aux_stack.push(start);
    
    while (!aux_stack.empty()) {
        cout << endl;
        
        print_vector(color, ord);
        print_stack(aux_stack);
        
        int u = aux_stack.top();
        aux_stack.pop();
        
        cout << "no atual: " << u << endl;
        
        if (u == target) return true;
        
        for (int v = 0; v < ord; v++) {
            if (graph[u][v] == 1 && color[v] == white) {
                color[v] = gray;
                aux_stack.push(v);
            }
        }
        
        color[u] = black;
    }
    return false;
}


/**
 * Breadth first search
 */
bool bfs(adj_mat_t graph, int start, int target) {
    int color[ord];
    queue<int> aux_queue;
    
    for (int i = 0; i < ord; i++) {
        color[i] = white;
    }
    
    print_vector(color, ord);
    
    color[start] = gray;
    aux_queue.push(start);
    
    while (!aux_queue.empty()) {
        cout << endl;
        
        print_vector(color, ord);
        print_queue(aux_queue);
        
        int u = aux_queue.front();
        aux_queue.pop();
        
        cout << "no atual: " << u << endl;
        
        if (u == target) return true;
        
        for (int v = 0; v < ord; v++) {
            if (graph[u][v] == 1 && color[v] == white) {
                color[v] = gray;
                aux_queue.push(v);
            }
        }
        
        color[u] = black;
    }
    return false;
}

int main(int argc, char** argv) {
    adj_mat_t graph;
    
    init_graph(graph);
    
    print_matrix(graph);
    
    cout << "dfs: " << dfs(graph, 0, 3) << endl;
    cout << endl;
    cout << "bfs: " << bfs(graph, 0, 3) << endl;
    
    return 0;
}