Hello BFS, Hello DFS!

andalousie

Graph_search.cpp

#include <iostream>
#include <ctime>
#include "graph.h"
using namespace std;

int main(){    
        /** Creates a graph with 12 vertices */
    Graph g1(12);

    /** Adds edges to the graph */
    g1.addEdge(1, 2); g1.addEdge(1, 3);
    g1.addEdge(2, 4); g1.addEdge(3, 4);
    g1.addEdge(3, 6); g1.addEdge(4 ,7);
    g1.addEdge(5, 6); g1.addEdge(5, 7);
    clock_t t1;
    t1 = clock();

    /** Explores all vertices findable from vertex 1 */
    g1.BFS(1, 3);
    float diff = (double)(clock() - t1)/CLOCKS_PER_SEC ;
    std::cout << std::endl << "The time taken for Breadth first search: "<< diff << std::endl;
    
    clock_t t2;
    t2 = clock();

    /** Explores all vertices findable from vertex 1 */
    g1.DFS(1, 3);
    float diff2 = (double)(clock() - t2)/CLOCKS_PER_SEC ;
    std::cout << std::endl << "The time taken for Breadth first search: "<< diff2 << std::endl;
} 

graph.h

#if !defined (GRAPH_H)
#define GRAPH_H

/************************************************************

Class Graph represents a Graph [V,E] having vertices V and
edges E.

************************************************************/
class Graph {
    private:
        int    _n;  /// n is the number of vertices in the graph
        int ** _A;  /// A stores the edges between two vertices
    public:
        Graph(int size = 2);
        ~Graph();
        bool isConnected(int, int);
        void addEdge(int x, int y);
        void BFS(int, int);
        void DFS(int, int);
};

#endif

graph.cc

#include <iostream>
#include "graph.h"
#include "queue.h"
#include "stack.h"

Graph::Graph(int size) {
    int i, j;
    if (size < 2) _n = 2;
    else _n = size;
    _A = new int*[_n];
    for (i = 0; i < _n; ++i)
        _A[i] = new int[_n];
    for (i = 0; i < _n; ++i)
        for (j = 0; j < _n; ++j)
            _A[i][j] = 0;
} 

Graph::~Graph() {
    for (int i = 0; i < _n; ++i)
    delete [] _A[i];
    delete [] _A;
} 

/******************************************************
Checks if two given vertices are connected by an edge
@param u vertex
@param v vertex
@return true if connected false if not connected
******************************************************/
bool Graph::isConnected(int x, int y) {
    return (_A[x-1][y-1] == 1);
} 

/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int x, int y) {
    _A[x-1][y-1] = _A[y-1][x-1] = 1;
} 

/*****************************************************
performs Breadth First Search
@param s initial vertex
*****************************************************/
void Graph::BFS(int s, int required) {
    Queue Q;

    /** Keeps track of explored vertices */
    bool *explored = new bool[_n+1];

    /** Initailized all vertices as unexplored */
    for (int i = 1; i <= _n; ++i)
        explored[i] = false;

    /** Push initial vertex to the queue */
    Q.enqueue(s);
    explored[s] = true; /** mark it as explored */
    std::cout << "Breadth first Search starting from vertex ";
    std::cout << s << " : " << std::endl;

    /** Unless the queue is empty */
    while (!Q.isEmpty()) {
        /** Pop the vertex from the queue */
        int v = Q.dequeue();

        if(v == required) break;
                /** display the explored vertices */
        std::cout << v << " ";

        /** From the explored vertex v try to explore all the
        connected vertices */
        for (int w = 1; w <= _n; ++w)

            /** Explores the vertex w if it is connected to v
            and and if it is unexplored */
            if (isConnected(v, w) && !explored[w]) {
                /** adds the vertex w to the queue */
                Q.enqueue(w);
                /** marks the vertex w as visited */
                explored[w] = true;
            }
    }
    std::cout << std::endl;
    delete [] explored;
}

/*****************************************************
performs Depth First Search
@param s initial vertex
*****************************************************/
void Graph::DFS(int x, int required){
    IStack s;
    bool *visited = new bool[_n+1];
    int i;
    for(i = 0; i <= _n; i++)
        visited[i] = false;
    s.push(x);
    visited[x] = true;
    std::cout << "Depth first Search starting from vertex ";
    std::cout << x << " : " << std::endl;
    while(!s.isEmpty()){
        int k = s.pop();
        if(k == required) break;
        std::cout << k << " ";
        for (i = _n; i >= 0 ; --i)
            if (isConnected(k, i) && !visited[i]) {
                s.push(i);
                visited[i] = true;
            }
    }
    std::cout << std::endl;
    delete [] visited;
}

stack.h

#if !defined (STACK_H)
#define STACK_H

const int maxStack=16;

class IStack
{
public:
        IStack():_top(0){}
        void push(int i);
        int pop();
        bool isFull () const { return _top >= maxStack; }
        bool isEmpty () const { return _top == 0; }
private:
        int _arr [maxStack];
        int _top;
};

#endif

stack.cc

#include "stack.h"
#include <cassert>
#include <iostream>

void IStack::push (int i)
{
        assert (_top < maxStack);
        _arr [_top] = i;
        ++_top;
}

int IStack::pop ()
{
        assert (_top > 0);
        --_top;
        return _arr [_top];
}

queue.h

#if !defined (QUEUE_H)
#define QUEUE_H

const int maxPuts=16;

class Queue
{
public:
        Queue();
        int  dequeue();
        void enqueue(int x);
        bool isEmpty() { return _putIdx == _getIdx; }
private:
        int _arr [maxPuts];
        int _putIdx;
        int _getIdx;
};

#endif

queue.cc

#include <cassert>
#include "queue.h"

Queue::Queue()
: _putIdx(0),
  _getIdx(0)
{}

int Queue::dequeue()
{
        assert (_getIdx<_putIdx);
        ++_getIdx;
        return _arr [(_getIdx-1) % maxPuts];
}

void Queue::enqueue(int x)
{
        assert (_putIdx<maxPuts+_getIdx);
        _arr [_putIdx % maxPuts]=x;
        ++_putIdx;
}

我刚刚参照书上写了一个DAG的拓扑排序

andalousie

刚刚有点多余的输出，修正了。

lpppl

支持小甲鱼,赞点鱼币回来下载

casinosun

是干什么的？？

未闻丶花名

路过看看 = =

andalousie

casinosun 发表于 2014-2-8 16:38

                               
登录/注册后可看大图

是干什么的？？

图的搜索，广搜和深搜

未闻丶花名

路过看看= =！

andalousie

做了小改动，把单队列改成循环队列了。

Ayfkm

大神太给力啦