第六章图
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
如果空了
排序方法总结简单排序法选择插入冒泡
先进排序法希快速其他
下载本文