图的操作.txt

关于图的一些基本操作

五.算法设计题

1.     void CreatGraph (AdjList g)

//建立有n个顶点和m 条边的无向图的邻接表存储结构

{int n,m;

   scanf("%d%d",&n,&m);

for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量

{scanf(&g[i].vertex);  g[i].firstarc=null;}

for (k=1;k<=m;k++)//输入边信息

{scanf(&v1,&v2);//输入两个顶点

i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位

p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点

p->adjvex=j; p->next=g[i].firstarc; g[i].firstarc=p;//将边结点链入

  p=(ArcNode *)malloc(sizeof(ArcNode));

p->adjvex=i; p->next=g[j].firstarc;  g[j].frstarc=p;

}

}//算法CreatGraph结束

2.     void CreatAdjList(AdjList g)

//建立有向图的邻接表存储结构

{int n;

scanf("%d",&n);

for (i=1;i<=n;j++)

{scanf(&g[i].vertex); g[i].firstarc=null;}//输入顶点信息

scanf(&v1,.&v2);

    while(v1 && v2)//题目要求两顶点之一为0表示结束

     {i=GraphLocateVertex(g2,v1);

      p=(ArcNode*)malloc(sizeof(ArcNode));

      p->adjvex=j;  p->next=g[i].firstarc;  g[i].firstarc=p;

scanf(&v1,&v2);

} }

3.     void CreatMGraph(AdjMulist g)

//建立有n个顶点e条边的无向图的邻接多重表的存储结构

{int n,e;

scanf("%d%d",&n,&e);

     for(i=1,i<=n;i++)    //建立顶点向量

      { scanf(&g[i].vertex);  g[i].firstedge=null;}

     for(k=1;k<=e;k++)    //建立边结点

      {scanf(&v1,&v2);

       i=GraphLocateVertex(g,v1); j=GraphLocateVertex(g,v2);

p=(ENode *)malloc(sizeof(ENode));

p->ivex=i; p->jvex=j; p->ilink=g[i].firstedge; p->jlink=g[j].firstedge;

g[i].firstedge=p; g[j].firstedge=p;

}

}//算法结束

4.     void CreatOrthList(OrthList g)

//建立有向图的十字链表存储结构

{int i,j,v; //假定权值为整型

scanf("%d",&n);

  for(i=1,i<=n;i++)    //建立顶点向量

    { scanf(&g[i].vertex);    g[i].firstin=null; g[i].firstout=null;}

      scanf("%d%d%d",&i,&j,&v);

      while (i && j && v)       //当输入i,j,v之一为0时,结束算法运行

      {p=(OrArcNode *)malloc(sizeof(OrArcNode)); //申请结点

       p->headvex=j;    p->tailvex=i;   p->weight=v;  //弧结点中权值域

       p->headlink=g[j].firstin; g[j].firstin=p;

       p->tailink=g[i].firstout; g[i].firstout=p;

scanf("%d%d%d",&i,&j,&v);

      } }算法结束

[算法讨论]  本题已假定输入的i和j是顶点号,否则,顶点的信息要输入,且用顶点定位函数求出顶点在顶点向量中的下标。图建立时，若已知边数（如上面1和2题），可以用for循环；若不知边数，可用while循环（如本题），规定输入特殊数（如本题的零值）时结束运行。本题中数值设为整型，否则应以和数值类型相容的方式输入。

