[알고리즘] 인접 리스트(adjacency list) 자료구조- JavaScript

인접리스트 자료구조

- 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현

- 메모리를 효율적으로 사용하고 싶을 때 사용

- 구조 : 시작점을 key로, '도착점들의 배열'을 값으로 가지는 객체 형태

 

// 인접리스트 예시 by JavaScript

{
  a: [c, d],     // a에서는 c와 d로 향하는 간선 있음
  b: [a, c, d],  // b에서는 a, c, d로 향하는 간선 있음 
  c : [a],       // c에서는 a로 향하는 간선 있음
  d : [b, c]     // d에서는 b와 c로 향하는 간선 있음
 }

 

코드 작성 포인트

1. 인접 리스트를 객체에 담기 위한 변수 선언

2. 정점을 추가하는 메소드를 구현하되, 이미 있는 정점이면 그대로 놔두기

3. 두 정점 사이 간선을 추가하는 메소드 구현 : 키의 값인 배열에 push 메소드로  요소 추가

4. 두 정점 사이 간선을 삭제하는 메소드 구현  : 배열에서 정점의 인덱스를 찾고, splice 메소드로 해당 요소 삭제

5. 정점을 삭제하는 메소드 구현 (정점과 이어진 간선도 함께 제거)

  - 방법1 : 키의 값인 배열을 모두 순회하여, 삭제하려는 정점에 해당하는 요소를 splice 메소드로 간선을 삭제

  - 방법2 : 삭제하려는 정점과 인접하는 정점들을 순회하여, 간선 삭제 메소드를 사용하여 간선을 삭제

 

코드 구현 (JavaScript)

- undefined와 null을 false 로 변경하기 (Boolean type으로 변경) : 앞에 !!를 붙여주기

- 반복문으로 모든 정점의 값인 배열을 순회하기 : Object.values(객체명) 메소드 사용

 

// undirected graph (무향 그래프) && adjacency list (인접 리스트)

class GraphWithAdjacencyList {
  
  
  // 정점들과 인접 리스트를 담을 객체 생성
  constructor() {
    this.vertices = {};
  }
  
  
  // 정점을 추가하는 메소드 구현
  addVertex(vertex) {
    // 넘겨받은 인자(정점)는 키가 되며, 빈 배열을 값으로 할당
    // 이미 존재하는 정점이라면, 덮어 씌워지지 않아야 함
	this.vertices[vertex] = this.vertices[vertex] || [];
  }

  // 정점의 존재여부를 boolean 타입으로 반환하는 메소드 구현
  contains(vertex) {
    return !!this.vertices[vertex];
  }

  // 두 정점 사이 간선을 추가하는 메소드 구현 (무방향 그래프이므로 쌍방 구현)
  addEdge(fromVertex, toVertex) {
	
    // 넘겨받은 2개의 정점 모두 존재해야 하며, 아닐 경우 아무것도 하지 않기
	if (!this.contains(fromVertex) || !this.contains(toVertex)) {
	  return;
	}
    
    // fromVertex의 인접 리스트에 toVertex를 추가
    if (!this.hasEdge(fromVertex, toVertex)) {
      this.vertices[fromVertex].push(toVertex);
	}

    // toVertex의 인접 리스트에 fromVertex를 추가
	if (!this.hasEdge(toVertex, fromVertex)) {
      this.vertices[toVertex].push(fromVertex)
	}
  }
  
  
  // fromVertex와 toVertex 사이 간선의 존재여부를 확인하는 메소드
  hasEdge(fromVertex, toVertex) {
		
    // 만약 정점(fromVertex)이 존재하지 않는다면 false 반환
	if (!this.contains(fromVertex)) {
	  return false;
	}
	// 존재한다면 해당 정점의 리스트에 toVertex가 포함되어 있는지 여부 반환
	return !!this.vertices[fromVertex].includes(toVertex);
  }


  // 두 정점 사이 간선을 삭제하는 메소드
  removeEdge(fromVertex, toVertex) {

    // 인자로 넘겨받은 두 정점이 모두 존재하지 않는다면 아무것도 하지 않기
	if (!this.contains(fromVertex) || !this.contains(toVertex)) {
	  return;
	}

    // fromVertex의 인접 리스트에 있는 toVertex를 삭제하기
    if (this.hasEdge(fromVertex, toVertex)) {
	  const index = this.vertices[fromVertex].indexOf(toVertex);
	  this.vertices[fromVertex].splice(index, 1);
	}

	// toVertex의 인접 리스트에 있는 fromVertex를 삭제하기
    if (this.hasEdge(toVertex, fromVertex)) {
      const index = this.vertices[toVertex].indexOf(fromVertex);
      this.vertices[toVertex].splice(index, 1);
    }
  }


  // 정점을 삭제하는 메소드 구현 (간선도 함께 삭제하기)
  removeVertex(vertex) {
		
    // 인자로 받은 정점(vertex)가 존재할 경우에만 진행
	if (this.contains(vertex)) {
    
      // 모든 정점들의 리스트를 순회하여 전달인자의 정점(vertex)과 이어진 간선 제거
      for (let arr of Object.values(this.vertices)) {
        let idx = arr.indexOf(vertex);
        arr.splice(idx,1)
      }
      
      // 전달인자로 주어진 정점을 삭제
      delete this.vertices[vertex];
	}
  }
}

 

- 전달인자 vertex와 인접한 정점들만 순회하면서 removeEdge로 간선을 삭제하기

 

  // removeVertex의 레퍼런스 코드
  removeVertex(vertex) {
  
  // 인자로 받은 정점(vertex)가 존재할 경우에만 진행
    if (this.contains(vertex)) {
  
  // 전달인자의 정점과 인접한 정점들만 removeEdge 메소드로 삭제
      while (this.vertices[vertex].length > 0) {
        this.removeEdge(this.vertices[vertex][0], vertex);
      }
	
      // 최종적으로 해당 정점을 삭제합니다
	  delete this.vertices[vertex];
	}
  }