C++笔记-基于邻接表的BFS（宽度优先遍历）

落日映苍穹つ 2022-10-10 15:54 90阅读 0赞

这里是基于邻接表的，有向的，具体代码如下：

#include <iostream>
    #include <list>
    
    using namespace std;
    
    
    class Graph
    {
    	int V;
    
    
    	list<int> *adj;
    public:
    	Graph(int V);
    
    
    	void addEdge(int v, int w);
    
    
    	void BFS(int s);
    };
    
    Graph::Graph(int V)
    {
    	this->V = V;
    	adj = new list<int>[V];
    }
    
    void Graph::addEdge(int v, int w)
    {
    	adj[v].push_back(w);
    }
    
    void Graph::BFS(int s)
    {
    
    	bool *visited = new bool[V];
    	for (int i = 0; i < V; i++)
    		visited[i] = false;
    
    
    	list<int> queue;
    
    
    	visited[s] = true;
    	queue.push_back(s);
    
    
    	list<int>::iterator i;
    
    	while (!queue.empty())
    	{
    
    		s = queue.front();
    		cout << s << " ";
    		queue.pop_front();
    
    
    		for (i = adj[s].begin(); i != adj[s].end(); ++i)
    		{
    			if (!visited[*i])
    			{
    				visited[*i] = true;
    				queue.push_back(*i);
    			}
    		}
    	}
    }
    
    
    int main()
    {
    
    	Graph g(4);
    	g.addEdge(0, 1);
    	g.addEdge(1, 2);
    	g.addEdge(0, 3);
    	
    	cout << "Following is Breadth First Traversal " << endl;
    	g.BFS(0);
    
    	getchar();
    	return 0;
    }

程序运行截图如下：

![2021062908414134.png][]

这里的g.BFS(0);代表，从0这个顶点开始。

邻接表是这样的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxNzg0NDI3NjE_size_16_color_FFFFFF_t_70][]

[2021062908414134.png]: /images/20221005/cb4d0daab6df473fba0979fd8cfc00cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxNzg0NDI3NjE_size_16_color_FFFFFF_t_70]: /images/20221005/13872606b859495098fa99b8209c20ac.png