图的操作.txt

关于图的一些基本操作

if (g[v][j]!=0) //存在边(v,j)

         if (visited[j]!=1) {if (!visited[j]) dfs(j); }//if

         else {cycle=1; Print(j,j);}

    visited[v]=2;

}//dfs

void find_cycle() //判断是否有回路，有则输出邻接矩阵。visited数组为全局变量。

     {for (i=1;i<=n;i++) visited[i]=0;

      for (i=1;i<=n;i++ ) if (!visited[i])  dfs(i);

}//find_cycle

14．[题目分析]有几种方法判断有向图是否存在环路，这里使用拓扑排序法。对有向图的顶点进行拓扑排序，若拓扑排序成功，则无环路；否则，存在环路。题目已假定有向图用十字链表存储，为方便运算，在顶点结点中，再增加一个入度域indegree，存放顶点的入度。入度为零的顶点先输出。为节省空间，入度域还起栈的作用。值得注意的是，在邻接表中，顶点的邻接点非常清楚，顶点的单链表中的邻接点域都是顶点的邻接点。由于十字链表边（弧）结点个数与边（弧）个数相同（不象无向图边结点个数是边的二倍），因此，对某顶点v, 要判断其邻接点是headvex还是tailvex。

    int Topsor(OrthList  g)

//判断以十字链表为存储结构的有向图g是否存在环路，如是，返回1，否则，返回0。

{int top=0; //用作栈顶指针

 for (i=1;i<=n;i++)    //求各顶点的入度。设有向图g有n个顶点，初始时入度域均为0

  {p=g[i].firstin;     //设顶点信息就是顶点编号，否则，要进行顶点定位

   while(p)  

     {g[i].indegree++; //入度域增1

if (p->headvex==i) p=p->headlink; else p=p->taillink; //找顶点i的邻接点

}//while(p)  }//for

for (i=1;i<=n;i++)      //建立入度为0的顶点的栈

  if (g[i].indegree==0) {g[i].indegree=top; top=i; }

m=0;  //m为计数器，记输出顶点个数

while (top<>0) 

  {i=top; top=g[top].indegree; m++;      //top指向下一入度为0的顶点

   p=g[i].firstout; 

   while (p) //处理顶点i的各邻接点的入度

 {if (p->tailvex==i) k=p->headvex; else k=p->tailvex;}//找顶点i的邻接点

      g[k].indegree--; //邻接点入度减1

      if (g[k].indegree==0) {g[k].indegree=top; top=k; }  //入度为0的顶点再入栈

if (p->headvex==i) p=p->headlink; else p=p->taillink;//找顶点i的下一邻接点

     }//while (p) 

 }// while (top<>0)

if (m<n) retun(1);  //有向图存在环路

  else return(0);   //有向图无环路

}//算法结束

15. int FirstAdj(AdjMuList g , vertype v)

   //在邻接多重表g中，求v的第一邻接点，若存在，返回第一邻接点，否则，返回0。

    {i=GraphLocateVertex(g,v); //确定顶点v在邻接多重表向量中的下标，不考虑不存在v的情况。

     p=g[i].firstedge;   //取第一个边结点。

     if (p==null ) return (0);

else {if (ivex==i) return (jvex); else return (ivex);}

//返回第一邻接点，ivex和jvex中必有一个等于i

     }// FirstAdj

16. [题目分析]本题应使用深度优先遍历，从主调函数进入dfs(v)时 ，开始记数，若退出dfs()前，已访问完有向图的全部顶点（设为n个），则有向图有根，v为根结点。将n个顶点从1到n编号，各调用一次dfs()过程，就可以求出全部的根结点。题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组等均设计为全局变量。建立有向图g的邻接表存储结构参见上面第2题，这里只给出判断有向图是否有根的算法。

  int  num=0， visited[]=0  //num记访问顶点个数,访问数组visited初始化。

  const  n=用户定义的顶点数;

  AdjList g ;             //用邻接表作存储结构的有向图g。

  void  dfs(v)

     {visited [v]=1;  num++; //访问的顶点数＋1

      if (num==n) {printf(“%d是有向图的根。\n”,v); num=0;}//if

      p=g[v].firstarc;

      while (p)

        {if (visied[p->adjvex]==0) dfs (p->adjvex);

p=p->next;} //while

      visited[v]=0; num--; //恢复顶点v

}//dfs

