인접행렬과 인접리스트 탐색

 

그래프를 표현하는 방법 2가지

(컴퓨터에게 정점-간선으로 연결된 그래프가 있다고 알려주는 것)

- 인접행렬 : 2차원 배열을 기반으로 그래프 표현

- 인접리스트 : 연결리스트를 기반으로 그래프 표현

 

1. 0번부터 방문 안한 노드를 찾고 해당 노드부터 방문한다.

2. 연결된 노드를 이어서 방문한다.

3. 방문한 노드는 다시 방문하지 않는다.

 

인접행렬을 기반으로 탐색하기

- 2차원 배열 이용

//인접행렬 
#include <bits/stdc++.h>
using namespace std;

const int V=10;
bool a[V][V], visited[V];           //0으로 초기화

void go(int from){
	visited[from] =1;
	cout << from << "\n";
	
	for(int i=0; i<V; i++){
		if(visited[i]) continue;
		if(a[from][i]){
			go(i);
		}
	}
}

int main(){
	//양방향 간선 표기 
	a[1][2]=1; a[2][1]=1;
	a[1][3]=1; a[3][1]=1;
	a[3][4]=1; a[4][3]=1;
	
	for(int i=0; i<V; i++){
		for(int j=0; j<V; j++){
			if(a[i][j] && visited[i]==0){
				go(i);
			}
		}
	}
	return 0;
}

 

 

인접리스트를 기반으로 탐색하기

- vector이용 

(list보다 vector 이용하는게 더 편함)

//인접리스트
#include <bits/stdc++.h>
using namespace std;

const int V=10;
vector<int> adj[V];         //인접 리스트 표현 
bool visited[V];            //방문한 정점인지

void go(int vertex){
	visited[vertex]=1;
	cout << vertex << "\n";
	
	for(int there : adj[vertex]){
        if(visited[there]) continue;
        go(there);
    } 

}

int main(){
	
	//양방향 간선에 대한 표기 
	adj[1].push_back(2); adj[2].push_back(1);
	adj[1].push_back(3); adj[3].push_back(1);
	adj[3].push_back(4); adj[4].push_back(3);
	
	//방문 안한 노드 순차적 탐색
	for(int i=0; i<V; i++){
		if(adj[i].size() !=0 && visited[i]==0){
			go(i);
		}
	} 
		
	return 0;
}

---

인접행렬과 인접 리스트의 차이

 

1. 공간 복잡도

- 인접행렬 : O(V^2)

- 인접리스트 : O( V+E )

(리스트에 연결된 정점만 들어가기 때문에)

---

2. 시간 복잡도

▶ 간선 1개 찾기

- 인접행렬 : O(1)

- 인접리스트 : O(V)

 

▶ 모든 간선 찾기

- 인접행렬 : O(V^2)

- 인접리스트 : O(V+E)

 

---

그래프가 희소(sparse)할 때는 인접리스트
그래프가 조밀(dense)할 때는 인접행렬