Bei einem gerichteten Graphen den längsten Zyklus ausgeben.

Regeln

• Jedes sinnvolle Eingabeformat ist zulässig (z. B. Kantenliste, Konnektivitätsmatrix).
• Die Bezeichnungen sind nicht wichtig, daher können Sie den von Ihnen benötigten und / oder gewünschten Bezeichnungen Einschränkungen auferlegen, sofern sie keine zusätzlichen Informationen enthalten, die nicht in der Eingabe enthalten sind (z. B. können Sie nicht verlangen, dass die Knoten in Zyklen vorhanden sind mit ganzen Zahlen beschriftet, und andere Knoten sind mit alphabetischen Zeichenfolgen beschriftet).
• Ein Zyklus ist eine Folge von Knoten, die alle miteinander verbunden sind, und es wird kein Knoten wiederholt, außer dem Knoten, der Beginn und Ende des Zyklus ist ( [1, 2, 3, 1]ein Zyklus ist, aber [1, 2, 3, 2, 1]nicht).
• Wenn der Graph azyklisch ist, hat der längste Zyklus die Länge 0 und sollte daher eine leere Ausgabe ergeben (z. B. leere Liste, überhaupt keine Ausgabe).
• Das Wiederholen des ersten Knotens am Ende der Liste der Knoten im Zyklus ist optional ( [1, 2, 3, 1]und [1, 2, 3]bezeichnet denselben Zyklus).
• Wenn es mehrere Zyklen gleicher Länge gibt, können einer oder alle ausgegeben werden.
• Builtins sind zulässig, aber wenn Ihre Lösung eine verwendet, sollten Sie eine alternative Lösung einbeziehen, die keine trivialisierenden Builtins verwendet (z. B. ein Builtin, das alle Zyklen ausgibt). Die alternative Lösung wird jedoch nicht für Ihre Punktzahl angerechnet, so dass dies völlig optional ist.

Testfälle

In diesen Testfällen wird die Eingabe als eine Liste von Kanten (wobei das erste Element der Quellknoten und das zweite Element der Zielknoten ist) und die Ausgabe als eine Liste von Knoten ohne Wiederholung des ersten / letzten Knotens angegeben.

[(0, 0), (0, 1)] -> [0]
[(0, 1), (1, 2)] -> []
[(0, 1), (1, 0)] -> [0, 1]
[(0, 1), (1, 2), (1, 3), (2, 4), (4, 5), (5, 1)] -> [1, 2, 4, 5]
[(0, 1), (0, 2), (1, 3), (2, 4), (3, 0), (4, 6), (6, 8), (8, 0)] -> [0, 2, 4, 6, 8]
[(0, 0), (0, 8), (0, 2), (0, 3), (0, 9), (1, 0), (1, 1), (1, 6), (1, 7), (1, 8), (1, 9), (2, 1), (2, 3), (2, 4), (2, 5), (3, 8), (3, 1), (3, 6), (3, 7), (4, 1), (4, 3), (4, 4), (4, 5), (4, 6), (4, 8), (5, 0), (5, 8), (5, 4), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 9), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 8), (7, 9), (8, 0), (8, 1), (8, 2), (8, 5), (8, 9), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6)] -> [0, 9, 6, 7, 8, 2, 5, 4, 3, 1]
[(0, 0), (0, 2), (0, 4), (0, 5), (0, 7), (0, 9), (0, 11), (1, 2), (1, 4), (1, 5), (1, 8), (1, 9), (1, 10), (2, 0), (2, 1), (2, 3), (2, 4), (2, 5), (2, 6), (3, 0), (3, 1), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 11), (4, 1), (4, 3), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (5, 0), (5, 4), (5, 6), (5, 7), (5, 8), (5, 11), (6, 0), (6, 8), (6, 10), (6, 3), (6, 9), (7, 8), (7, 9), (7, 2), (7, 4), (7, 5), (8, 8), (8, 9), (8, 2), (8, 4), (8, 7), (9, 0), (9, 1), (9, 2), (9, 3), (9, 6), (9, 10), (9, 11), (10, 8), (10, 3), (10, 5), (10, 6), (11, 2), (11, 4), (11, 5), (11, 9), (11, 10), (11, 11)] -> [0, 11, 10, 6, 9, 3, 8, 7, 5, 4, 1, 2]

Mathematica, 80 58 Bytes

Dank JungHwan Min. Satte 22 Bytes gespart

