자료구조 [자바스크립트]

Contents

• Stack
• Queue

• Tree

  • Interface
  • Depth first
  • Breadth first
  • Check Tree width and depth
• Set

• Linked List

  • Constructor
  • Insert a node in the middle
  • Delete a node
  • Linked List function
  • insertHead & removeHead
  • forEach & print
  • addMiddle & removeMiddle
  • insertAfter & removeAfter

• Binary Search Tree

  • Contructor
  • Intert
  • Contains
  • Add a node
  • Find a node

• Hash Tables

  • Chaining
  • Linear Probing
• Graph

Stack

Stack과 Queue는 비슷한 구조를 가졌습니다. 차이점은 Stack은 나중에 들어온 데이터가 먼저 제거되고, Queue는 먼저 들어온 데이터 순으로 제거됩니다. Stack과 Queue는 시간복잡도가 constant이기에 처리 속도가 빠릅니다. Javascript engine은 우리의 코드를 실행할 때 내부적으로 Call Stack과 Message queue를 가지고 있습니다. 또한, 텍스트 에디터나 웹브라우저의 뒤로가기 버튼은 Stack을 사용하고 있습니다.

아마도 대부분 알게 모르게 Stack을 사용해 봤을 것입니다. 자바스크립트의 배열을 만들고 push와 pop으로 그 배열을 조작했다면 Stack을 사용한 것입니다. Stack과 Queue는 각 데이터가 메모리 영역에 분산돼 있지 않고 인접해 있습니다. 몇몇 언어에서는 배열 생성 시 메모리를 지정해 주어야합니다. 자바스크립트는 dynamic-array이기에 이러한 부분을 직접 처리할 필요가 없습니다.

배열을 이용하면 손쉽게 Stack을 구현할 수 있지만, 아래의 코드는 객체를 사용해 Stack을 구현했습니다. 먼저 객체를 사용해 Stack 생성자 함수를 작성합니다.

function Stack(capacity) {
  this.capacity = capacity;
  this.storage = {};
  this.count = 0;
}

다음으로 새로운 데이터를 추가할 push method를 prototype 객체에 추가합니다. 새로운 데이터를 추가한 후 반환값은 데이터 전체 길이입니다

Stack.prototype.push = function(value) {
  if (this.count === this.capacity) {
    return 'Max capacity already reached. Please remove an element before adding a new one.';
  } else if (value !== undefined) {
    this.storage[this.count++] = value;
    return this.count;
  }
};

이제 Stack에 데이터를 추가할 수 있습니다. 다음으로는 데이터를 제거하는 pop method를 추가합니다. 가장 나중에 추가된 데이터를 stack에서 삭제 후 해당 데이터를 반환합니다.

Stack.prototype.pop = function() {
  if (this.count === 0) {
    return 'No element inside the stack.';
  } else if (this.count > 0) {
    let deletedEl = this.storage[this.count];

    delete this.storage[--this.count];

    return deletedEl;
  }
};

기본적인 데이터의 추가와 삭제 기능을 위와 같이 작성했습니다. 추가로 아래의 코드는 stack의 크기를 반환하는 메서는, 특정 데이터가 있는지 확인하는 메서드, 특정 데이터까지 도달하는데 몇 번의 pop 호출이 필요한지 확인하는 메서드 입니다.

Stack.prototype.count = function() {
  return this.count;
};

Stack.prototype.contains = function(value) {
  if (this.count > 0) {
    for (let i = 0; i < this.count; i++) {
      if (this.storage[i] === value) {
        return true;
      }
    }

    return false;
  }
};

Stack.prototype.until = function(value) {
  if (this.count > 0) {
    let counter = 0;

    for (let i = this.count - 1; i >= 0; i--) {
      counter++;

      if (this.storage[key] === value) {
        return counter;
      }
    }
  }
};

