图的应用之一：一笔画问题 图的典型应用是一笔画问题，其他应用将在图论算法中涉及。 [例题] 编程找出图 1－2（1）的一笔画路线。 [分析与解]： (1)首先用邻接矩阵来表示图：如果 i,j 两点间有线段连接则值为 1，否则 为 0。 0 1 0 0 1 1 可用数组常量 links[i,j] 表示，即： 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 const links:array[1..n, 1..n] OF Integer= ((0,1,0,0,1,1), (1,0,1,1,0,1),(0,1,0,1,0,0), (O,1,1,0,1,1),(1,0,0,1,0,1), (1,1,0,1,1,0)); (2)计算每个点的度数存 dgr[i]中，如对于第 i 个顶点，可这样统计： for j:=1 to n do dgr[i]:=dgr[i]+links[i,j]; sum:=sum+dgr[i]; (3)统计奇点的个数，即 dgr 中有几个奇数，存 odt 中。 if odd(dgr[i]) then odt:=odt+1; start;=i; (4)如果 odt>2 则无解，否则从一个奇点开始搜索路线，其算法如下 1 

Nowd->r [程序清单] Program postal_route; const n = 6; links:array[1..n, 1..n] OF Integer= ((0,1,0,0,1,1), (1,0,1,1,0,1), (0,1,0,1,0,0), (0,1,1,0,1,1), (1,0,0,1,0,1), (1,1,0,1,1,0)); var dgr: array[1..n] of integer; i, j, r, sum, odt, start, nowd: integer; Procedure find_degree; Begin sum:=0; odt:=0; start:=1; For i:= 1 to n Do Begin dgr[i]:= 0; For j:= 1 to n do dgr[i]:= dgr[i] + links[i,j]; sum:= sum + dgr[i]; If odd(dgr[i]) Then Begin odt := odt + 1; start:= i End End; End; { main code .... } BEGIN Find_degree; if odt>2 Then 2 

Begin writeln ('no sulution . ');exit End; Nowd:= start; write(start); repeat r:=0; repeat r:=r+1; until (links[nowd,r]>0) and ((dgr[r]>1) or ((dgr[r]=1) and (sum=2))); links[nowd,r]:=0; links[r,nowd]:=0; sum:=sum-2; dec(dgr[nowd]); dec(dgr[r]); nowd :=r; write('->',r); until sum = 0; writeln; readln END. 运行结果为： 5->1->2->3->->4->2->6->4->5->6->1 3