5．void InvertAdjList(AdjList gin,gout）

//将有向图的出度邻接表改为按入度建立的逆邻接表

    {for (i=1;i<=n;i++)//设有向图有n个顶点，建逆邻接表的顶点向量。

      {gin[i].vertex=gout[i].vertex; gin.firstarc=null; }

     for (i=1;i<=n;i++)   //邻接表转为逆邻接表。

      {p=gout[i].firstarc;//取指向邻接表的指针。

       while (p!=null)

            { j=p->adjvex;

              s=(ArcNode *)malloc(sizeof(ArcNode));//申请结点空间。

              s->adjvex=i; s->next=gin[j].firstarc; gin[j].firstarc=s;

              p=p->next;//下一个邻接点。

            }//while

     }//for   }

6. void  AdjListToAdjMatrix(AdjList gl, AdjMatrix gm)

//将图的邻接表表示转换为邻接矩阵表示。

{for (i=1;i<=n;i++)  //设图有n个顶点，邻接矩阵初始化。

       for (j=1;j<=n;j++) gm[i][j]=0;

     for (i=1;i<=n;i++)

      {p=gl[i].firstarc;  //取第一个邻接点。

       while (p!=null) {gm[i][p->adjvex]=1;p=p->next; }//下一个邻接点

       }//for  }//算法结束

7. void  AdjMatrixToAdjList( AdjMatrix gm, AdjList gl )

//将图的邻接矩阵表示法转换为邻接表表示法。

{for (i=1;i<=n;i++)   //邻接表表头向量初始化。

      {scanf(&gl[i].vertex); gl[i].firstarc=null;}

     for (i=1;i<=n;i++)

       for (j=1;j<=n;j++)

          if (gm[i][j]==1)

             {p=(ArcNode *)malloc(sizeof(ArcNode)) ;//申请结点空间。

p->adjvex=j;//顶点I的邻接点是j

p->next=gl[i].firstarc; gl[i].firstarc=p; //链入顶点i的邻接点链表中

}

 }//end

[算法讨论] 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。

8.[题目分析] 在有向图中，判断顶点Vi和顶点Vj间是否有路径，可采用遍历的方法，从顶点Vi出发，不论是深度优先遍历（dfs）还是宽度优先遍历（bfs），在未退出dfs或bfs前,若访问到Vj，则说明有通路，否则无通路。设一全程变量flag。初始化为0，若有通路，则flag=1。

算法1：int visited[]=0;  //全局变量，访问数组初始化

int  dfs(AdjList g , vi)

    //以邻接表为存储结构的有向图g，判断顶点Vi到Vj是否有通路,返回1或0表示有或无

 { visited[vi]=1;   //visited是访问数组，设顶点的信息就是顶点编号。

    p=g[vi].firstarc;  //第一个邻接点。

    while ( p!=null)

       { j=p->adjvex;

        if (vj==j) { flag=1; return（1）;} //vi 和 vj 有通路。

        if (visited[j]==0) dfs(g,j);

        p=p->next； }//while 

     if (!flag) return(0);

  }//结束

[算法讨论] 若顶点vi和vj 不是编号，必须先用顶点定位函数,查出其在邻接表顶点向量中的下标i和j。下面算法2输出vi 到 vj的路径，其思想是用一个栈存放遍历的顶点，遇到顶点vj时输出路径。

算法2：void dfs(AdjList g , int i)

  //有向图g的顶点vi（编号i）和顶点vj（编号j）间是否有路径，如有，则输出。

   {int top=0,stack[]; //stack是存放顶点编号的栈

    visited[i]=1;      //visited 数组在进入dfs前已初始化。

    stack[++top]=i;

    p=g[i].firstarc; /求第一个邻接点.

    while (p)

      {if (p->adjvex==j)

              {stack[++top]=j; printf( "顶点 vi 和 vj 的路径为：\n");

               for (i=1; i<=top; i++)  printf( "%4d",stack[i]); exit(0);

 }//if

            else if (visited[p->adjvex]==0) {dfs(g,g->adjvex); top--; p=p->next;}//else if

           }//while

    }//结束算法2

算法3：本题用非递归算法求解。

  int  Connectij (AdjList g , vertype vi , vj )

 //判断n个顶点以邻接表表示的有向图g中，顶点 Vi 各Vj 是否有路径，有则返回1，否则返回0。

{ for (i=1;i<=n;i++)  visited[i]=0; //访问标记数组初始化。

  i=GraphLocateVertex(g,vi); //顶点定位，不考虑 vi或 vj不在图中的情况。

  j=GraphLocateVertex(g,vj);

  int stack[],top=0;stack[++top]=i;

  while(top>0)

{k=stack[top--]; p=g[k].firstarc;

while(p!=null && visited[p->adjvex]==1) p=p->next; //查第k个链表中第一个未访问的弧结点。

 if(p==null) top--;

 else {i=p->adjvex;

if(i==j) return(1); //顶点vi和vj 间有路径。

else {visited[i]=1; stack[++top]=i;}//else

}//else

    }while

return(0); } //顶点vi和vj 间无通路。

9. void DeletEdge(AdjList g,int i,j)

     //在用邻接表方式存储的无向图g中，删除边(i,j)

{p=g[i].firstarc;  pre=null; //删顶点i 的边结点(i,j),pre是前驱指针

while (p)

     if (p->adjvex==j)

       {if(pre==null)g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。

     else {pre=p; p=p->next;}   //沿链表继续查找

p=g[j].firstarc;  pre=null; //删顶点j 的边结点(j,i)

while (p)

     if (p->adjvex==i)

       {if(pre==null)g[j].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。

     else {pre=p; p=p->next;}   //沿链表继续查找

   }// DeletEdge

[算法讨论] 算法中假定给的i，j 均存在，否则应检查其合法性。若未给顶点编号，而给出顶点信息，则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。

10. void  DeleteArc（AdjList g,vertype vi,vj）

   //删除以邻接表存储的有向图g的一条弧<vi,vj>，假定顶点vi和vj存在

{i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); //顶点定位

   p=g[i].firstarc;  pre=null;

while (p)

    if (p->adjvex==j)

      {if(pre==null) g[i].firstarc=p->next;else pre->next=p->next;free(p);}//释放结点空间。

    else  { pre=p; p=p->next;}

}//结束

11. void InsertArc ( OrthList g ,vertype vi,vj)

//在以十字链表示的有向图g中插入弧<vi,vj>

{ i=GraphLocateVertex(g,vi); //顶点定位.

  j=GraphLocateVertex(g,vj);

p=(OrArcNode *)malloc(sizeof(OrArcNode));

p=headvex=j; p=tailvex=i;  //填写弧结点信息并插入十字链表。

p->headlink=g[j].firstin; g[j].firstin=p;

p->taillink=g[i].firstout; g[i].firstout=p;

}//算法结束

12. [题目分析]在有向图的邻接表中，求顶点的出度容易，只要简单在该顶点的邻接点链表中查结点个数即可。而求顶点的入度，则要遍历整个邻接表。

 int count (AdjList g , int k )

//在n个顶点以邻接表表示的有向图g中，求指定顶点k(1<=k<=n)的入度。

{ int count =0;

 for (i=1;i<=n;i++)   //求顶点k的入度要遍历整个邻接表。

 if(i!=k)           //顶点k的邻接链表不必计算

{p=g[i].firstarc;//取顶点 i 的邻接表。

 while (p)

    {if (p->adjvex==k) count++;

     p=p->next;

}//while

}//if

  return(count); //顶点k的入度.

}

13. [题目分析]有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。

void  Print(int v,int start )  //输出从顶点start开始的回路。

{for(i=1;i<=n;i++)

    if(g[v][i]!=0 && visited[i]==1 )  //若存在边（v,i），且顶点i的状态为1。

      {printf(“%d”,v); if(i==start) printf(“\n”); else Print(i,start);break;}//if

    }//Print

void dfs(int v)

   {visited[v]=1;

for(j=1;j<=n;j++ )