Published on

[자료구조] javascript 그래프 (graph)

Authors
  • avatar
    Name
    piano cat
    Twitter

javascript 에서 그래프 자료구조에 대해서 알아보자

그래프는 비선형자료구조로 노드들이 이어져 있는 형태의 자료구조를 말한다.

정점(노드), 간선, 방향, 가중에 따라서 그래프 구조의 특징이 다르다.

그래프 구현 방법으로는 인접행렬과 인접리스트 가 있다.

인접행렬 (무방향, 비가중)

class Graph {
  constructor(numNodes) {
    this.numNodes = numNodes
    this.adjMatrix = []

    // 인접 행렬 초기화
    this.adjMatrix = Array.from(Array(this.numNodes), () => Array(this.numNodes).fill(0))
  }

  addEdge(node1, node2) {
    // 무방향 그래프이므로 두 방향 모두 연결해줍니다.
    this.adjMatrix[node1][node2] = 1
    this.adjMatrix[node2][node1] = 1
  }
}

// 그래프 생성 및 간선 추가
const graph = new Graph(4)
graph.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(1, 3)
graph.addEdge(2, 3)
console.log(graph.adjMatrix)
/** 결과
[
  [0,1,1,0],
  [1,0,0,1],
  [1,0,0,1],
  [0,1,1,0]
]
**/

인접리스트 (방향, 가중)

    A --2-- B
   / \    / \
  1   3  4   5
 /     \/     \
C       D      E
// 노드를 나타내는 클래스
class Node {
  constructor(id) {
    this.id = id
    this.edges = [] // 이 노드와 연결된 간선 목록
  }
}

// 간선을 나타내는 클래스
class Edge {
  constructor(nodeId, weight) {
    this.nodeId = nodeId
    this.weight = weight
  }
}

// 그래프를 나타내는 클래스
class Graph {
  constructor() {
    this.nodes = {} // 그래프의 모든 노드를 담은 객체
  }

  // 노드를 추가하는 메서드
  addNode(id) {
    this.nodes[id] = new Node(id)
  }

  // 간선을 추가하는 메서드
  addEdge(fromNode, toNode, weight) {
    this.nodes[fromNode].edges.push(new Edge(toNode, weight))
  }
}

// 그래프 생성 및 노드/간선 추가
const graph = new Graph()
graph.addNode('A')
graph.addNode('B')
graph.addNode('C')
graph.addNode('D')
graph.addNode('E')
graph.addEdge('A', 'B', 2)
graph.addEdge('A', 'C', 1)
graph.addEdge('A', 'D', 3)
graph.addEdge('B', 'D', 4)
graph.addEdge('B', 'E', 5)
console.log(graph.nodes)
/** 결과
{
    "A": {
        "id": "A",
        "edges": [
            {
                "nodeId": "B",
                "weight": 2
            },
            {
                "nodeId": "C",
                "weight": 1
            },
            {
                "nodeId": "D",
                "weight": 3
            }
        ]
    },
    "B": {
        "id": "B",
        "edges": [
            {
                "nodeId": "D",
                "weight": 4
            },
            {
                "nodeId": "E",
                "weight": 5
            }
        ]
    },
    "C": {
        "id": "C",
        "edges": []
    },
    "D": {
        "id": "D",
        "edges": []
    },
    "E": {
        "id": "E",
        "edges": []
    }
}
**/

활용 예시

노드와 간선으로 이루어진 데이터, 네트워크 데이터 등

  • 노드와 간선으로 이루어진 데이터: 지도, 지하철 노선도, 인터넷 등
  • 네트워크 데이터: 최단 경로, 최소 스패닝 트리, 최대 유량 등