위와 같이 Stack을 자바스크립트의 객체를 통해서 구현해 보았습니다. 다음으로 Queue로 넘어갈까 하다가 뭔가 아쉬워 객체 대신 string으로 Stack을 간단히 만들어 보겠습니다. 우선 생성자 함수의 객체를 String 변경합니다.

function Stack(capacity) {
  this.capacity = capacity;
  this.storage = '';
  this.count = 0;
}

그리고 동일하게 push와 pop을 구현해 봅니다.

Stack.prototype.push = function(value) {
  if (this.count === this.capacity) {
    return 'Max capacity already reached.';
  } else if (value !== undefined) {
    this.storage += '***' + value;

    return ++this.count;
  }
};

Stack.prototype.pop = function() {
  if (this.count > 0) {
    let lastIdx = this.storage.lastIndexOf('***');
    let deletedEl = this.storage.slice(lastIdx + 3);

    this.storage = this.storage.substr(0, lastIdx);
    this.count--;

    return deletedEl;
  }

  return 'No element inside the stack.';
};

Queue

만약 배열로 Queue를 만들고, unshift method로 데이터를 제거한다면 시간복잡도는 어떻게 될까요? 일반적으로, index 1부터 순차적으로 index를 변경해야하기 때문에 linear가 됩니다. 하지만, 대부분의 모던 브라우저에서 이 기능이 linear보다 최적화되어 있습니다.

아래의 코드는 위의 Stack과 마찬가지로 Queue를 객체를 이용해 구현해 보았습니다. 먼저 객체를 사용해 Queue 생성자 함수를 작성합니다. Stack과는 다르게 head와 tail 두 변수를 만들었습니다. Queue는 선입선출이기 때문에 데이터를 추가하고 삭제하는 작업을 위해 head와 tail을 tracking합니다.

function Queue(capacity) {
  this.storage = {};
  this.capacity = capacity;
  this.head = 0;
  this.tail = 0;
}

다음 코드는 데이터의 길이를 반환하는 count method입니다.

Queue.prototype.count = function() {
  return this.tail - this.head;
};

다음으로 새로운 데이터를 추가할 enqueue method를 prototype 객체에 추가합니다. 새로운 데이터를 추가한 후 반환값은 데이터 전체 길이입니다.

Queue.prototype.enqueue = function(value) {
  if (this.count() === this.capa) {
    return 'Max capacity already reached.';
  } else if (value !== undefined) {
    this.storage[this.tail++] = value;

    return this.count();
  }
};

그리고 Queue의 데이터를 제거하는 enqueue method를 추가합니다. 가장 오래된 데이터를 queue에서 삭제 후 해당 데이터를 반환합니다.

Queue.prototype.dequeue = function() {
  if (this.count() > 0) {
    let deledtedEl = this.storage[this.head];

    delete this.storage[this.head++];

    return deletedEl;
  }
};

Tree

트리는 계층구조를 가진 자료구조입니다. 웹개발 분야에서 가장 쉬운 예를 찾으면, 브라우저의 DOM을 들 수 있습니다. 이외에도 프로그래밍을 조금 공부하다보면 트리 구조를 쉽게 접할 수 있습니다.

트리는 데이터의 최상위에 위치할 root 노드가 필요하고, 또 각 데이터를 어떻게 저장할지 생각해 보는것이 중요한 것 같습니다. 그리고 노드에 key 또는 다른 노드를 추가하기 위한 메소드도 필요할 것입니다.

Tree Interface

트리 구조의 기본적인 interface를 살펴보면 아래와 같습니다.

Constructor :

• root
• Storage

Methods :

• add(value)

  • 새로운 트리 노드를 추가하는 메소드

• contains(value): (value: any) => boolean

  • 인자로 받은 값이 Tree에 존재하는지 확인
• min/max : This returns the min or max value / key in the tree
• remove(key) : This removes the key from the tree

