bfs,dfs,인접행렬,인접리스트(c++)

● 인접행렬

<장점>

- 구현이 빠르다.

- 노드가 서로 연결되어 있는지 확인이 쉽다.

<단점>

- 특정 노드에 연결된 모든 노드를 검색할때,adj[i][1]~adj[i][v]를 전부 확인해야한다.

- 전체 노드 탐색시 시간복잡도가 O(V^2) 이다.

#include <iostream>
using namespace std;

int N,M;
int adj[10][10];
int main() {
    cin >> n >> m;
    for (int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        adj[a][b] = 1;
        adj[b][a] = 1;
    }
}

 

● 인접리스트

<장점>

- 특정 노드에 연결된 노드 바로 검색 가능

<단점>

- 노드가 서로 연결되어 있는지 확인이 오래걸린다.(특정노드가 검색노드 갖고있는지 리스트 탐색해야함)

#include <iostream>
using namespace std;

int n,m;
vector<int> adj[10];
int main(){
    cin>>n>>m;
    for (int i=0;i<n;i++){
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
}

 

dfs

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 1001;
bool visit[MAX];
vector<int> adj[MAX];
queue<int> Q;

void DFS(int cur){
    visit[cur] = true;
    for (int i=0; i<adj[cur].size();i++){
        int next = adj[cur][i]; // 현재노드 연결된 다음노드 next에 저장
        if(visit[next]) continue; // 방문했다면 그 다음 노드로
        DFS(next); // 방문하지 않았다면 DFS 탐색
    }
}

int main() {
    int n,m,v;
    cin >> n >> m >> v;
    
    for(int i=0;i<m;i++)
    {
        int s,e;
        cin >> s >> e;
        adj[s].push_back(e);
        adj[e].push_back(s);
    }
    
    for(int i=1;i<=n;i++)
    {
        sort(adj[i].begin(),adj[i].end());
    }
    
    DFS(v);
}

 

 

bfs

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 1001;
bool visit[MAX];
vector<int> adj[MAX];
queue<int> Q;

void BFS(int start){
    memset(visit,false,sizeof(visit));
    visit[start] = true;
    Q.push(start);
    
    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        for(int i=0; i<adj[x].size(); i++){
            int next = adj[x][i];
            if(!visit[next]){
                visit[next] = true;
                Q.push(next);
            }
        }
    }
}

int main(){
    int n, m, v;
    cin >> n >> m >> v;
    
    for (int i=0; i<m; i++){
        int s, e;
        cin >> s >> e;
        adj[s].push_back(e);
        adj[e].push_back(s);
    }
    
    for(int i=1; i<=n; i++){ //선택사항(인접노드 순차방문 위함)
        sort(adj[i].begin(),adj[i].end()); 
    }
    
    BFS(v);
}

 

 

 

 

 

 

 

 

내용 출처https://seohyun0120.tistory.com/entry/C-BFS%EC%99%80-DFS-%EC%9D%B8%EC%A0%91%ED%96%89%EB%A0%AC%EA%B3%BC-%EC%9D%B8%EC%A0%91%EB%A6%AC%EC%8A%A4%ED%8A%B8

(C++) BFS와 DFS, 인접행렬과 인접리스트