Krononberg

bfs graph (C++) 본문

개발 로그/자료구조

bfs graph (C++)

k._. 2024. 2. 9. 06:47
#include <iostream>
#include <list>
#include <queue>

using namespace std;

class Graph{
	int V;
    list<int>*adj;
	
public:
	Graph(int V);
    ~Graph();
    void add_line(int from, int to);
    void bfs(int start);
};


Graph::Graph(int V){
	this->V = V;
	adj = new list<int>[V];
}

Graph::~Graph(){
	delete[] adj;
}

void Graph::add_line(int from, int to){
	adj[from].push_back(to);
}

void Graph::bfs(int start){
	bool *visited = new bool[V]{false};
    
    visited[start] = true;
    queue<int> queue;
    
    queue.push(start);
    
    while(!queue.empty()){
    	int current = queue.front();
        queue.pop();
        cout << current << ' ';
        
        for(auto i = adj[current].begin(); i != adj[current].end(); ++i){
        	if(!visited[*i]){
            	visited[*i] = true;
                queue.push(*i);
            }
        }
    }
    
	delete[] visited;
}


int main(){
	Graph g(5);
    g.add_line(0, 1);
    g.add_line(1, 2);
    g.add_line(2, 3);    
    g.add_line(2, 4);
    g.add_line(4, 1);
    
    g.bfs(0);
    
	return 0;
}

'개발 로그 > 자료구조' 카테고리의 다른 글

binary search (C++)  (0) 2024.02.09
quick sort (C++)  (0) 2024.02.09