트리 구조에서 일반적으로 중요하게 학습해야 할 사항은 tree-traversal 입니다. tree-traversal이라고 하면 트리의 모든 node를 iterating하는 것을 말합니다. tree-traversal에는 크게 Breadth-first traversal과 Depth-first traversal 두 가지가 있습니다.

먼저 트리 구조의 노드를 생성하는 생성자 함수를 만들겠습니다. Constructor function으로도 만들 수 있지만, tree의 node는 factory function으로 생성해 보도록 하겠습니다.

const Node = function(data) {
  const newNode = Object.create(treeMethods);

  newNode.data = data;
  newNode.children = [];

  return newNode;
};

const treeMethods = {};

treeMethods.add = function(data) {
  this.children.push(Node(data));
};

treeMethods.contains = function(value) {
  if (this.value === value) {
    return true;
  }

  return this.children.some(node => node.value === value);
};

treeMethods.remove = function(data) {
  this.children = this.children.filter(node => node.data !== data);
};

위와 같이 tree의 node를 생성하는 factory function을 만들었습니다. node를 만들었으니, 이제 tree를 만들어 보도록 하겠습니다. Tree는 ES6의 class로 만들도록 하겠습니다.

class Tree {
  constructor() {
    this.root = null;
  }
}

Tree의 root node를 지정하는 class를 생성했습니다. 위에서 언급했던 Tree를 traverse할 두 가지 메소드를 추가하도록 하겠습니다.

트리 순회를 구현하는 방법은 여러가지가 있겠지만, 저는 새로운 배열을 생성해서 이 배열에 Tree의 각 Node를 모아서 순회하는 방법으로 구현하겠습니다.

Depth first (깊이우선 탐색)

Depth first search를 하기 위해, 먼저 주어진 root node를 요소로 가지는 배열을 생성합니다. 그리고 root node의 children node를 배열의 앞으로 unshift 합니다. 배열의 길이가 0이 될 때까지, 배열의 첫 요소를 꺼내서 이 작업을 반복합니다. 코드로 써 보면 아래와 같습니다. 참고로, 새로 생성한 배열 입장에서 보면 늦게 추가된 요소가 먼저 빠져 나가기 때문에, stack 구조로 된 배열로 생각할 수 있습니다.

class Tree {
  constructor() {
    this.root = null;
  }

  traverseDF(callback) {
    const nodeStack = [this.root];

    while (nodeStack.length) {
      const curNode = nodeStack.shift();

      callback(curNode);

      nodeStack.unshift(...curNode.children);
    }
  }
}

Breadth first (너비우선 탐색)

Breadth first traverse 또한 위의 Depth first traverse와 크게 다른점은 없습니다. 새로 생성한 배열에 children node를 추가할 때 push로 추가해 주면 됩니다. 이렇게 함으로써, 하위 Level에 있는 children node는 배열의 끝에 위치해 상위 level의 node traversing이 모두 완료된 후에 차례가 돌아오게 됩니다. 너비우선 탐색의 경우 새로 생성한 배열은 Queue 구조를 가지게 됩니다.

class Tree {
  constructor() {
    this.root = null;
  }

  traverseBF(callback) {
    const nodeQueue = [this.root];

    while (nodeQueue.length) {
      const curNode = nodeQueue.shift();

      nodeQueue.push(...curNode.children);

      callback(curNode);
    }
  }
}

보너스 - 트리 넓이 및 깊이 확인

Tree 구조를 학습하다 보면 트리의 깊이, 넓이를 확인하는 알고리즘 문제를 보게될 것입니다. 트리의 넓이와 깊이를 확인하기 위해서, 앞서 학습한 너비우선 탐색으로 접근하면 수월합니다. 하지만 각 층별의 넓이와 트리의 깊이를 계산해야 하기 때문에 조금 더 생각을 해봐야 해요.

새로운 배열에 node를 추가하는 방법은 같지만, 새로운 Level(층)을 시작하기 전 partition 역할을 할 요소를 추가해야 합니다.

