FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
JavaScript/Sorts/TopologicalSort.js at master · TheAlgorithms/JavaScript · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
TheAlgorithms
/
JavaScript
Public
Uh oh!
There was an error while loading.
Please reload this page
.
Notifications
You must be signed in to change notification settings
Fork
5.8k
Star
34.2k
Code
Issues
21
Pull requests
192
Actions
Projects
Wiki
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Wiki
Security and quality
Insights
Expand file tree
Breadcrumbs
JavaScript
/
Sorts
/
TopologicalSort.js
Copy path
More file actions
More file actions
Latest commit
History
History
History
63 lines (55 loc) · 1.43 KB
Breadcrumbs
JavaScript
/
Sorts
/
TopologicalSort.js
Copy path
File metadata and controls
63 lines (55 loc) · 1.43 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
export
function
TopologicalSorter
(
)
{
const
graph
=
{
}
let
isVisitedNode
let
finishTimeCount
let
finishingTimeList
let
nextNode
this
.
addOrder
=
function
(
nodeA
,
nodeB
)
{
nodeA
=
String
(
nodeA
)
nodeB
=
String
(
nodeB
)
graph
[
nodeA
]
=
graph
[
nodeA
]
||
[
]
graph
[
nodeA
]
.
push
(
nodeB
)
}
this
.
sortAndGetOrderedItems
=
function
(
)
{
isVisitedNode
=
Object
.
create
(
null
)
finishTimeCount
=
0
finishingTimeList
=
[
]
for
(
const
node
in
graph
)
{
if
(
Object
.
prototype
.
hasOwnProperty
.
call
(
graph
,
node
)
&&
!
isVisitedNode
[
node
]
)
{
dfsTraverse
(
node
)
}
}
finishingTimeList
.
sort
(
function
(
item1
,
item2
)
{
return
item1
.
finishTime
>
item2
.
finishTime
?
-
1
:
1
}
)
return
finishingTimeList
.
map
(
function
(
value
)
{
return
value
.
node
}
)
}
function
dfsTraverse
(
node
)
{
isVisitedNode
[
node
]
=
true
if
(
graph
[
node
]
)
{
for
(
let
i
=
0
;
i
<
graph
[
node
]
.
length
;
i
++
)
{
nextNode
=
graph
[
node
]
[
i
]
if
(
isVisitedNode
[
nextNode
]
)
continue
dfsTraverse
(
nextNode
)
}
}
finishingTimeList
.
push
(
{
node
,
finishTime
:
++
finishTimeCount
}
)
}
}
/* TEST */
// const topoSorter = new TopologicalSorter()
// topoSorter.addOrder(5, 2)
// topoSorter.addOrder(5, 0)
// topoSorter.addOrder(4, 0)
// topoSorter.addOrder(4, 1)
// topoSorter.addOrder(2, 3)
// topoSorter.addOrder(3, 1)
// topoSorter.sortAndGetOrderedItems()
Back
|
FazBrowse Home
|
New Git URL