[关闭]
@bintou 2017-12-08T13:49:40.000000Z 字数 1469 阅读 664

图的定义及BFS

Source Code


C++代码.

  1. // Program to print BFS traversal from a given
  2. // source vertex. BFS(int s) traverses vertices
  3. // reachable from s.
  4. #include<iostream>
  5. #include <list>
  6. using namespace std;
  7. // This class represents a directed graph using
  8. // adjacency list representation
  9. class Graph
  10. {
  11. int V; // No. of vertices
  12. // Pointer to an array containing adjacency
  13. // lists
  14. list<int> *adj;
  15. public:
  16. Graph(int V); // Constructor
  17. // function to add an edge to graph
  18. void addEdge(int v, int w);
  19. // prints BFS traversal from a given source s
  20. void BFS(int s);
  21. };
  22. Graph::Graph(int V)
  23. {
  24. this->V = V;
  25. adj = new list<int>[V];
  26. }
  27. void Graph::addEdge(int v, int w)
  28. {
  29. adj[v].push_back(w); // Add w to v’s list.
  30. }
  31. void Graph::BFS(int s)
  32. {
  33. // Mark all the vertices as not visited
  34. bool *visited = new bool[V];
  35. for(int i = 0; i < V; i++)
  36. visited[i] = false;
  37. // Create a queue for BFS
  38. list<int> queue;
  39. // Mark the current node as visited and enqueue it
  40. visited[s] = true;
  41. queue.push_back(s);
  42. // 'i' will be used to get all adjacent
  43. // vertices of a vertex
  44. list<int>::iterator i;
  45. while(!queue.empty())
  46. {
  47. // Dequeue a vertex from queue and print it
  48. s = queue.front();
  49. cout << s << " ";
  50. queue.pop_front();
  51. // Get all adjacent vertices of the dequeued
  52. // vertex s. If a adjacent has not been visited,
  53. // then mark it visited and enqueue it
  54. for (i = adj[s].begin(); i != adj[s].end(); ++i)
  55. {
  56. if (!visited[*i])
  57. {
  58. visited[*i] = true;
  59. queue.push_back(*i);
  60. }
  61. }
  62. }
  63. }
  64. // Driver program to test methods of graph class
  65. int main()
  66. {
  67. // Create a graph given in the above diagram
  68. Graph g(4);
  69. g.addEdge(0, 1);
  70. g.addEdge(0, 2);
  71. g.addEdge(1, 2);
  72. g.addEdge(2, 0);
  73. g.addEdge(2, 3);
  74. g.addEdge(3, 3);
  75. cout << "Following is Breadth First Traversal "
  76. << "(starting from vertex 2) \n";
  77. g.BFS(2);
  78. cout << "\n";
  79. return 0;
  80. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注