PROC dfs(g:adjlist; I,j:vtxptr);

7.15 PROC CreatAdjList(VAR G:AdjList; V:string; A:ArcList);

{由各顶点信息V和各条弧的信息A建立有向图的邻接表G。}

{V为字符串，每个顶点由一个字符V[i]表示，共有length(V)}

{个顶点；A为顺序表，每条弧由其依附的两个顶点（字符）}

{的序偶<A.pair[j].x,A.pair[j].y>表示，共有A.n条弧。}

FOR i:=1 TO length(V) DO {邻接表初始化，length(V)个顶点}

[ G[i].vexdata:=V[i]; G[i].firstarc:=NIL ]

FOR i:=1 TO A.n DO {输入A.n条弧}

[ x:=A.pair[i].x ;

y:=A.pair[i].y; {输入一每条弧依附的两个顶点}

i:=LOC_VERTEX(G,x); {判定顶点x在顶点向量中的位序}

j:=LOC_VERTEX(G,y); {判定顶点y在顶点向量中的位序}

new(p);

p^.adjvex:=j;

p^.nextarc:=G[i].firstarc;

G[i].firstarc:=p {弧结点插入邻接点链表}

]

ENDP;

7．16 PROC InsertVertex(VAR G:Graph; v:vertex);

{在采用邻接矩阵存储结构的图G上插入顶点v }

FOR i:=1 TO n DO G[i,n+1]:=0;

FOR i:=1 TO n DO G[n+1,i]:=0;

G[n+1,n+1]:=0; {变为n+1个顶点的邻接矩阵}

PROC InsertArc(VAR G:Graph; v,w:vertex);

{在采用邻接矩阵存储结构的图G上插入弧<v,w>}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

j:=LOC_VERTEX(G,w); {判定顶点w在顶点向量中的位序}

G[i,j]:=1; G[j,i]:=1;

PROC DeleteVertex(VAR G:Graph; v:vertex);

{在采用邻接矩阵存储结构的图G上删除顶点v，从n个顶点}

{变成个n-1顶点,也即从n阶方阵变为n-1阶方阵}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

{将去掉第i行第i列的n阶方阵变为n-1阶方阵}

FOR j:=1 TO i-1 DO {左上角}

FOR k:=1 TO i-1 DO G1[j,k]:=G[j,k];

FOR j:=i+1 TO n DO {左下角}

FOR k:=1 TO i-1 DO G1[j-1,k]:=G[j,k];

FOR j:= 1 TO i-1 DO {右上角}

FOR k:=i+1 TO n DO G1[j,k-1]:=G[j,k];

FOR j:=i+1 TO n DO {右下角}

FOR k:= i+1 TO n DO G1[j-1,k-1]:=G[j,k];

PROC DeleteArc(VAR G:Graph; v,w:vertex);

{在采用邻接矩阵存储结构的图G上删除弧<v,w>}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

j:=LOC_VERTEX(G,w); {判定顶点w在顶点向量中的位序}

G[i,j]:=0; G[j,i]:=0;

{ 若是有向图只作： G[i,j]:=0 }

ENDP;

7．17

PROC InsertVertex(VAR G:AdjList; v:vertex);

{在采用邻接表存储结构的图G上插入顶点v }

G[n+1].vexdata:=v; G[n+1].firstarc:=NIL

ENDP;

PROC InsertArc(VAR G: AdjList; v,w:vertex);

{在采用邻接表存储结构的图G上插入弧<v,w>}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

j:=LOC_VERTEX(G,w); {判定顶点w在顶点向量中的位序}

new(p);

p^.adjvex:=j;

p^.nextarc:=G[i].firstarc;

G[i].firstarc:=p {弧结点插入邻接点链表}

{若是无向图，则应再生成一结点，插入到w的邻接点的链表中}

{ new(p);

p^.adjvex:=i;

p^.nextarc:=G[j].firstarc;

G[j].firstarc:=p {弧结点插入邻接点链表}

}

ENDP;

PROC DeleteArc(VAR G: AdjList; v,w:vertex);

{在采用邻接表存储结构的有向图G上删除弧<v,w>}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