그리고, 각 층의 넓이를 요소로 하는 또다른 배열을 생성합니다. 각 node를 확인하면 층의 넓이에 1씩 더해주고, partition 요소를 만나면 다음의 요소부터는 새로운 층에 위치한 node이기 때문에 배열에 0을 추가해 줍니다.

class Tree {
  constructor() {
    this.root = null;
  }

  levelWidth() {
    const nodeQueue = [this.root, 'partition'];
    const widthByLevel = [0];

    while (nodeQueue.length > 1) {
      const curNode = nodeQueue.shift();

      if (curNode === 'partition') {
        nodeQueue.push(curNode);
        widthByLevel.push(0);
      } else {
        nodeQueue.push(...curNode.children);
        widthByLevel.push(widthByLevel[widthByLevel.length - 1]++);
      }
    }

    return widthByLevel;
  }
}

Set

Set은 정렬되지 않은 컬렉션입니다. Set의 중요한 특징 중 하나는 중복된 요소를 가지지 않는다는 점이며, 그 값은 컬렉션 내에서 유일합니다. 수학의 유한집합의 개념을 컴퓨터 과학에 적용한 것입니다. 따라서 중복이 없는 자료 구조를 원한다면 Set이 유용합니다.

Linked List

연결리스트는 Tree구조이지만 하나의 자식노드만 가지고 있는 구조입니다. 그리고 배열과는 다른게 Linked List의 각 노드는 데이터 값과 다음 노드를 가리키는 참조값을 가지고 있습니다. 위에서 언급한 바와 같이 자바스크립트 배열은 dynamic array입니다. dynamic array가 없는 언어에서 Linked list는 dynamic array를 대체해 사용하기에도 좋습니다.

모든 자료구조가 그렇듯 Linked List 또한 장단점이 있습니다. Linked List에서 데이터를 추가하거나 삭제할 때 constant 시간복잡도를 가지고 있어, 속도가 빠릅니다. Linked List와 자주 비교되는 배열에서 같은 작업을 했을때의 시간복잡도는 Linear입니다. 추가하거나 삭제한 요소 이후의 모든 요소의 위치를 변경해주어야 하기 때문입니다. Linked List에서는 다음 노드를 가리키는 Pointer만 변경을 해주면 됩니다.

반면, 데이터를 검색하려면 원하는 데이터를 찾을때까지 전체리스트를 훑어야 합니다. 배열에서는 특정 요소에 index로 바로 접근할 수 있습니다.

정리하자면, Linked List에서 데이터의 추가 및 삭제 작업의 시간복잡도는 O(1), 데이터를 얻는 시간복잡도는 O(n)입니다. Array List에서 데이터의 추가 및 삭제 작업의 시간복잡도는 O(n), 데이터를 가져오는 시간복잡도는 O(1)입니다.

Linked List를 만들어서 노드를 생성하고 삭제하는 방법 몇 가지에 대해 아래와 같이 풀어서 설명해 봤습니다.

Constructor 생성

• 새로운 노드를 생성합니다.
• 새로운 노드의 next를 head로 지정합니다.
• head의 값을 새로 생성한 노드로 지정합니다.

중간에 데이터 추가하기

• 요소를 추가할 n번째 인덱스 바로 전 노드로 이동합니다.
• 바로 전 노드를 변수 1에 저장합니다.
• 그리고 n번째 노드를 변수 2에 저장합니다.
• 새로운 노드를 생성합니다.
• 변수 1이 새로운 노드를 가리키게 하고, 새로운 노드는 변수 2를 가리키도록 합니다.

데이터 삭제하기

• 삭제할 n번째 인덱스 바로 전 노드로 이동합니다.
• n번째 인덱스 전 노드의 next를 삭제할 노드의 next로 지정해 줍니다.

Linked List Function

