[그래프] 인접 리스트(adjency list) 코드 구현 C++

C++ 그래프 인접 리스트(adjency list) vector 구현

 

linkedlist made by vector in cpp

C++에서 벡터를 이용해 인접리스트를 쉽게 만들 수 있다.

 

vector<int> map[node개수] 
vector<int> map[시작노드].push_back(연결노드)

 

 

인접리스트 노드

 

 

 

예를 들어 위 그림처럼 단방향그래프로

1번 정점에서 갈 수 있는 정점이 2, 3, 4 라면

map[1].push_back(2)

map[1].push_back(3)

map[1].push_back(4)

를 해주면 된다.

 

 

 

 

 

현재 노드에서 갈 수 있는 다음 노드를 선택 하는 방법

for(int i=0; i<map[현재노드].size(); i++){
	//현재 노드에서 갈 수 있는 노드를 선택 하는 방법
	int next_node = map[현재노드][i];
}

이렇게 노드를 선택해주면 DFS나 BFS에 활용할 수 있다.

 

 

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <math.h>
using namespace std;
int ch[30], cnt=0, n, path[30],p1=0;
vector<int> map[30];

void DFS(int v){
	if(v==n){
		
		for(int i=0; path[i]!=0; i++){
			printf("%d ",path[i]);
		}
		printf("\n");
		cnt++;
	}
	else{
		for(int i=0; i<map[v].size(); i++){
			int vv = map[v][i];
			if(ch[vv]==0){
				ch[vv]=1;
				path[p1++]=vv;
				DFS(vv);
				p1--;
				ch[vv]=0;
				path[p1]=0;
			}
			
		}
		
	}
	
}
int main() {
	//freopen("input.txt.txt","rt",stdin);
	int m,i,j,a,b;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	path[p1++]=1;
	ch[1] = 1;
	DFS(1);
	
	printf("%d",cnt);
}