자료구조 공부기록 <그래프 표현: 인접 행렬 & 인접 리스트>

자료구조에서 그래프란?

그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어집니다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 합니다.

그래프 표현하는 두 방식을 소개시켜줄려고 한다.

1. 인접행렬

알아둬야 할 그래프 용어 인접(adjacency): 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기합니다.
인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냅니다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표입니다. 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장합니다. 예를 들면 장소끼리 연결되있다면 서로의 거리를 입력해놔도 좋습니다.

윗 왼쪽 그래프를 인접행렬로 표현을 한것이다.

• [1][2] = 1 , 1->2 이렇게 표현을 할수가있다
• [2][1] = 0 , 2->1 가는 방향이 없기 때문에 값을 0으로 표현한다.

인접 행렬은 언제 사용할까?

한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이합니다.
예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어 있는지 바로 확인할 수 있습니다.
가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됩니다.

인접행렬 구현:

class GraphWithAdjacencyMatrix {
  //graph의 constructor를 구현합니다.
  constructor() {
    this.matrix = [];
  }
  //vertex를 추가합니다.
  addVertex() {
    const currentLength = this.matrix.length;
    for (let i = 0; i < currentLength; i++) {
      this.matrix[i].push(0);
    }
    this.matrix.push(new Array(currentLength + 1).fill(0));
  }
  //vertex를 탐색합니다.
  //this.matrix에 vertex가 존재한다면 true를 리턴하고, 반대의 경우라면 false를 리턴합니다.
  contains(vertex) {

    return !!this.matrix[vertex];
  }
  //vertex와 vertex를 이어주는 edge를 추가합니다.
  addEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    // this.matrix[from][to]의 값을 1로 바꿔줘서 edge로 연결이 되어 있음을 표시합니다.
    this.matrix[from][to] = 1;
  }
  
  hasEdge(from, to) {
    return !!this.matrix[from][to];
  }
  // from vertex와 to vertex 사이에 관련이 없다면, edge를 제거 합니다.
  removeEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
    if (
      from > currentLength ||to > currentLength ||from < 0 ||to < 0) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    this.matrix[from][to] = 0;
  }
}

1. 인접리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현합니다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있습니다. 위 그래프를 인접 리스트로 표현하면 다음 그림과 같습니다.

오른쪽의 인접 리스트에서, adj[1]에 있는 세 노드의 순서는 의미가 없습니다. 2,3,4 순이 아닌 3,2,4 순이 되어도 무관하지만, 보기 좋도록 하기 위해 오름차순으로 저장해 놓은 것을 뿐입니다. 따라서, adj[1]의 노드 2와 노드 3사이에 화살표가 있는 것을 노드 2와 노드 3사이에 간선이 있다는 의미가 아니라 단순히, vector에 노드 3이 노드 2보다 나중에 push_back 되었기 때문이라고 이해하면 됩니다.

무방향 인접리스트 그래프:

인접 리스트는 언제 사용할까?

메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용합니다.
인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지합니다.

인접리스트 구현:(무방향)

// undirected graph (무향 그래프)
// adjacency list (인접 리스트)
class GraphWithAdjacencyList {
	constructor() {
		this.vertices = {};
	}

	addVertex(vertex) {
		// TODO: 정점을 추가합니다.
		// 넘겨받은 인자(정점)은 키가 되며, 빈 배열을 값으로 할당합니다.
		// 이미 존재하는 정점이라면, 덮어 씌워지지 않아야 합니다.
    if(!this.vertices[vertex]){
      this.vertices[vertex] = [];
    }
	}

	contains(vertex) {
		// 인자로 넘겨받은 정점의 존재여부를 반환합니다.
		return !!this.vertices[vertex];
	}

	addEdge(fromVertex, toVertex) {
		// TODO: 간선을 추가합니다.
		// - fromVertex의 인접 리스트에 toVertex를 추가하고
		// - toVertex의 인접 리스트에 fromVertex를 추가합니다.
		// 넘겨받은 2개의 정점 모두 존재하는 정점이어야 합니다.

		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			return;
		}

		if (!this.hasEdge(fromVertex, toVertex)) {
      this.vertices[fromVertex].push(toVertex);
		}

		if (!this.hasEdge(toVertex, fromVertex)) { // 방향 있는 인접 리스트 를 구현하고 싶으면 이부분은 지워주세요.
       this.vertices[toVertex].push(fromVertex);
		}
	}

	hasEdge(fromVertex, toVertex) {
		// 만약 정점(fromVertex)이 존재하지 않는다면
		if (!this.contains(fromVertex)) {
			// false를 반환합니다
			return false;
		}
		// 존재한다면 해당 정점의 리스트에 toVertex가 포함되어있는지 반환합니다
		return !!this.vertices[fromVertex].includes(toVertex);
	}

	removeEdge(fromVertex, toVertex) {
		// TODO: 간선을 삭제합니다.
		// 인자로 넘겨받은 두 정점이 모두 존재한다면
		// - fromVertex의 인접 리스트에 있는 toVertex를 삭제하고
		// - toVertex의 인접 리스트에 있는 fromVertex를 삭제합니다.

		if (!this.contains(fromVertex) || !this.contains(toVertex)) {
			return;
		}

		if (this.hasEdge(fromVertex, toVertex)) {
			const index = this.vertices[fromVertex].indexOf(toVertex);
			this.vertices[fromVertex].splice(index, 1);
		}
		// TODO:  두번째 정점의 인접 리스트에 첫번째 정점이 있을 경우
    if (this.hasEdge(toVertex, fromVertex)) {
			const index = this.vertices[toVertex].indexOf(fromVertex);
			this.vertices[toVertex].splice(index, 1);
		}
	}

	removeVertex(vertex) {
		// TODO: 정점을 삭제합니다.
		// 인자로 넘겨받은 정점(A)이 존재한다면
		// - 이 정점(A)을 삭제함은 물론,
		// - 다른 모든 정점들의 리스트를 순회하며 넘겨받은 정점(A)과 이어져 있는 간선을 제거합니다
		if (this.contains(vertex)) {
      Object.keys(this.vertices).forEach((ele)=>{
        if(ele!==vertex){
        this.removeEdge(vertex,ele);
        }
      })
      delete this.vertices[vertex]; 
		}
	}
}