Posted By

medikgt on 07/19/09


Tagged

graph transversal


Versions (?)

Who likes this?

2 people have marked this snippet as a favorite

sailtsaogmailcom
khouser


Breadth First Search


 / Published in: C++
 

  1. #include <iostream>
  2. #include <limits>
  3. #include <map>
  4. #include <list>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. const int INFINITY = INT_MAX;
  10.  
  11. enum Color { WHITE, GRAY, BLACK };
  12.  
  13. class Vertex
  14. {
  15. public:
  16. Vertex();
  17. Vertex(char id);
  18. ~Vertex();
  19. char Vertex::getId() const;
  20. void Vertex::setId(char arg);
  21.  
  22. bool operator <(const Vertex& rhs) const
  23. {
  24. return id < rhs.id;
  25. }
  26.  
  27. private:
  28. char id;
  29. };
  30.  
  31. Vertex::Vertex(): id('0')
  32. {}
  33.  
  34. Vertex::Vertex(char id): id(id)
  35. {}
  36.  
  37. Vertex::~Vertex()
  38. {
  39. }
  40.  
  41. char Vertex::getId() const
  42. {
  43. return id;
  44. }
  45.  
  46. void Vertex::setId(char arg)
  47. {
  48. id = arg;
  49. }
  50.  
  51. int main()
  52. {
  53. //created the vertices
  54. Vertex r('r');
  55. Vertex s('s');
  56. Vertex t('t');
  57. Vertex u('u');
  58. Vertex v('v');
  59. Vertex w('w');
  60. Vertex x('x');
  61. Vertex y('y');
  62.  
  63. //use maps for keeping track of color, distance and parents
  64. map< Vertex , Color> color;
  65. color[r] = WHITE;
  66. color[s] = WHITE;
  67. color[t] = WHITE;
  68. color[u] = WHITE;
  69. color[v] = WHITE;
  70. color[w] = WHITE;
  71. color[x] = WHITE;
  72. color[y] = WHITE;
  73.  
  74. map< Vertex , int> distance;
  75. distance[r] = INFINITY;
  76. distance[s] = INFINITY;
  77. distance[t] = INFINITY;
  78. distance[u] = INFINITY;
  79. distance[v] = INFINITY;
  80. distance[w] = INFINITY;
  81. distance[x] = INFINITY;
  82. distance[y] = INFINITY;
  83.  
  84. map< Vertex , char> parent;
  85. parent[r] = '0';
  86. parent[s] = '0';
  87. parent[t] = '0';
  88. parent[u] = '0';
  89. parent[v] = '0';
  90. parent[w] = '0';
  91. parent[x] = '0';
  92. parent[y] = '0';
  93.  
  94. //create the adj lists
  95. list<Vertex> adj_r;
  96. list<Vertex> adj_s;
  97. list<Vertex> adj_t;
  98. list<Vertex> adj_u;
  99. list<Vertex> adj_v;
  100. list<Vertex> adj_w;
  101. list<Vertex> adj_x;
  102. list<Vertex> adj_y;
  103.  
  104. adj_r.push_back(s);
  105. adj_r.push_back(v);
  106.  
  107. adj_s.push_back(r);
  108. adj_s.push_back(w);
  109.  
  110. adj_t.push_back(w);
  111. adj_t.push_back(x);
  112. adj_t.push_back(u);
  113.  
  114. adj_u.push_back(t);
  115. adj_u.push_back(x);
  116. adj_u.push_back(y);
  117.  
  118. adj_v.push_back(r);
  119.  
  120. adj_w.push_back(s);
  121. adj_w.push_back(t);
  122. adj_w.push_back(x);
  123.  
  124. adj_x.push_back(w);
  125. adj_x.push_back(t);
  126. adj_x.push_back(y);
  127. adj_x.push_back(u);
  128.  
  129. adj_y.push_back(x);
  130. adj_y.push_back(u);
  131.  
  132. //map vertices to corresponding lists
  133. map< Vertex , list<Vertex> > adj;
  134. adj[r] = adj_r;
  135. adj[s] = adj_s;
  136. adj[t] = adj_t;
  137. adj[u] = adj_u;
  138. adj[v] = adj_v;
  139. adj[w] = adj_w;
  140. adj[x] = adj_x;
  141. adj[y] = adj_y;
  142.  
  143. //other objects
  144. queue<Vertex> q;
  145. Vertex currentVertex;
  146. Vertex currentDecescendant;
  147.  
  148. //start algorithm
  149. color[s] = GRAY;
  150. distance[s] = 0;
  151. parent[s] = NULL;
  152.  
  153. q.push(s);
  154.  
  155. //in while loop
  156. while( !q.empty() )
  157. {
  158. //dequeue
  159. currentVertex = q.front();
  160. q.pop();
  161.  
  162. //for each currentDecescendant in adj[currentVertex]
  163. list<Vertex>::iterator it;
  164. for(it = adj[currentVertex].begin(); it != adj[currentVertex].end(); it++)
  165. {
  166. currentDecescendant.setId( it->getId() );
  167.  
  168. if( color[currentDecescendant]==WHITE )
  169. {
  170. color[currentDecescendant] = GRAY;
  171. distance[currentDecescendant] = distance[currentVertex] + 1;
  172. parent[currentDecescendant] = currentVertex.getId();
  173.  
  174. q.push(currentDecescendant);
  175. }
  176. }
  177.  
  178. color[currentVertex] = BLACK;
  179. }
  180.  
  181. cout << "distance[r]: " << distance[r] <<endl;
  182. cout << "distance[s]: " << distance[s] <<endl;
  183. cout << "distance[t]: " << distance[t] <<endl;
  184. cout << "distance[u]: " << distance[u] <<endl;
  185. cout << "distance[v]: " << distance[v] <<endl;
  186. cout << "distance[w]: " << distance[w] <<endl;
  187. cout << "distance[x]: " << distance[x] <<endl;
  188. cout << "distance[y]: " << distance[y] <<endl;
  189.  
  190. cout << endl;
  191.  
  192. cout << "parent[r]: " << parent[r] <<endl;
  193. cout << "parent[s]: " << parent[s] <<endl;
  194. cout << "parent[t]: " << parent[t] <<endl;
  195. cout << "parent[u]: " << parent[u] <<endl;
  196. cout << "parent[v]: " << parent[v] <<endl;
  197. cout << "parent[w]: " << parent[w] <<endl;
  198. cout << "parent[x]: " << parent[x] <<endl;
  199. cout << "parent[y]: " << parent[y] <<endl;
  200.  
  201. cout << endl;
  202.  
  203. char travaller = 'u';
  204. char source = 's';
  205.  
  206. while(travaller!=source)
  207. {
  208. cout << parent[travaller];
  209. travaller = parent[travaller];
  210. }
  211.  
  212. return 0;
  213. }

Report this snippet  

You need to login to post a comment.