data-structures/Graph.js at master · salvatoreolivieri/data-structures · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//Edge List: A key value pain stored inside an array of arrays, 0 is connected with 2 and vice versa
const edgeGraph = [
  [0, 2],
  [2, 3],
  [2, 1],
  [1, 3],
]

// Adjacent List: The index math with value, so the fist array is index of 0 that is connected with 2, the index of 1 is connected with 2 and 3 and so on..
const adjacentGraph = [[2], [2, 3], [0, 1, 3], [1, 2]]

// Adjacent Matrix: The same like the adjacent list but with matrix representation
const adjacentMatrixGraph = [
  [0, 0, 1, 0],
  [0, 0, 1, 1],
  [1, 1, 0, 1],
  [0, 1, 1, 0],
]

// Implementation
class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }

  addVertex(node) {
    this.adjacentList[node] = []
    this.numberOfNodes++
  }

  // Undirected Graph
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }

  showConnections() {
    const allNodes = Object.keys(this.adjacentList)

    for (let node of allNodes) {
      let nodeConnections = this.adjacentList[node]

      let connections = ""
      let vertex

      for (vertex of nodeConnections) {
        connections += vertex + " "
      }

      console.log(`${node}--> ${connections}`)
    }
  }
}

const myGraph = new Graph()
myGraph.addVertex("0")
myGraph.addVertex("1")
myGraph.addVertex("2")
myGraph.addVertex("3")
myGraph.addVertex("4")
myGraph.addVertex("5")
myGraph.addVertex("6")
myGraph.addEdge("3", "1")
myGraph.addEdge("3", "4")
myGraph.addEdge("4", "2")
myGraph.addEdge("4", "5")
myGraph.addEdge("1", "2")
myGraph.addEdge("1", "0")
myGraph.addEdge("0", "2")
myGraph.addEdge("6", "5")

myGraph.showConnections()