define M 20资料.docx

define M 20资料.docx

《define M 20资料.docx》由会员分享，可在线阅读，更多相关《define M 20资料.docx（20页珍藏版）》请在冰点文库上搜索。

defineM20资料

#defineM20

#include

#include

#include

/*定义图*/

typedefstruct{

 intV[M];

 intR[M][M];

 intvexnum;

}Graph;

/*创建图*/

voidcreatgraph（Graph*g,intn）

{

 inti,j,r1,r2;

 g->vexnum=n;

 /*顶点用i表示*/

 for（i=1;i<=n;i++）

 {

   g->V[i]=i;

 }

/*初始化R*/

 for（i=1;i<=n;i++）

  for（j=1;j<=n;j++）

   {

     g->R[i][j]=0;

   }

/*输入R*/

 printf（"PleaseinputR（0,0END）:

\n"）;

 scanf（"%d,%d",&r1,&r2）;

 while（r1!

=0&&r2!

=0）

  {

   g->R[r1][r2]=1;

   g->R[r2][r1]=1;

   scanf（"%d,%d",&r1,&r2）;

  }

}

/*打印图的邻接矩阵*/

voidprintgraph（Graph*g）

{

inti,j;

for（i=1;i<=g->vexnum;i++）

{for（j=1;j<=g->vexnum;j++）

  {

    printf（"%2d",g->R[i][j]）;

  }

  printf（"\n"）;

  }

}

/*全局变量：

访问标志数组*/

intvisited[M];

/*访问顶点*/

voidvisitvex（Graph*g,intvex）

{

printf（"%d",g->V[vex]）;

}

/*获取第一个未被访问的邻接节点*/

intfirstadjvex（Graph*g,intvex）

{

intw,i;

for（i=1;i<=g->vexnum;i++）

 {

  if（g->R[vex][i]==1&&visited[i]==0）

   {

     w=i;

     break;

   }

  else

   {

     w=0;

   }

 }

 returnw;

}

/*获取下一个未被访问的邻接节点（深度遍历）*/

intnextadjvex（Graph*g,intvex,intw）

{

 intt;

 t=firstadjvex（g,w）;

 returnt;

}

/*深度递归遍历*/

 voiddfs（Graph*g,intvex）

  {

   intw;

   visited[vex]=1;

   visitvex（g,vex）;

   for（w=firstadjvex（g,vex）;w>0;w=nextadjvex（g,vex,w））

     if（!

visited[w]）

      {

dfs（g,w）;

      }

  }

  voiddfstraverse（Graph*g）

  {

    inti;

    for（i=1;i<=g->vexnum;i++）

      visited[i]=0;

    for（i=1;i<=g->vexnum;i++）

      if（!

visited[i]）

        {dfs（g,i）;}

  }

/*定义队列*/

typedefstruct{

intV[M];

intfront;

intrear;

}Queue;

/*初始化队列*/

initqueue（Queue*q）

{

 q->front=0;

 q->rear=0;

}

/*判断队列是否为空*/

intquempty（Queue*q）

{

 if（q->front==q->rear）

 {

  return0;

 }

 else

 {

  return1;

 }

}

/*入队操作*/

enqueue（Queue*q,inte）

{

 if（（q->rear+1）%M==q->front）

  {

   printf（"Thequeueisoverflow!

\n"）;

   return0;

  }

  else

  {

   q->V[q->rear]=e;

   q->rear=（q->rear+1）%M;

   return1;

  }

}

/*出队操作*/

dequeue（Queue*q）

{

 intt;

 if（q->front==q->rear）

  {

    printf（"Thequeueisempty!

\n"）;

    return0;

  }

  else

  {

    t=q->V[q->front];

    q->front=（q->front+1）%M;

    returnt;

  }

}

/*广度遍历*/

voidbestraverse（Graph*g）

{

 inti;

 Queue*q=（Queue*）malloc（sizeof（Queue））;

 for（i=1;i<=g->vexnum;i++）

 {

  visited[i]=0;

 }

 initqueue（q）;

 for（i=1;i<=g->vexnum;i++）

 {

   if（!

visited[i]）

    {

      visited[i]=1;

      visitvex（g,g->V[i]）;

      enqueue（q,g->V[i]）;

      while（!

quempty（q））

       {

         intu,w;

         u=dequeue（q）;

         for（w=firstadjvex（g,u）;w>0;w=nextadjvex（g,u,w））

           {

             if（!

visited[w]）

              {

                visited[w]=1;

  visitvex（g,w）;

                enqueue（q,w）;

              }

           }

       }

    }

 }

}

