Traverser
Traverser copied to clipboard
intuit
Create post order,IN order, Pre order, DFS,BFS examples in Kotlin
1. Issue Link: https://github.com/intuit/Traverser/issues/17
2. Brief explanation of a change:
3. Will it break existing clients and code in production? YES
@vibhu172000 please, put some description to your PR. What does it solve? From the provided code I can tel that you put examples how to recursively traverse a tree. Sure, you can do that. How is that related to this project?
DFS-
Graph
9 7
0 1
1 2
1 3
2 3
3 4
6 7
6 8
Result
Component 1 0 1 2 3 4
Component 2 5
Component 3 6 7 8
There are 3 connected components
The important things worth mentioning here is the use of forEachwith it
variable and ranges from Kotlin helped me quite a lot. Use of Pair and
variable like tv.first is also helpful.
enum class Color { BLACK, WHITE } var vert: MutableList<Color> = mutableListOf() var adj: MutableList<MutableList<Pair<Int, Int>>> = mutableListOf()
vert is a list of Color enum which is used track the visit status of each
node. WHITE denotes if it’s unvisited while BLACK means it’s visited. adj
maintains are graph in the form of adjacency list which list of list of Pairs. Pair contains two numbers of which first denotes the node and
second denotes the weight associated with that edge which is in this case
is 1.
the core DFS is very small
fun dfs(u: Int) {
vert[u] = Color.BLACK
print(" $u")
(0..adj[u].size-1).forEach {
val tv = adj[u][it]
if(vert[tv.first] == Color.WHITE) dfs(tv.first)
}
}
BFS Graph 9 7 0 1 1 2 1 3 2 3 3 4 6 7 6 8 Result u: 0 and [Node(color=BLACK, distance=0, parent=-1), Node(color=BLACK, distance=1, parent=1), Node(color=BLACK, distance=2, parent=2), Node(color=BLACK, distance=2, parent=3), Node(color=BLACK, distance=3, parent=4)] u: 6 and [Node(color=BLACK, distance=0, parent=-1), Node(color=BLACK, distance=1, parent=7), Node(color=BLACK, distance=1, parent=8)] u: 5 and [Node(color=BLACK, distance=0, parent=-1)]
use the following variables and enum class.
enum class Color {
BLACK, WHITE
}
var adj: MutableList<MutableList<Pair<Int, Int>>> = mutableListOf()
We make use of a data class Node to keep track of color for visiting,
distance and parent of the node while doing BFS.
On Wed, Oct 28, 2020, 05:47 Greg Kesler <[email protected] wrote:
@vibhu172000 https://github.com/vibhu172000 please, put some description to your PR. What does it solve? From the provided code I can tel that you put examples how to recursively traverse a tree. Sure, you can do that. How is that related to this project?
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/intuit/Traverser/pull/21#issuecomment-717616785, or unsubscribe https://github.com/notifications/unsubscribe-auth/APYLMOUQM2IFZVIR5YZPTUDSM5PIDANCNFSM4SUAYAFQ .
@vibhu172000 thanks again, I saw this in another PR. Still, the question is: how this is related to traverser? Have you tried to implement your dfs/bfs using traverser component from this project?
Actually I have decided an example in previous mail of bed, dfs in kotlin.
On Wed, Oct 28, 2020, 09:24 Greg Kesler <[email protected] wrote:
@vibhu172000 https://github.com/vibhu172000 thanks again, I saw this in another PR. Still, the question is: how this is related to traverser? Have you tried to implement your def/bfs using traverser component from this project?
— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/intuit/Traverser/pull/21#issuecomment-717679106, or unsubscribe https://github.com/notifications/unsubscribe-auth/APYLMOXMSI5KZMSPXD24AVDSM6IXNANCNFSM4SUAYAFQ .