-
Notifications
You must be signed in to change notification settings - Fork 45
Expand file tree
/
Copy pathgraph.js
More file actions
74 lines (64 loc) · 1.3 KB
/
graph.js
File metadata and controls
74 lines (64 loc) · 1.3 KB
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
/**
* graph https://zh.wikipedia.org/wiki/%E5%9B%BE_(%E6%95%B0%E5%AD%A6)#.E5.9B.BE.E7.9A.84.E5.AD.98.E5.82.A8.E8.A1.A8.E7.A4.BA
**/
class Vertex() {
constructor(labrl,isVisited) {
this.label = label;
this.isVisited = isVisited;
}
}
class Graph(v) {
constructor() {
this.vertices = v;
this.edges = 0;
this.adj = [];
this.marked = [];
for(let i=0;i<v;++i) {
this.adj[i] = [];
this.adj[i].push('');
this.marked[i] = false;
}
}
addEdge(v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
}
showGrap() {
for(let i=0;i<this.vertices;i++) {
console.log(i + '->');
for(let j=0;j<this.vertices;++j) {
if(this.adj[i][j] != undefined) {
console.log(this.adj[i][j] + ' ');
}
}
}
}
dfs(v) {
this.marked[v] = true;
if(this.adj[v] != undefined) {
for(let j in this.adj[v]) {
if(!this.marked[j]) {
this.dfs(w);
}
}
}
}
bfs(s) {
let q = [];
this.marked[s] = true;
q.push(s);
while(q.length>0) {
let v = q.shift();
if(this.adj[v]!= undefined) {
//
}
for(let j in this.adj[v]) {
if(!this.marked[j]) {
this.marked[j] = true;
q.push(j);
}
}
}
}
}