Hello BFS, Hello DFS!
本帖最后由 andalousie 于 2014-2-25 10:01 编辑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 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*;
for (i = 0; i < _n; ++i)
_A = new int;
for (i = 0; i < _n; ++i)
for (j = 0; j < _n; ++j)
_A = 0;
}
Graph::~Graph() {
for (int i = 0; i < _n; ++i)
delete [] _A;
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 == 1);
}
/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int x, int y) {
_A = _A = 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;
/** Initailized all vertices as unexplored */
for (int i = 1; i <= _n; ++i)
explored = false;
/** Push initial vertex to the queue */
Q.enqueue(s);
explored = 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) {
/** adds the vertex w to the queue */
Q.enqueue(w);
/** marks the vertex w as visited */
explored = 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;
int i;
for(i = 0; i <= _n; i++)
visited = false;
s.push(x);
visited = 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) {
s.push(i);
visited = 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 ;
int _top;
};
#endifstack.cc
#include "stack.h"
#include <cassert>
#include <iostream>
void IStack::push (int i)
{
assert (_top < maxStack);
_arr = i;
++_top;
}
int IStack::pop ()
{
assert (_top > 0);
--_top;
return _arr ;
}queue.h
#if !defined (QUEUE_H)
#define QUEUE_H
const int maxPuts=16;
class Queue
{
public:
Queue();
intdequeue();
void enqueue(int x);
bool isEmpty() { return _putIdx == _getIdx; }
private:
int _arr ;
int _putIdx;
int _getIdx;
};
#endifqueue.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 =x;
++_putIdx;
}我刚刚参照书上写了一个DAG的拓扑排序
刚刚有点多余的输出，修正了。 支持小甲鱼,赞点鱼币回来下载 是干什么的？？ 路过看看 = = casinosun 发表于 2014-2-8 16:38 static/image/common/back.gif
是干什么的？？
图的搜索，广搜和深搜 路过看看= =！ 做了小改动，把单队列改成循环队列了。 大神太给力啦
页:
[1]