/*主程序*/

main（）

{

 intn;

 Graph*g=（Graph*）malloc（sizeof（Graph））;

 charmenu;

 printf（"Pleaseinputthenumberofvertex:

\n"）;

 scanf（"%d",&n）;

 creatgraph（g,n）;

 printf（"Thisisthelinjiejuzhenofgraph:

\n"）;

 printgraph（g）;

 input:

 printf（"Choose:

\nb:

Breadth_first\nd:

Depth_first\nq:

quit\n"）;

 while（（menu=getchar（））=='\n'）;

 if（menu=='b'）

   {

     printf（"Breadth_first:

\n"）;

     bestraverse（g）;

     printf（"\n"）;

     gotoinput;

   }

 elseif（menu=='d'）

   {

     printf（"Depth_first:

\n"）;

     dfstraverse（g）;

     printf（"\n"）;

     gotoinput;

   }

 elseif（menu=='q'）

   {

    exit（0）;

   }

 else

   {

     printf（"Inputerror!

\nChoose:

\nb:

Breadth_first\nd:

Depth_first\nq:

quit\n"）;

   }}

#defineM20

#include

#include

#include

/*定义图*/

typedefstruct{

 intV[M];

 intR[M][M];

 intvexnum;

}Graph;

/*创建图*/

voidcreatgraph（Graph*g,intn）

{

 inti,j,r1,r2;

 g->vexnum=n;

 /*顶点用i表示*/

 for（i=1;i<=n;i++）

 {

   g->V[i]=i;

 }

/*初始化R*/

 for（i=1;i<=n;i++）

  for（j=1;j<=n;j++）

   {

     g->R[i][j]=0;

   }

/*输入R*/

 printf（"PleaseinputR（0,0END）:

\n"）;

 scanf（"%d,%d",&r1,&r2）;

 while（r1!

=0&&r2!

=0）

  {

   g->R[r1][r2]=1;

   g->R[r2][r1]=1;

   scanf（"%d,%d",&r1,&r2）;

  }

}

/*打印图的邻接矩阵*/

voidprintgraph（Graph*g）

{

inti,j;

for（i=1;i<=g->vexnum;i++）

{for（j=1;j<=g->vexnum;j++）

  {

    printf（"%2d",g->R[i][j]）;

  }

  printf（"\n"）;

  }

}

/*全局变量：

访问标志数组*/

intvisited[M];

/*访问顶点*/

voidvisitvex（Graph*g,intvex）

{

printf（"%d",g->V[vex]）;

}

/*获取第一个未被访问的邻接节点*/

intfirstadjvex（Graph*g,intvex）

{

intw,i;

for（i=1;i<=g->vexnum;i++）

 {

  if（g->R[vex][i]==1&&visited[i]==0）

   {

     w=i;

     break;

   }

  else

   {

     w=0;

   }

 }

 returnw;

}

/*获取下一个未被访问的邻接节点（深度遍历）*/

intnextadjvex（Graph*g,intvex,intw）

{

 intt;

 t=firstadjvex（g,w）;

 returnt;

}

/*深度递归遍历*/

 voiddfs（Graph*g,intvex）

  {

   intw;

   visited[vex]=1;

   visitvex（g,vex）;

   for（w=firstadjvex（g,vex）;w>0;w=nextadjvex（g,vex,w））

     if（!

visited[w]）

      {

dfs（g,w）;

      }

  }

  voiddfstraverse（Graph*g）

  {

    inti;

    for（i=1;i<=g->vexnum;i++）

      visited[i]=0;

    for（i=1;i<=g->vexnum;i++）

      if（!

visited[i]）

        {dfs（g,i）;}

  }

/*定义队列*/

typedefstruct{

intV[M];

intfront;

intrear;

}Queue;

/*初始化队列*/

initqueue（Queue*q）

{

 q->front=0;

 q->rear=0;

}

/*判断队列是否为空*/

intquempty（Queue*q）

{

 if（q->front==q->rear）

 {

  return0;

 }

 else

 {

  return1;

 }

}

/*入队操作*/

enqueue（Queue*q,inte）

