软件技术基础算法总结

第六章图

1、图的遍历

按深度优先遍历图（邻接表）

VoidDFS(t)//t为出发点

{ift=nullreturn//如果出发点为空，返回

Print(t);//访问当前节点

Visit[t]=1;//记录访问过当前节点

While(t->visit!=null)//遍历该节点的所有邻接点

{t=t->ne_t//

If(visit[t]!=1)//如果没访问过则深度遍历DFS(t)

return非递归算法

DFS(T)

当栈非空

{弹出邻接点未标记的进栈并标记按广度优先的遍历图（邻接表）

VoidBFS(t)//

{入队如果队非空

{出队将该节点没有访问过的邻接节点入队

VoidBFS(t)Ift=nullreturn;

Visit[t]=1;

Getinq(t);

While(!qempty)T=outq;

Vist(t)

While(t!=null)T=t->ne_t

If(visit(t)==0)

{getq(q)

Visti(t)=1

2、克鲁斯卡尔方法构造最小代价生成树Voidklsk(t，g,n)

{E(T)=null

For(i=1;i

{找到图中最短边

将最短边在e(g)删除

If(不构成回路)该边添加进E（t）Elsei--;3、普莱姆法构造最小代价生成树

{将E（t）=null

U={1}

While(u!=v)

{选出最小边（u,v）u在U中，v在U-V中E(T)=E(T)U(u,v)

U(T)=UU（u，v）

4、图的最短路径生成

Floyd

For(k=0;k

{for(0

For(0

{if(a +a

{a =a +a ;

S =k;5、DKASLIO

FOR(0

{for(0

V(j)=m[i][j]

While(0

{t=findmin(v)

V(t)=-1

For(0

Topsort()Stacks

找入度为零对人栈内For(0

{如果非空

弹出并输出

Ptr=k->link

当ptr不为空时

Ptr->count--;

如果为零则压入站内ptr=->ptr->link

如果空了

排序方法总结简单排序法选择插入冒泡

先进排序法希快速其他