위의 이해를 바탕으로 Linked List 및 여러 method를 자바스크립트를 이용해 구현해 보도록 하겠습니다. 먼저 Linked List의 노드를 생성하는 construction function을 만듭니다. 그리고 Linked List 자체를 생성하는 생성자 함수를 만듭니다.

function Node(value) {
  this.value = value;
  this.next = null;
}

function LinkedList(value) {
  if (value === undefined) {
    return console.log('Please provide value for first node.');
  }

  let firstNode = new Node(value, ref);

  this.head = firstNode;
  this.tail = this.head;
  this.length = 1;
}

insertHead & removeHead

Linked List의 맨 처음 노드, 그러니까 Head에 노드를 추가하거나 삭제하는 방법은 아래와 같이 작성해 보았습니다.

LinkedList.prototype.insertHead = function(value) {
  let tempNode = new Node(value);
  tempNode.next = this.head;

  this.head = tempNode;
  this.length++;
};

LinkedList.prototype.removeHead = function() {
  let oldHead = this.head;
  let newHead = this.head.next;

  this.head = newHead;
  oldHead.next = null;

  return oldHead;
};

forEach & print

배열의 forEach method와 같이 Linked List의 forEach를 아래와 같이 만들 수 있습니다. 이 forEach를 활용해 전체 데이터 값을 string으로 반환하는 method를 만들 수 있습니다.

LinkedList.prototype.forEach = function(callback) {
  let tempNode = this.head;
  while (tempNode) {
    callback(tempNode.value);
    tempNode = tempNode.next;
  }
};

LinkedList.prototype.print = function() {
  let valueArr = [];

  this.forEach(function(value) {
    valueArr.push(value);
  });

  return valueArr.join(', ');
};

addMiddle & removeMiddle

n번째 위치에 새로운 노드를 추가하고 삭제하는 method는 아래와 같이 구현할 수 있습니다.

LinkedList.prototype.addMiddle = function(idx, input) {
  let tempNode = this.head;

  for (let i = 1; i < idx; i++) {
    tempNode = tempNode.next;
  }

  let newNode = new Node(input);
  newNode.next = tempNode.next;
  tempNode.next = newNode;
  this.length++;

  return this.length;
};

LinkedList.prototype.removeMiddle = function(idx) {
  let tempNode = this.head;

  while (--idx < 0) {
    tempNode = tempNode.next;
  }

  let deleted = tempNode.next;
  tempNode.next = tempNode.next.next;
  this.length--;

  return deleted;
};

insertAfter & removeAfter

위의 addMiddle, removeMiddle과 유사하지만 참조할 노드를 argument로 받아 그 argument를 기준으로 노드를 추가하고 삭제할 수도 있습니다.

LinkedList.prototype.insertAfter = function(refNode, value) {
  let oldNext = refNode.next;
  let newNext = new Node(value);

  refNode.next = newNext;
  newNext.next = oldNext;

  if (this.tail === refNode) {
    this.tail = newNext;
  }

  this.length++;

  return this.length;
};

LinkedList.prototype.removeAfter = function(refNode) {
  let deleted = refNode.next;

  if (!deleted) {
    return 'Nothing to be removed.';
  }

  refNode.next = deleted.next;

  deleted.next = null;

  if (deleted === this.tail) {
    this.tail = refNode;
  }

  this.length--;

  return deleted;
};

Binary Search Tree

Binary Tree는 좌, 우측에 하나씩 최대 2개의 자식 노드를 가집니다. 그리고 Binary Search Tree(BST)에서는 모든 왼쪽의 자식 노드는 부모 요소의 값보다 작은 값을 가집니다. 그리고 모든 오른쪽의 자식 노드는 부모 노드의 값보다 큰 값을 가집니다.(또는 그 반대) 일반적으로 BST에 동일한 값의 노드를 만들지 않지만, 만약 동일한 값의 자식노드를 만든다면 왼쪽 또는 오른쪽 한 곳에만 생성될 수 있도록 사전에 결정을 합니다.