void  JudgeRoot()

//判断有向图是否有根，有根则输出之。

 {static int i ;

for (i=1;i<=n;i++ ) //从每个顶点出发，调用dfs()各一次。

 {num=0; visited[1..n]=0; dfs(i); }

 　}// JudgeRoot

算法中打印根时，输出顶点在邻接表中的序号（下标），若要输出顶点信息，可使用g[i].vertex。

17. [题目分析] 使用图的遍历可以求出图的连通分量。进入dfs或bfs一次，就可以访问到图的一个连通分量的所有顶点。

void  dfs ()

{visited[v]=1; printf ( “%3d”,v); //输出连通分量的顶点。

p=g[v].firstarc;

while (p!=null)

  {if（visited[p->adjvex==0]） dfs(p->adjvex);

   p=p->next;

}//while

}// dfs

  void  Count()

    //求图中连通分量的个数

     {int k=0 ; static AdjList g ; //设无向图g有n个结点

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

         if (visited[i]==0) { printf ("\n第%d个连通分量:\n",++k); dfs(i);}//if

      }//Count

算法中visited[]数组是全程变量，每个连通分量的顶点集按遍历顺序输出。这里设顶点信息就是顶点编号，否则应取其g[i].vertex分量输出。

18. void bfs(AdjList GL，vertype v )

    //从v发广度优先遍历以邻接表为存储结构的无向图GL。

     {visited[v]=1; 

      printf( "%3d",v);            //输出第一个遍历的顶点。

      QueueInit(Q); QueueIn(Q ,v); //先置空队列，然后第一个顶点v入队列，设队列容量足够大

      while (!QueueEmpty(Q))

        {v=QueueOut(Q); p=GL[v].firstarc; //GL是全局变量， v入队列。

         while (p!=null)

           {if(visited[p->adjvex]==0)

              {printf("%3d",p->adjvex); visited[p->adjvex]=1; QueueIn(Q,p->adjvex);}//if

p=p->next; 

}//while

         }// while (!QueueEmpty(Q))

      }//bfs

    void  BFSCOM()

       //广度优先搜索，求无向图Ｇ的连通分量。

       { int count=0; //记连通分量个数。

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

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

           if (visited[i]==0) {printf("\n第%d个连通分量:\n",++count); bfs(i);}//if

        }//BFSCOM

19.请参见上题18。HEAD，MARK，VER，LINK相当于上题GL，visited，adjvex，next。

20. void  Traver(AdjList g,vertype v)

      //图g以邻接表为存储结构，算法从顶点v开始实现非递归深度优先遍历。

{struct arc *stack[];

   visited[v]=1；printf(v);  //输出顶点v

   top=0; p=g[v].firstarc; stack[++top]=p;

   while(top>0 || p!=null)

     {while (p) 

        if (p && visited[p->adjvex]) p=p->next;

        else {printf(p->adjvex); visited[p->adjvex]=1; 

stack[++top]=p; p=g[p->adjvex].firstarc;

 }//else

          if (top>0) {p=stack[top--]; p=p->next; }

         }//while  }//算法结束。

[算法讨论] 以上算法适合连通图，若是非连通图，则再增加一个主调算法,其核心语句是

for (vi=1;vi<=n;vi++) if (!visited[vi]) Traver(g,vi);

21. （１）限于篇幅，邻接表略。

（２）在邻接点按升序排列的前提下，其dfs和bfs序列分别为BADCEF和BACEDF。

（３）void dfs(v)

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

     visited[i]=1; printf(v);   //输出顶点信息

     p=g[i].firstarc;

     while (p)

       { if (visited[p->adjvex]==0) dfs(g[p->adjvex].vertex);

         p=p->next;

}//while

    }//dfs

void traver( )

    //深度优先搜索的递归程序；以邻接表表示的图g是全局变量。

   { for (i=1;i<=n;i++)  visited[i]=0; //访问数组是全局变量初始化。

     for (vi=v1;vi<=vn;vi++)

         if (visited[GraphLocateVertex(g，vi)]==0) dfs(vi);

   }//算法结束。