(FindCycle[#,∞,All]/.{}->{Cases[#,v_v_]})[[-1,;;,1]]&

ist das Drei-Byte-Zeichen U+F3D5für den privaten Gebrauch \[DirectedEdge]. Reine Funktion mit dem ersten Argument #, das eine Liste gerichteter Kanten sein soll. Findet längste AllZyklen Infinityin Graph@#und ersetzt dann die leere Liste durch die Liste der Selbstschleifen. Zyklen werden als Listen von Kanten dargestellt und nach Länge sortiert. Daher nehmen wir den letzten derartigen Zyklus und nehmen von allen Kanten das erste Argument, um eine Liste von Scheitelpunkten im angegebenen Ausgabeformat zu erhalten.

Wenn nur Mathematica Schleifen als einen Zyklus von Länge behandelt 1( AcyclicGraphQ @ CycleGraph[1, DirectedEdges -> True]gibt True, ernsthaft), dann könnten wir andere 26Bytes speichern :

FindCycle[#,∞,All][[-1,;;,1]]&

Haskell , 157 154 150 Bytes

import Data.List
g#l=nub[last$(e:d):[d|p==last q||e`elem`init d]|d@(p:q)<-l,[e,f]<-g,p==f]
h g=snd$maximum$((,)=<<length)<$>[]:until((==)=<<(g#))(g#)g

Probieren Sie es online!

Vielen Dank an @Laikoni und @Zgrab, dass sie ein paar Bytes gespart haben!

Dies ist ein sehr ineffizientes Programm:

Die erste Funktion #nimmt eine Liste von Pfaden l(eine Liste von Listen von Zahlen) und versucht, die Elemente von zu erweitern, lindem jede mögliche Kante (eine Liste der Länge 2) von gzu jedem Element von vorangestellt wird l. Dies geschieht nur, wenn das Element von lnicht bereits ein Zyklus ist und der neue Knoten, der vorangestellt werden würde, nicht bereits im Element von enthalten ist l. Wenn es sich bereits um einen Zyklus handelt, stellen wir nichts voran, sondern fügen ihn erneut zur neuen Liste der Pfade hinzu. Wenn wir ihn erweitern können, fügen wir den erweiterten Pfad zur neuen Liste hinzu, andernfalls fügen wir ihn nicht zur neuen Liste hinzu .

Jetzt hversucht die Funktion wiederholt, diese Pfade (beginnend mit der Liste der Kanten selbst) zu erweitern, bis wir einen festen Punkt erreichen, dh wir können keinen Pfad mehr erweitern. Zu diesem Zeitpunkt haben wir nur Zyklen in unserer Liste. Dann geht es nur noch darum, den längsten Zyklus auszuwählen. Offensichtlich erscheinen die Zyklen mehrmals in dieser Liste, da jede mögliche zyklische Drehung eines Zyklus wieder ein Zyklus ist.

Pyth, 20 Bytes

eMefqhMT.>{eMT1s.pMy

Testsuite

Nimmt eine Liste von Kanten auf, wie in den Beispielen.

Erläuterung:

eMefqhMT.>{eMT1s.pMy
eMefqhMT.>{eMT1s.pMyQ    Variable introduction
                   yQ    Take all subsets of the input, ordered by length
                .pM      Reorder the subsets in all possible ways
               s         Flatten
                         (This should be a built in, I'm going to make it one.)
   f                     Filter on (This tests that we've found a cycle)
    qhMT                 The list of first elements of edges equals
           eMT           The last elements
         .>   1          Rotated right by 1
        {                Deduplicated (ensures no repeats, which would not be a
                         simple cycle)
  e                      Take the last element, which will be the longest one.
eM                       Take the last element of each edge, output.

Bash + bsdutils, 129 Bytes

sed 's/^\(.*\) \1$/x \1 \1 x/'|sort|(tsort -l>&-)|&tr c\\n '
 '|sed 's/x //g'|awk 'm<NF{m=NF;gsub(/[^0-9 ] ?/,"");print}'|tail -1

tsort erledigt das ganze schwere Heben, aber sein Ausgabeformat ist ziemlich einzigartig und es erkennt keine Zyklen der Länge 1. Beachten Sie, dass dies mit GNU tsort nicht funktioniert.

Nachprüfung

--- t1 ---
0
--- t2 ---
--- t3 ---
0 1
--- t4 ---
1 2 4 5
--- t5 ---
0 2 4 6 8
--- t6 ---
0 2 1 6 3 7 4 8 9 5
--- t7 ---
0 11 10 3 1 2 4 7 5 8 9 6

JavaScript (ES6), 173 163 156 145 139 Bytes

5 Bytes dank @Neil gespart

f=(a,m,b=[])=>a.map(z=>!([x,y]=z,m&&x-m.slice(-1))&&b.length in(c=(n=m||[x],q=n.indexOf(y))?~q?b:f(a.filter(q=>q!=z),[...n,y]):n)?b=c:0)&&b

Testschnipsel

f=(a,m,b=[])=>a.map(z=>!([x,y]=z,m&&x-m.slice(-1))&&b.length in(c=(n=m||[x],q=n.indexOf(y))?~q?b:f(a.filter(q=>q!=z),[...n,y]):n)?b=c:0)&&b

g=a=>console.log("Input:",JSON.stringify(a),"Output:",JSON.stringify(f(a)))

g([[0,0]])
g([[0,1],[1,2]])
g([[0,1],[1,0]])
g([[0,1],[1,2],[2,0]])
g([[0,1],[1,2],[1,3],[2,4],[4,5],[5,1]])
g([[0,1],[0,2],[1,3],[2,4],[3,0],[4,6],[6,8],[8,0]])

Haskell , 109 108 Bytes

import Data.List
f g=last$[]:[b|n<-[1..length g],e:c<-mapM(\_->g)[1..n],b<-[snd<$>e:c],b==nub(fst<$>c++[e])]

Eine Brute-Force-Lösung: Generieren Sie alle Listen von Kanten mit zunehmender Länge bis zur Länge der Eingabe, behalten Sie die Zyklen bei und geben Sie die letzte zurück. Nimmt das Diagramm im Format [(1,2),(2,3),(2,4),(4,1)]. Probieren Sie es online!

Erläuterung

f g=                    -- Define function f on input g as
  last$                 -- the last element of the following list
  []:                   -- (or [], if the list is empty):
  [b|                   --  lists of vertices b where
   n<-[1..length g],    --  n is between 1 and length of input,
   e:c<-                --  list of edges with head e and tail c is drawn from
    mapM(\_->g)[1..n],  --  all possible ways of choosing n edges from g,
   b<-[snd<$>e:c],      --  b is the list of second elements in e:c,
   b==                  --  and b equals
    nub(fst<$>c++[e])]  --  the de-duplicated list of first elements
                        --  in the cyclic shift of e:c.

MATLAB, 291 260 Bytes

Nimmt eine Adjezenzmatrix an, Ain der eine Kante (i,j)durch ein 1in gekennzeichnet A(i,j)ist und Ain allen anderen Einträgen Null ist. Die Ausgabe ist eine Liste eines längsten Zyklus. Die Liste ist leer, wenn überhaupt kein Zyklus vorhanden ist, und die Liste enthält Start- und Endpunkt, wenn ein Zyklus vorhanden ist. Es verwendet 1-basierte Indizierung.

Diese Lösung verwendet keine integrierten Funktionen für Diagramme.

function c=f(A);N=size(A,1);E=eye(N);c=[];for j=1:N;l=g(j);if numel(l)>numel(c);c=l;end;end;function p=g(p)if ~any(find(p(2:end)==p(1)))e=E(p(end),:)Q=find(e*A)k=[];for q=Q;if ~ismember(q,p(2:end))n=g([p,q]);if numel(n)>numel(k);k=n;end;end;end;p=k;end;end;end

Leider wird dies in TryItOnline nicht ausgeführt, da eine Funktion innerhalb einer Funktion verwendet wird, die rekursiv ist. Mit ein wenig Modifikation können Sie es auf octave-online.net ausprobieren .

Für den allerletzten Testfall habe ich einen alternativen längsten Zyklus gefunden [0 2 1 4 3 5 7 8 9 11 10 6 0](diese Notation verwendet eine 0-basierte Indizierung)

Erläuterung

Der grundlegende Ansatz hierbei ist, dass wir von jedem Knoten ein BFS durchführen und sicherstellen, dass wir keinen der Zwischenknoten außer dem Startknoten erneut besuchen. Mit dieser Idee können wir alle möglichen Zyklen sammeln und einfach den längsten auswählen.

function c=f(A);
N=size(A,1);
E=eye(N);
c=[]; % current longest cycle
for j=1:N;                                      % iterate over all nodes
    l=getLongestCycle(j);                       % search the longest cycle through the current node
    if numel(l)>numel(c);                       % if we find a longer cycle, update our current longest cycle
        c=l;
    end;

end;

    function p=getLongestCycle(p);              % get longest cycle from p(1) using recursion
        if ~any(find(p(2:end)==p(1)));          % if we just found a cycle, return the cycle do nothing else, OTHERWISE:
            e=E(p(end),:);                      % from the last node, compute all outgoing edges
            Q=find(e*A);                        
            k=[];                               
            for q=Q;                            % iterate over all outogoin edges
                if ~ismember(q,p(2:end));       % if we haven't already visited this edge,
                    n=getLongestCycle([p,q]);   % recursively search from the end node of this edge
                    if numel(n)>numel(k);       % if this results in a longer cycle, update our current longest cycle
                        k=n;
                    end;
                end;
            end;
            p=k;
        end;
    end; 
end