Program EulerPath_Algorithm;(**************************************************************************}{ An Euler path (pronounced 'oiler') in a graph G is a path that uses each }{ arc of G exactly once and can exist in a connected graph iff there are }{ either no nodes whose degree is odd or exactly two nodes whose degree is }{ odd. For the case of no nodes posessing an odd degree, the path can
}{ begin at any node and will end there; for the case of two nodes posessing}{ an odd degree, the path must begin at one odd node and end at the other. }{--------------------------------------------------------------------------}{ Released to the public domain by Natural Systems. This routine may be
}{ freely distributed.
}{--------------------------------------------------------------------------}{ Natural Systems is the producer of DATA STRUCTURES (DS), a highly
}{ versital library of the most critical structures--such as graphs--for
}{ all Borland compilers supporting OOP.
}{
}{ Euler's, as well as the Dijkstra, Warshall, Bellman-Ford, Floyd's,
}{ Kruskal's (and many, many more) methods, are available in DS. And
}{ that's just one class--there's too many to list... (Of course, because }{ of its' object oriented nature, there are no restrictions or side-
}{ effects. Just good solid code!)
}{
}{ Contact Natural Systems on CompuServe @ [71301,1221], by phone/FAX @
}{ (617) 232-6951, or by post @ PO Box 968 / Brookline, MA / 02146 to get }{ more information about or, better yet, purchase DS. MasterCard & Visa
}{ Accepted.
}{**************************************************************************){$IfDef Windows}Uses WinCRT;{$Else}Uses CRT;{$EndIf}Const n = 5;Var M : Array [1..n, 1..n] of Word;Function IsOdd(x:LongInt) : Boolean;{**************************************************************************} BeginIf ( (x MOD 2) = 0 ) Then IsOdd := FalseElse IsOdd := True;{EndIf} End;{EndFunction}Procedure EulerPath;{**************************************************************************}{ Determins whether an Euler path exists in a connected graph with
}{ adjacency matrix M.
}{**************************************************************************} VarTotal : Integer;
{ Number of odd nodes found so far }Degree : Integer;
{ Degree of a node }i, j: Word;
{ indices } BeginTotal := 0;i := 1;While (Total2 Then Write('No Euler path exists')Else WriteLn('Euler path exists');{EndIf} End;{End EulerPath}Var i, j : Word;Begin M[1,1] := 0; M[1,2] := 1; M[1,3] := 0; M[1,4] := 0; M[1,5] := 0; M[2,1] := 0; M[2,2] := 0; M[2,3] := 1; M[2,4] := 0; M[2,5] := 0; M[3,1] := 1; M[3,2] := 0; M[3,3] := 0; M[3,4] := 1; M[3,5] := 0; M[4,1] := 0; M[4,2] := 0; M[4,3] := 0; M[4,4] := 0; M[4,5] := 0; M[5,1] := 1; M[5,2] := 0; M[5,3] := 1; M[5,4] := 0; M[5,5] := 0; For i := 1 To n DoBegin For j := 1 To n Do
Write(M[i, j]:3); {End For} WriteLn;End; {End For} EulerPath; WriteLn; M[4,5] := 1; For i := 1 To n DoBegin For j := 1 To n Do
Write(M[i, j]:3); {End For} WriteLn;End; {End For} EulerPath; ReadLn;End.参考资料：搜索的。:D
已赞过已踩过< |