j:=LOC_VERTEX(G,w); {判定顶点w在顶点向量中的位序}

p:=G[i].firstarc; q:=p; {q是p的前驱}

IF p^.adjvex=j

THEN G[i].firstarc:=p^.nextarc {w是v的第一邻接点}

ELSE [ WHILE p^.adjvex<>j DO

[ q:=p; p:=p^.nextarc ]

q^.nextarc:=p^.nextarc;

]

dispose(p);

ENDP;

7.17 (续)

PROC DeleteVertex(VAR G: AdjList; v:vertex);

{在采用邻接表存储结构的图G上删除顶点v，所有与该顶点相关}

{的弧都应删除，这一向量元素作删除标记。若真删除，得作许多调整}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

G[i].vexdata:=’#’; p:=G[i].firstarc; {‘#’是删除标记}

WHILE p<>NIL DO {将从v发出的弧都删除}

[ q:=p; p:=p^.nextarc; dispose(q) {回收结点空间} ]

G[i].firstarc:=NIL

FOR j:=1 TO n DO {删除所有以v为弧头{序号为 i}的弧}

IF i<>j THEN

[ p:=G[j].firstarc;

IF p<>NIL THEN

IF p^.adjvex=i

THEN G[j].firstarc:=p^.nextarc

{v是第一邻接点}

ELSE [found:=false;{v是否是邻接点的标志}

WHILE (p<>NIL) AND NOT found DO

IF p^.adjvex<>i

THEN [q:=p; p:=p^.nextarc]

ELSE [ q^.nextarc:=p^.nextarc;

dispose(p);

found:=true

]

] {END OF FOR j:=1 TO n DO}

ENDP;

7．18 PROC DeleteVertex(VAR G: OrthoList; v:vertex);

{在采用十字链表存储结构的图G上删除顶点v，所有与该顶点相}

{关的弧都应删除，这一向量元素作删除标记。若真删除，得作许}

{多调整。}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

G[i].data:=’#’; G[i].firstin:=G[I].firstout:=NIL;

{删除顶点，作标记}

FOR j:=1 TO n DO { 删除以顶点v为弧头的弧}

IF j<>i THEN

[ p:=G[j].firstout; {先查看第一邻接点是否是v}

IF p^.headvex=v

THEN G[j].firstout:=p^.firstout

ELSE [q:=p; found:=false; {查以v为弧头的顶点}

WHILE (p<>NIL) AND NOT found DO

IF p^.headvex=v

THEN [q^.tlink:=p^.tlink;found:=true]

ELSE [q:=p; p:=p^.tlink]

]

FOR j:=1 TO n DO { 删除以顶点v为弧尾的弧}

IF j<>i THEN

[ p:=G[j].firstin; {先查看第一邻接点是否是v}

IF p^.tailvex=v

THEN G[j].firstin:=p^.firstin

ELSE

[q:=p; found:=false; {查以v为弧尾头的顶点}

WHILE (p<>NIL) AND NOT found DO

IF p^.tailvex=v

THEN [ q^.hlink:=p^.hlink; found:=true; ]

ELSE [ q:=p; p:=p^.hlink]

]

] {END OF FOR j:=1 TO n DO}

ENDP;

7.18 (续)

PROC InsertVertex(VAR G:OrthoList; v:vertex);

{在采用十字链表存储结构的图G上插入顶点v }

G[n+1].data:=v; G[n+1].firstin:=NIL; G[n+1].firstout:=NIL;

PROC InsertArc(VAR G: OrthoList; v,w:vertex);

{在采用十字链表存储结构的图G上插入弧<v,w>}

i=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

j:=LOC_VERTEX(G,w); {判定顶点w在顶点向量中的位序}

new(p);

p^.headvex:=i; p^.tailvex:=j;

p^.tlink:=G[i].firstout;

G[i].firstout:=p {弧结点插入i的邻接点链表}

p^.hlink:=G[j].firstin; G[j].firstin:=p {插入以j为弧头的链表}

PROC DeleteArc(VAR G: OrthoList; v,w:vertex);

{在采用十字链表存储结构的有向图G上删除弧<v,w>}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

j:=LOC_VERTEX(G,w); {判定顶点w在顶点向量中的位序}

p:=G[i].firstout; {先查看第一邻接点是否是w}

IF p^.headvex=w THEN G[i].firstout:=p^.firstout

ELSE [q:=p; found:=false;

WHILE (p<>NIL) AND NOT found DO

IF p^.headvex=w

THEN [q^.tlink:=p^.tlink;found:=true]

ELSE [q:=p; p:=p^.tlink]

]

p:=G[j].firstin; {先查看第一邻接点是否是v}

IF p^.tailvex=v THEN G[j].firstin:=p^.firstin

ELSE [q:=p; found:=false;

WHILE (p<>NIL) AND NOT found DO

IF p^.tailvex=v

THEN [q^.hlink:=p^.hlink; found:=true; ]

ELSE [q:=p; p:=p^.hlink]

ENDP;

7.197．18 PROC DeleteVertex(VAR G: OrthoList; v:vertex);

{在采用十字链表存储结构的图G上删除顶点v，所有与该顶点相}

{关的弧都应删除，这一向量元素作删除标记。若真删除，得作许}

{多调整。}

i:=LOC_VERTEX(G,v); {判定顶点v在顶点向量中的位序}

7.22 PROC Connect_DFS(VAR g:adjlisttp,i,j:vtxptr)

{基于图的深度优先策略，本算法判断以邻接表为存储结构的有}

{向图g中，是否存在顶点i到顶点j的路径。i<=i,j<=n,i<>j }

PROC dfs(g:adjlist;i,j:vtxptr);

{图g用邻接表存储。本算法从顶点 i 出发，深度优先遍历，}

{若遍历到j结点，则说明顶点i和j有通路。}

visited[i]:=true;

IF i=j

THEN found:=true { i和j有通路}

ELSE [ p:=g[i].firstarc;

WHILE p<>NIL DO

[ k:=p^.adjvex;

IF NOT visited[k] THEN dfs(g,k,j);

IF NOT found THEN p:=p^.nextarc

]

ENDP; {END OF PROC dfs }

{调用dfs的主过程如下：}

[ visited[1..n]:=false; found:=false;{标志，全程变量}

readln(i,j); {读入顶点(i,j)} dfs(g,i,j);

IF found THEN writeln(‘顶点’ , i , ’ 和 ‘ ,j,’ 有通路’)

ELSE writeln(‘顶点 ‘ ,i,’ 和 ‘,j,’ 没有通路’)

] {END OF PROC OF path_i_to_j }

ENDP;

7．23 PROC bfs(g:adjlist; i,j:vtxptr);

{算法说明同上，这里是宽度优先遍历}

INITQUEUE(q); ENQUEUE(q,i);

WHILE (NOT EMPTY(q)) AND (NOT found ) DO

[i:=DELQUEUE(q); visited[i]:=true;

IF i=j THEN found:=true

ELSE [ p:=g[i].firstarc;

WHILE p<>NIL DO

[ w:=p^.adjvex;

IF NOT visited[w] THEN ENQUEUE(q,w);

p:=p^.nextarc

]

ENDP; {END OF PROC dfs }

7.38 PROC InversePolish(G:Adjlist; v:vtxptr; VAR ip:String);

{有向无环图G用邻接表存储，四则运算算术表达式用G表示。}

{假设表达式中操作数都是单字母变量。本算法求该表达式的逆}

{波兰表达式。假定v是有向无环图的入度为0的顶点。}

P:=G[v].firstarc;

WHILE p<>NIL DO

[ w:=p^.adjvex; InversePolish(G,w,ip);

p:=p^.nextarc;

]

ip:=ip+G[v].vexdata; {逆波兰表达式存在ip 字符串中}

ENDP；

7.38

{以下是非递归算法}

PUSH（s,v）;

WHILE NOT EMPTY(s) DO

[j:=POP(s);

p:=G[I].firstarc;

WHILE p<>NIL DO

[ w:=p^.adjvex; {邻接点}；

PUSH(s,w);

P:=G[w].firstarc; {w的第一邻接点}

]

w:=POP(s); ip:=ip+G[w].vexdata;

p:=p^.nextarc

]