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.

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!