africa = CountryData["Africa"];

borderQ[cont1_, cont2_] := 
  MemberQ[CountryData[cont1, "BorderingCountries"], CountryData[cont2]];

adjm = Table[If[borderQ[u, v] || borderQ[v, u], 1, 0], {u, africa}, {v, africa}];

coords=Reverse[CountryData[#,"CenterCoordinates"]&/@africa,2];

southgraph=AdjacencyGraph[africa,adjm,VertexCoordinates->coords, EdgeStyle->Directive[Thickness[.003],White], VertexStyle->Directive[EdgeForm[GrayLevel[.8]],GrayLevel[.7]], VertexSize->.8];

tour=FindPostmanTour[southgraph];

path = tour[[1, All, 1]];
vrule = Thread[VertexList[southgraph] -> Range[VertexCount[southgraph]]];
route = GraphEmbedding[southgraph][[Join[path, {path[[1]]}] /. vrule]];

Show[{Graphics[{LightGray, CountryData[#, "Polygon"] & /@ africa}], HighlightGraph[southgraph, path[[1]], VertexLabels -> "Name"], Graphics[{Arrowheads[Join[{0}, ConstantArray[.018, 45]]], GrayLevel[.3], Arrow[BSplineCurve[route, SplineDegree -> 2]]}]}]