BST의 이러한 구조 덕분에 빠르게 데이터를 추가하고 검색할 수 있습니다. BST에서 데이터를 검색한다면, 데이터를 찾을때까지 매 연산마다 데이터의 반을 신경쓰지 않아도 되기 때문에, 시간복잡도가 log(n)이 됩니다.

Binary Search Tree를 코드로 작성 전 Pseudocode를 작성해 봅니다.

Constructor 생성

• 새로운 노드를 생성합니다.
• 노드의 value, left, right 속성을 만듭니다.

Insert

• 추가할 값을 전달 받고, 값의 위치를 파악해야합니다.
• 현귀 노드의 값과 argument로 전달 받은 값을 비교 후 결과에 따라 왼쪽 또는 오른쪽으로 이동합니다.
• 왼쪽 또는 오른쪽에 자식 노드가 없다면 새로운 노드를 만든 후 추가합니다.
• 만약 이동한 자리에 노드가 있다면, 그 노드의 값과 다시 비교 후 위치를 파악합니다. 이를 위해 재귀를 이용하도록 하겠습니다.

Contains

• value를 전달 받아, Boolean값을 반환합니다.
• value와 현재 노드의 값을 비교합니다. 값이 같으면 true를 반환합니다.
• 현재 노드의 값보다 value가 크거나 작으면, 다음 노드(왼쪽 또는 오른쪽)으로 이동합니다.
• 다음 노드로 이동후 위의 작업을 반복합니다.
• 마지막까지 값을 못 찾으면 false를 반환합니다.

위의 내용을 기본적인 BST 노드를 만드는 생성자 함수를 아래와 같이 만들 수 있습니다.

function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

데이터 추가하기

insert메소드를 pseudocoding한 것을 기준으로 트리에 데이터를 추가하는 메소드를 아래와 같은 방식으로 구현을 할 수 있습니다.

BST.prototype.insert = function(value) {
  const direction = value <= this.value ? 'left' : 'right';

  if (this[direction]) {
    this[direction].insert(value);
  } else {
    this[direction] = new BST(value);
  }
};

데이터 찾기

BST.prototype.contains = function(value) {
  if (this.value === value) {
    return true;
  }

  const direction = value <= this.value ? 'left' : 'right';

  if (this[direction]) {
    return this[direction].contains(value);
  }

  return false;
};

Hash Tables

Hash Table은 컴퓨터공학에서 매우 강력한 도구이며, 프로그래밍 언어, 데이터베이스 등에서 광범위하게 사용하고 있습니다. 모든 자료 구조가 그렇듯 Hash Table 또한 tradeoff가 존재합니다. Hash table은 메모리 사용량이 크고 복잡한 hashing이 필요합니다. 하지만, 데이터를 검색, 삭제하는데 constant의 시간복잡도를 가집니다.

Hashing function을 통해 key를 전달하면, Hashing function이 그것을 고유의 메모리 공간의 주소로 변환합니다. Hash Table은 객체가 위치한 정확한 위치를 알 수 있고, 데이터가 존재하는지 파악할 수 있기 때문에 Map과 Set에서 매우 유용합니다.

하지만, Hash Table은 순서에 대한 개념은 없기 때문에 정렬된 리스트에서는 그리 유용하지 못 합니다. 그리고 collision 없이 모든 객체를 저장하기 위해서 충분히 큰 메모리 공간이 필요합니다.

또한, 정확한 주소를 찾을 수 있을만큼 충분히 잘 짜여진 hashing 알고리즘이 필요합니다. 이 알고리즘은 몇가지 조건을 갖추어야 합니다. 먼저 Idempotent(멱등)해야 합니다. 바꿔말하면, 함수가 무수히 많이 호출이 되어도 같은 input의 조건에서 같은 결과를 반환해야 합니다.

