Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9987436

Browse files
committed
07.01 (1) BFS topological sorting
1 parent13611ab commit9987436

File tree

3 files changed

+102
-0
lines changed

3 files changed

+102
-0
lines changed
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package_01_TopologicalSorting;
2+
3+
importjava.util.ArrayList;
4+
5+
publicclassDirectedGraphNode {
6+
7+
intlabel;
8+
9+
ArrayList<DirectedGraphNode>neighbors;
10+
11+
publicDirectedGraphNode(intx) {
12+
label =x;
13+
neighbors =newArrayList<>();
14+
}
15+
16+
}
Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
/**
2+
* Time : O() ; Space: O()
3+
* @tag : LintCode Copyright; Geeks for Geeks; Depth First Search; Breadth First Search
4+
* @by : Steven Cooks
5+
* @date: Sep 26, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* Given an directed graph, a topological order of the graph nodes is defined
10+
* as follow:
11+
*
12+
* For each directed edge A -> B in graph, A must before B in the order list.
13+
* The first node in the order can be any node in the graph with no nodes direct to it.
14+
* Find any topological order for the given graph.
15+
*
16+
***************************************************************************
17+
* {@link http://www.lintcode.com/en/problem/topological-sorting/ }
18+
*/
19+
package_01_TopologicalSorting;
20+
21+
importjava.util.ArrayList;
22+
importjava.util.Hashtable;
23+
importjava.util.LinkedList;
24+
importjava.util.Map;
25+
importjava.util.Queue;
26+
27+
/** see test {@link _01_TopologicalSorting.SolutionTest } */
28+
publicclassSolution {
29+
30+
publicArrayList<DirectedGraphNode>topSort(ArrayList<DirectedGraphNode>graph) {
31+
Map<DirectedGraphNode,Integer>in =newHashtable<>();
32+
// count in-degree for each node in the graph
33+
for (DirectedGraphNodenode :graph) {
34+
if (!in.containsKey(node)) {
35+
in.put(node,0);
36+
}
37+
for (DirectedGraphNodeneighbor :node.neighbors) {
38+
intdegree =1;
39+
if (in.containsKey(neighbor)) {
40+
degree +=in.get(neighbor);
41+
}
42+
in.put(neighbor,degree);
43+
}
44+
}
45+
46+
// put all nodes with zero in-degree
47+
Queue<DirectedGraphNode>zeros =newLinkedList<>();
48+
for (DirectedGraphNodenode :in.keySet()) {
49+
if (in.get(node) ==0) {
50+
zeros.offer(node);
51+
}
52+
}
53+
54+
// construct result
55+
ArrayList<DirectedGraphNode>res =newArrayList<>();
56+
while (!zeros.isEmpty()) {
57+
DirectedGraphNodenode =zeros.poll();
58+
res.add(node);
59+
for (DirectedGraphNodeneighbor :node.neighbors) {
60+
intdegree =in.get(neighbor) -1;
61+
if (degree >0) {
62+
in.put(neighbor,degree);
63+
}
64+
if (degree ==0) {
65+
zeros.offer(neighbor);
66+
}
67+
}
68+
}
69+
returnres;
70+
}
71+
72+
}
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package_01_TopologicalSorting;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importorg.junit.Test;
6+
7+
publicclassSolutionTest {
8+
9+
@Test
10+
publicvoidtest() {
11+
fail("Not yet implemented");// TODO
12+
}
13+
14+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp