Hello BFS, Hello DFS!

andalousie

Graph_search.cpp

1. #include <iostream>
   
2. #include <ctime>
   
3. #include "graph.h"
   
4. using namespace std;
   
5. 
   
6. int main(){   
   
7.         /** Creates a graph with 12 vertices */
   
8.     Graph g1(12);
   
9. 
   
10.     /** Adds edges to the graph */
    
11.     g1.addEdge(1, 2); g1.addEdge(1, 3);
    
12.     g1.addEdge(2, 4); g1.addEdge(3, 4);
    
13.     g1.addEdge(3, 6); g1.addEdge(4 ,7);
    
14.     g1.addEdge(5, 6); g1.addEdge(5, 7);
    
15.     clock_t t1;
    
16.     t1 = clock();
    
17. 
    
18.     /** Explores all vertices findable from vertex 1 */
    
19.     g1.BFS(1, 3);
    
20.     float diff = (double)(clock() - t1)/CLOCKS_PER_SEC ;
    
21.     std::cout << std::endl << "The time taken for Breadth first search: "<< diff << std::endl;
    
22.    
    
23.     clock_t t2;
    
24.     t2 = clock();
    
25. 
    
26.     /** Explores all vertices findable from vertex 1 */
    
27.     g1.DFS(1, 3);
    
28.     float diff2 = (double)(clock() - t2)/CLOCKS_PER_SEC ;
    
29.     std::cout << std::endl << "The time taken for Breadth first search: "<< diff2 << std::endl;
    
30. }

复制代码

graph.h

1. #if !defined (GRAPH_H)
   
2. #define GRAPH_H
   
3. 
   
4. /************************************************************
   
5. 
   
6. Class Graph represents a Graph [V,E] having vertices V and
   
7. edges E.
   
8. 
   
9. ************************************************************/
   
10. class Graph {
    
11.     private:
    
12.         int    _n;  /// n is the number of vertices in the graph
    
13.         int ** _A;  /// A stores the edges between two vertices
    
14.     public:
    
15.         Graph(int size = 2);
    
16.         ~Graph();
    
17.         bool isConnected(int, int);
    
18.         void addEdge(int x, int y);
    
19.         void BFS(int, int);
    
20.         void DFS(int, int);
    
21. };
    
22. 
    
23. #endif

复制代码

graph.cc

1. #include <iostream>
   
2. #include "graph.h"
   
3. #include "queue.h"
   
4. #include "stack.h"
   
5. 
   
6. Graph::Graph(int size) {
   
7.     int i, j;
   
8.     if (size < 2) _n = 2;
   
9.     else _n = size;
   
10.     _A = new int*[_n];
    
11.     for (i = 0; i < _n; ++i)
    
12.         _A[i] = new int[_n];
    
13.     for (i = 0; i < _n; ++i)
    
14.         for (j = 0; j < _n; ++j)
    
15.             _A[i][j] = 0;
    
16. }
    
17. 
    
18. Graph::~Graph() {
    
19.     for (int i = 0; i < _n; ++i)
    
20.     delete [] _A[i];
    
21.     delete [] _A;
    
22. }
    
23. 
    
24. /******************************************************
    
25. Checks if two given vertices are connected by an edge
    
26. @param u vertex
    
27. @param v vertex
    
28. @return true if connected false if not connected
    
29. ******************************************************/
    
30. bool Graph::isConnected(int x, int y) {
    
31.     return (_A[x-1][y-1] == 1);
    
32. }
    
33. 
    
34. /*****************************************************
    
35. adds an edge E to the graph G.
    
36. @param u vertex
    
37. @param v vertex
    
38. *****************************************************/
    
39. void Graph::addEdge(int x, int y) {
    
40.     _A[x-1][y-1] = _A[y-1][x-1] = 1;
    
41. }
    
42. 
    
43. /*****************************************************
    
44. performs Breadth First Search
    
45. @param s initial vertex
    
46. *****************************************************/
    