{

 if（（q->rear+1）%M==q->front）

  {

   printf（"Thequeueisoverflow!

\n"）;

   return0;

  }

  else

  {

   q->V[q->rear]=e;

   q->rear=（q->rear+1）%M;

   return1;

  }

}

/*出队操作*/

dequeue（Queue*q）

{

 intt;

 if（q->front==q->rear）

  {

    printf（"Thequeueisempty!

\n"）;

    return0;

  }

  else

  {

    t=q->V[q->front];

    q->front=（q->front+1）%M;

    returnt;

  }

}

/*广度遍历*/

voidbestraverse（Graph*g）

{

 inti;

 Queue*q=（Queue*）malloc（sizeof（Queue））;

 for（i=1;i<=g->vexnum;i++）

 {

  visited[i]=0;

 }

 initqueue（q）;

 for（i=1;i<=g->vexnum;i++）

 {

   if（!

visited[i]）

    {

      visited[i]=1;

      visitvex（g,g->V[i]）;

      enqueue（q,g->V[i]）;

      while（!

quempty（q））

       {

         intu,w;

         u=dequeue（q）;

         for（w=firstadjvex（g,u）;w>0;w=nextadjvex（g,u,w））

           {

             if（!

visited[w]）

              {

                visited[w]=1;

  visitvex（g,w）;

                enqueue（q,w）;

              }

           }

       }

    }

 }

}

/*主程序*/

main（）

{

 intn;

 Graph*g=（Graph*）malloc（sizeof（Graph））;

 charmenu;

 printf（"Pleaseinputthenumberofvertex:

\n"）;

 scanf（"%d",&n）;

 creatgraph（g,n）;

 printf（"Thisisthelinjiejuzhenofgraph:

\n"）;

 printgraph（g）;

 input:

 printf（"Choose:

\nb:

Breadth_first\nd:

Depth_first\nq:

quit\n"）;

 while（（menu=getchar（））=='\n'）;

 if（menu=='b'）

   {

     printf（"Breadth_first:

\n"）;

     bestraverse（g）;

     printf（"\n"）;

     gotoinput;

   }

 elseif（menu=='d'）

   {

     printf（"Depth_first:

\n"）;

     dfstraverse（g）;

     printf（"\n"）;

     gotoinput;

   }

 elseif（menu=='q'）

   {

    exit（0）;

   }

 else

   {

     printf（"Inputerror!

\nChoose:

\nb:

Breadth_first\nd:

Depth_first\nq:

quit\n"）;

   }}

intprim（intg[][max],intn）//最小生成树PRIM算法

{intlowcost[max],prevex[max];//LOWCOST[]存储当前集合U分别到剩余结点的最短路径

//prevex[]存储最短路径在U中的结点

inti,j,k,min;

for（i=2;i<=n;i++）//n个顶点，n-1条边

{lowcost[i]=g[1][i];//初始化

prevex[i]=1;//顶点未加入到最小生成树中

}

lowcost[1]=0;//标志顶点1加入U集合

for（i=2;i<=n;i++）//形成n-1条边的生成树

{min=inf;

k=0;

for（j=2;j<=n;j++）//寻找满足边的一个顶点在U,另一个顶点在V的最小边

if（（lowcost[j]

=0））

{min=lowcost[j];

k=j;

}

printf（"（%d,%d）%d\t",prevex[k]-1,k-1,min）;

lowcost[k]=0;//顶点k加入U

for（j=2;j<=n;j++）//修改由顶点k到其他顶点边的权值

if（g[k][j]

{lowcost[j]=g[k][j];

prevex[j]=k;

}

printf（"\n"）;

}

return0;

}

#include

#include"conio.h"

#defineWERTEX_MAX20//最大顶点数

typedefcharVextype;

typedefstruct//邻接矩阵存储表示

{

}voidprim（MGraphGn,Vextypev0）//最小生成树PRIM算法,从v0出发构造最小生成树

{closedgedge;

inti,j,k;

k=LocatVex（Gn,v0）;//查找v0的顶点序号

prinntf（"%c->U",V0）;//v0并入u集合

for（j=0;j

if（j!

=k）

{dge[j].adjvex=v0;

dge[j].lowcost=Gn.adj[k][j];

}

dge[k].lowcost=0;//初始u={v0}

for（i=0;i

{for（j=0;j