# Tag Info

## New answers tagged graph-theory

0

R, 89 bytes R=function(G,p={})if(!is.list(G),p,(A=lapply(G,R,c(p,el(G))))[[which.max(lengths(A))]]) Try it online! Recursive function taking a tree as input (for the input format see the TIO) and returning the subtree of maximum length.

1

Red, 95 bytes f: function[x s][m: []foreach i select x s[p: f x i if(length? p)> length? m[m: p]]rejoin[m s]] Try it online! Takes input as an adjacency list plus the starting node in the same form as in challenge specification. Returns the longest path in reverse order.

1

PowerShell, 114 109 104 103 96 bytes param($s,$e)$e|%{$p=($p+,"$_"*!(($a=$_)-$s))-replace"\b$a$",$_} $p|sort{(-split$_).count}-b 1 Try it online! Stores paths as an array of strings. Each path contains a list of vertices separated by spaces. Less golfed: param($startVertex,$edges) $edges|%{$fromVertex = $_$pathes += ,&...

2

Jelly, 13 12 bytes ;ⱮịṪ¥¥€Ẏ¥ƬẎṪ Try it online! A dyadic link taking the start node as the left argument and the list of lists of child nodes as the right argument. The start node is expected to be supplied as [[x]] where x is the number of the node. Uses 1-indexing since that’s the way Jelly is written. Thanks to @JonathanAllan for saving a byte! ...

0

Wolfram Language (Mathematica), 47 bytes Pick[#,#,#&@@#~Level~{Depth@#-1}]//._[]:>Set@$& Try it online! Input an expression - Mathematica's expressions are trees. For example: Pick almost does the job, but non-leaf nodes with successors still remain. Then we remove all empty nodes. Also 47 bytes Select@Not@*FreeQ[#&@@#~Level~{Depth@#-2}]//@#&... 2 Charcoal, 23 bytes ⊞υ⟦θ⟧ＦυＦ§η§ι⁰⊞υ⁺⟦κ⟧ιＩ⊟υ Try it online! Link is to verbose version of code. Takes the root as the first input and an array of lists of adjacencies as the second input and outputs the longest route in reverse order. Explanation: ⊞υ⟦θ⟧ Start a breadth first search with a list of just the root node. Ｆυ Process the lists in the order they ... 1 Kotlin 1.4.20, 92 bytes fun f(e:Map<Int,Set<Int>>,s:Int):List<Int> =(e[s]?.map{f(e,it)}?.maxBy{it.size}?:setOf())+s Usage fun main() = println(f(mapOf(0 to setOf(1, 2, 3), 1 to setOf(), 2 to setOf(4, 5), 3 to setOf(6), 4 to setOf(7), 5 to setOf(), 6 to setOf(8), 7 to setOf(9), 8 to setOf(), 9 to setOf()), 0)) Note This uses a deprecated ... 2 JavaScript (Node.js), 92 bytes a=>g=(h,...t)=>v=1/h?a[h].map((n,j)=>g[j]?0:g[j]=n&&t.push(j))[g(...t)]?[h,...v]:v||[h]:0 Try it online! Input the adjacency matrix of graph and the start node currily. This one works on graphs with cycles. JavaScript (Node.js), 68 bytes a=>s=>(g=(h,...t)=>v=h&&g(...t,...a[h].map(j=&... 4 Coconut, 45 bytes Takes the graph in the format shown in the example test case f=(g,s)->[s]+max(map(f$g,g[s])::[[]],key=len) Try it online! Uses Coconuts lambda syntax, \$ for partial application and :: as an operator for itertools.chain. The same would be 56 bytes in Python: f=lambda g,s:[s]+max([f(g,x)for x in g[s]]+[[]],key=len) Try it online!

Top 50 recent answers are included