Leetcode/graph.js at master · ferrikt/Leetcode · 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
Graph traversal means visiting every vertex and edge exactly once in a well-defined order.
The most common way of tracking vertices is to mark them. Breadth First Search (BFS)
There are many ways to traverse graphs. BFS is the most commonly used approach.
*/

class Graph {
  // defining vertex array and
  // adjacent list
  constructor(noOfVertices) {
    this.noOfVertices = noOfVertices;
    this.adjacencyList = new Map();
  }


  addVertex(v) {
    this.adjacencyList.set(v, []);
  }

  addEdge(u,v) {
    this.adjacencyList.get(u).push(v);
    this.adjacencyList.get(v).push(u);
  }

  printGraph(){

    const verticles = this.adjacencyList.keys();

    for (let x of verticles) {

      const vals = this.adjacencyList.get(x);
      let str = '';

      for (let val of vals) {
        str+=val+' ';
      };

      console.log(x+' -> '+str);
    };
  }

  // bfs(v)
	// dfs(v)
}

/*const g = new Graph(6);
var vertices = [ 'A', 'B', 'C', 'D', 'E', 'F' ];

// adding vertices
for (var i = 0; i < vertices.length; i++) {
    g.addVertex(vertices[i]);
}

// adding edges
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');

g.printGraph();
*/


const g = new Graph(5);

g.addVertex(0);
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addVertex(4);

g.addEdge(0,1);
g.addEdge(0,4);


g.addEdge(1,2);
g.addEdge(1,3);
g.addEdge(1,4);


g.addEdge(2,3);

g.addEdge(3,4);


g.printGraph();