22. [题目分析]强连通图指从任一顶点出发，均可访问到其它所有顶点，故这里只给出dfs()过程。

　　PROC dfs(g:AdjList , v0:vtxptr)

     //从v0出发，深度优先遍历以邻接表为存储结构的强连通图g。

     TYPE stack=ARRAY[1..n] OF arcptr; //栈元素为弧结点指针，n为顶点个数。

     s:stack; top:integer; top:=0

     visited[v0]:=1;

     write(v0:4); //设顶点信息就是顶点编号；否则要顶点定位。

     p:=g[v0]^.firstarc;

WHILE (top>0 || p!=NIL) DO

  BEGIN WHILE (p!= NIL) DO

              IF (visited[p^.adjvex]=1) THEN p:=p^.next; //查未访问的邻接点。

              ELSE  BEGIN w:=p^.adjvex; visited[w]:=1; top:=top+1; s[top]:=p;

                          p:=g[w].firstarc ;

 END； //深度优先遍历。

IF (top>0) THEN BEGIN p:=s[top]; top:=top-1; p:=p^.next END;

END；

ENDP；

23. [题目分析] 本题是对无向图Ｇ的深度优先遍历，dfs算法上面已有几处（见20-22）。这里仅给出将连通分量的顶点用括号括起来的算法。为了得出题中的输出结果，各顶点的邻接点要按升序排列。

　void Traver( )

    {for (i=1;i<=nodes(g);i++)  visited[i]=0; //visited是全局变量，初始化。

     for (i=1;i<=nodes(g);i++)　

       if (visied[i]==0) {printf ("(");  dfs(i);  printf (")");}//if

}//Traver

24.void  visit(vertype v)        //访问图的顶点v。

   void  initqueue (vertype Q[])   //图的顶点队列Ｑ初始化。

   void  enqueue (vertype Q[] ,v)   //顶点v入队列Ｑ。

   vertype delqueue (vertype Q[])   //出队操作。

   int   empty (Q)                  //判断队列是否为空的函数，若空返回１，否则返回０。

   vertype firstadj(graph g ,vertype v)//图g中v的第一个邻接点。

vertype nextadj(graph g ,vertype v ,vertype w)//图g中顶点v的邻接点中在w后的邻接点

void  bfs (graph g ,vertype v0)

      //利用上面定义的图的抽象数据类型，从顶点v0出发广度优先遍历图g。

      {visit(v0);

      visited[v0]=1; //设顶点信息就是编号，visited是全局变量。

      initqueue(Q);  enqueue(Q,v0); //v0入队列。

      while (!empty(Q))

        {v=delqueue(Q); //队头元素出队列。

         w=firstadj(g ,v); //求顶点v的第一邻接点

         while (w!=0) //w!=0表示w存在。

           {if (visited[w]==0) //若邻接点未访问。

              {visit(w); visited[w]=1; enqueue(Q,w);}//if

            w=nextadj(g,v,w); //求下一个邻接点。

            }//while }//while

       }//bfs

 void  Traver() 

        //对图g进行宽度优先遍历，图g是全局变量。

      {for (i=1;i<=n;i++)  visited[i]=0;

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

         if (visited[i]==0) bfs(i);

       }   //Traver

25.[题目分析] 本题应使用深度优先遍历。设图的顶点信息就是顶点编号，用num记录访问顶点个数，当num等于图的顶点个数（题中的NODES(G)），输出所访问的顶点序列，顶点序列存在path中，path和visited数组，顶点计数器num，均是全局变量，都已初始化。

  void SPathdfs(v0)

     //判断无向图Ｇ中是否存在以v0为起点，包含图中全部顶点的简单路径。

     {visited[v0]=1;  path[++num]=v0;

      if (num==nodes(G) //有一条简单路径，输出之。

          {for (i=1;i<=num;i++) printf( "%3d",path[i]); printf( "\n"); exit(0);} //if

      p=g[v0].firstarc;

      while (p)

        {if (visited[p->adjvex]==0) SPathdfs(p->adjvex); //深度优先遍历。