47. void Graph::BFS(int s, int required) {
    
48.     Queue Q;
    
49. 
    
50.     /** Keeps track of explored vertices */
    
51.     bool *explored = new bool[_n+1];
    
52. 
    
53.     /** Initailized all vertices as unexplored */
    
54.     for (int i = 1; i <= _n; ++i)
    
55.         explored[i] = false;
    
56. 
    
57.     /** Push initial vertex to the queue */
    
58.     Q.enqueue(s);
    
59.     explored[s] = true; /** mark it as explored */
    
60.     std::cout << "Breadth first Search starting from vertex ";
    
61.     std::cout << s << " : " << std::endl;
    
62. 
    
63.     /** Unless the queue is empty */
    
64.     while (!Q.isEmpty()) {
    
65.         /** Pop the vertex from the queue */
    
66.         int v = Q.dequeue();
    
67. 
    
68.         if(v == required) break;
    
69.                 /** display the explored vertices */
    
70.         std::cout << v << " ";
    
71. 
    
72.         /** From the explored vertex v try to explore all the
    
73.         connected vertices */
    
74.         for (int w = 1; w <= _n; ++w)
    
75. 
    
76.             /** Explores the vertex w if it is connected to v
    
77.             and and if it is unexplored */
    
78.             if (isConnected(v, w) && !explored[w]) {
    
79.                 /** adds the vertex w to the queue */
    
80.                 Q.enqueue(w);
    
81.                 /** marks the vertex w as visited */
    
82.                 explored[w] = true;
    
83.             }
    
84.     }
    
85.     std::cout << std::endl;
    
86.     delete [] explored;
    
87. }
    
88. 
    
89. /*****************************************************
    
90. performs Depth First Search
    
91. @param s initial vertex
    
92. *****************************************************/
    
93. void Graph::DFS(int x, int required){
    
94.     IStack s;
    
95.     bool *visited = new bool[_n+1];
    
96.     int i;
    
97.     for(i = 0; i <= _n; i++)
    
98.         visited[i] = false;
    
99.     s.push(x);
    
100.     visited[x] = true;
     
101.     std::cout << "Depth first Search starting from vertex ";
     
102.     std::cout << x << " : " << std::endl;
     
103.     while(!s.isEmpty()){
     
104.         int k = s.pop();
     
105.         if(k == required) break;
     
106.         std::cout << k << " ";
     
107.         for (i = _n; i >= 0 ; --i)
     
108.             if (isConnected(k, i) && !visited[i]) {
     
109.                 s.push(i);
     
110.                 visited[i] = true;
     
111.             }
     
112.     }
     
113.     std::cout << std::endl;
     
114.     delete [] visited;
     
115. }

复制代码

stack.h

1. #if !defined (STACK_H)
   
2. #define STACK_H
   
3. 
   
4. const int maxStack=16;
   
5. 
   
6. class IStack
   
7. {
   
8. public:
   
9.         IStack():_top(0){}
   
10.         void push(int i);
    
11.         int pop();
    
12.         bool isFull () const { return _top >= maxStack; }
    
13.         bool isEmpty () const { return _top == 0; }
    
14. private:
    
15.         int _arr [maxStack];
    
16.         int _top;
    
17. };
    
18. 
    
19. #endif

复制代码

stack.cc

1. #include "stack.h"
   
2. #include <cassert>
   
3. #include <iostream>
   
4. 
   
5. void IStack::push (int i)
   
6. {
   
7.         assert (_top < maxStack);
   
8.         _arr [_top] = i;
   
9.         ++_top;
   
10. }
    
11. 
    
12. int IStack::pop ()
    
13. {
    
14.         assert (_top > 0);
    
15.         --_top;
    
16.         return _arr [_top];
    
17. }

复制代码

queue.h

1. #if !defined (QUEUE_H)
   
2. #define QUEUE_H
   
3. 
   
4. const int maxPuts=16;
   
5. 
   
6. class Queue
   
7. {
   
8. public:
   
9.         Queue();
   
10.         int  dequeue();
    
11.         void enqueue(int x);
    
12.         bool isEmpty() { return _putIdx == _getIdx; }
    
13. private:
    
14.         int _arr [maxPuts];
    
15.         int _putIdx;
    
16.         int _getIdx;
    
17. };
    
18. 
    
19. #endif

复制代码

queue.cc

1. #include <cassert>
   
2. #include "queue.h"
   
3. 
   
4. Queue::Queue()
   
5. : _putIdx(0),
   
6.   _getIdx(0)
   
7. {}
   
8. 
   
9. int Queue::dequeue()
   
10. {
    
11.         assert (_getIdx<_putIdx);
    
12.         ++_getIdx;
    
13.         return _arr [(_getIdx-1) % maxPuts];
    
14. }
    
15. 
    
16. void Queue::enqueue(int x)
    
17. {
    
18.         assert (_putIdx<maxPuts+_getIdx);
    
19.         _arr [_putIdx % maxPuts]=x;
    
20.         ++_putIdx;
    
21. }

复制代码

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

andalousie

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

lpppl

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

casinosun

是干什么的？？

未闻丶花名

路过看看 = =

andalousie

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

                               
登录/注册后可看大图

是干什么的？？

图的搜索，广搜和深搜

未闻丶花名

路过看看= =！

andalousie

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

Ayfkm

大神太给力啦