// 이 함수는 Idempotent 합니다.
function double(x) {
  return x * 2;
}

// 이 함수는 Idempotent 하지 않습니다.
let multiplier = 0;
function doublePlus(x) {
  multiplier++;
  return 2 * x * multiplier;
}

doublePlus 함수는 같은 input을 주어 호출해도 매번 다른 결과를 반환합니다. 해당 함수가 side-effect를 가지고 있기 때문입니다. Side-effect란 함수를 호출하면, 함수 주변 환경에 어떠한 영향을 끼치는 것을 말합니다. 일반적으로 우리가 프로그래밍을 하며 이러한 영향을 가능한 줄이려고 할 것입니다. 왜냐하면, 이것은 함수 주변의 상황까지 고려해야 하기 때문에 코드 디버깅과 테스트를 어렵게 만들기 때문입니다. Hashing function에서 idempotent은 매우 중요합니다. 만약 Hashing function이 한 번이라도 잘못된 메모리 주소를 반환하면, 그 자료 구조를 사용할 수 없기 때문입니다.

좋은 Hashing algorithm을 만들기 위해서 값을 적절하게 분포해야합니다. 그렇지 않으면 충돌이 발생할 것입니다. 충돌은 두 개의 다른 input이 같은 반환 값을 받을 때 발생합니다. 다음은 알파벳을 숫자로 대체하는 잘못된 hashing algorithm의 예입니다. 'az'은 1 + 26이 되어 27이고, 'by'는 2 + 25가 되어 27이 되어 두 결과가 충돌합니다.

기본적으로 Hash Table의 검색과 삭제 등 작업은 매우 빠르게 이루어집니다. 이를 위해서 함수의 성능도 좋아야 합니다.

Hashing Function의 몇가지 기본적인 특징을 살펴보면 아래와 같습니다.

해시 테이블 간 충동 해결

해시 테이블의 해시 함수에 따른 key값을 입력해도 같은 반환 값을 받아 해시충돌이 발생하는 경우가 존재할 수 있습니다. 해시 테이블에서 충돌이 발생하면 자료를 적절하게 관리할 수 없기 때문에, 충돌 문제를 해결해 주어야 합니다. 충돌 문제의 일반적인 해결 방법으로 체이닝, 선형탐사, 이중 해싱 세 가지가 있으며, 해결 방법에 대해 알아보도록 하겠습니다.

체이닝(Separate Chaining)

그래프 (Graph)

그래프는 간선(edge)으로 연결된 노드 또는 정점(vertex)의 집합으로 네트워크 구조를 추상화한 자료구조입니다. 그래프에는 두 정점이 단방향 또는 양방향으로 연결 되었는지에 따라 directed graph와 undirected graph가 있습니다. 또, 간선의 가중치 유무에 따라 unweighted graph, weighted graph가 있습니다. 페이스북이나, 트위터와 같은 소셜 네트워크를 그래프로 표현할 수 있고, 실제 세계의 도로나 항로, 통신망을 나타낼 때도 그래프를 사용할 수 있습니다.

프로그래밍에서 그래프를 응용해 해결할 수 있는 문제들이 많습니다. 특정 정점, 간선 경로 검색, 최단 경로 찾기 등이 있습니다.

그래프 나타내기

인접 행렬

각 노드 간 연결 상태를 이차원 배열로 만들고 배열의 값을 0(미연결) 또는 1(연결)로 표시하는 방식이에요. 이 방식에서는 존재하지 않는 간선도 0으로 표시하기 때문에 불필요한 메모리 소비를 할 수 있습니다. 인접 정점을 찾을 때도 배열을 모두 순회해야 합니다.

인접 리스트

인접 리스트는 각 정점별로 인접 정점들의 리스트를 배열이나 해시테이블, 링크드 리스트 등의 자료 구조로 저장하는 방식이에요.

근접 행렬

근접 행렬은 그래프의 정점을 행으로