在算法实现方面要求，熟练掌握图的两种遍历方法，并能够根据图的基本原理解决一些应用问题，如：判定图的连通性、判定是否有环、计算特定路径等。

1，一个连通图采用邻接表作为存储结构，设计一个算法实现从顶点v出发的深度优先遍历的非递归过程。

void DFS1(AGraph *G,int v)
    {   int visited[MAXV],i,j;
        int St[MAXV],top=-1;
        ArcNode *p;
        for (i=0;i<G->n;i++)                 //访问标志数置初值
            visited[i]=0;
        top++;
        St[top]=v;                           //初始顶点进栈
        visited[v]=1;                        //修改访问标志
        while (top>-1)                       //栈不空时循环
        {   j=St[top];top--;                 //出栈
            printf("%d ",j);                 //访问节点j
            p=G->adjlist[j].firstarc;        //找第一个邻接点
            while (p!=NULL)
            {   if (visited[p->adjvex]==0)   //将未访问过的邻接点进栈
                {   top++;
                    St[top]=p->adjvex;
                    visited[p->adjvex]=1;    //修改访问标志
                }
                p=p->nextarc;                //找下一个邻接点
            }
        }
    }

2，设计一个算法，求无向图G（采用邻接表存储）的连通分量个数。

int visited[MAXV]={0};
    int Getnum(AGraph *G)                       //求图G的连通分量
    {   int i,n=0,visited[MAXVEX];
        for (i=0;i<G->n;i++)
            if (visited[i]==0)
            {   DFS(G,i);                       //对图G从顶点i开始进行深度优先遍历
                n++;                            //调用DFS的次数即为连通分量数
            }
        return n;
    }

int visited[MAXV]={0};
    int Getnum1(AGraph *G)             //求图G的连通分量
    {   int i,n=0,visited[MAXVEX];
        for (i=0;i<G->n;i++)
            if (visited[i]==0)
            {   BFS(G,i);              //对图G从顶点i开始进行广度优先遍历
                n++;                   //调用BFS的次数即为连通分量数
            }
        return n;
    }

2.1，假设一个无向图是非连通的，采用邻接表作为存储结构，试设计一个算法，输出图中各连通分量的节点序列。

int visited[MAXV]={0};
    DFSGraph(AGraph *G)
    {   int i,j=1;                               //用j记录连通分量的序号
        for (i=0;i<G->n;i++)
            if (visited[i]==0)
            {   printf("第%d个连通分量节点序列:",j++);
                DFS(G,i);                        //调用前面的深度优先遍历算法
            }
    }

int visited[MAXV]={0};
    BFSGraph(AGraph *G)
    {   int i,j=1;                               //用j记录连通分量的序号
        for (i=0;i<G->n;i++)
            if (visited[i]==0)
            {   printf("第%d个连通分量节点序列:",j++);
                BFS(G,i);                        //调用前面的广度优先遍历算法
            }
    }

3，假设无向图G采用邻接表存储，设计一个算法，判断图G是否为连通图。若为连通图返回1；否则返回0。

void DFS2(AGraph *G,int v,int &vn,int &en)
{   ArcNode *p;
        visited[v]=1;vn++;           //遍历过的顶点数增1
        p=G->adjlist[v].firstarc;
        while (p!=NULL)
        {   en++;                    //遍历过的边数增1
            if (visited[p->adjvex]==0)
                DFS2(G,p->adjvex,vn,en);
            p=p->nextarc;
        }
    }
    int GIsTree(AGraph *G)          //判断无向图G是否是一棵树
    {   int vn=0,en=0,i;
        for (i=0;i<G->n;i++)
        visited[i]=0;
        DFS2(G,1,vn,en);
        if (vn==G->n && en==2*(G->n-1))
            return 1;               //遍历顶点为G->n个,边数为2(g->n-1),则为树
        else
            return 0;
    }

3.1，设计一个算法，判断一个无向图G是否是一棵树。若是树，返回1；否则返回0。

void DFS2(AGraph *G,int v,int &vn,int &en)
{   ArcNode *p;
        visited[v]=1;vn++;           //遍历过的顶点数增1
        p=G->adjlist[v].firstarc;
        while (p!=NULL)
        {   en++;                    //遍历过的边数增1
            if (visited[p->adjvex]==0)
                DFS2(G,p->adjvex,vn,en);
            p=p->nextarc;
        }
    }
    int GIsTree(AGraph *G)          //判断无向图G是否是一棵树
    {   int vn=0,en=0,i;
        for (i=0;i<G->n;i++)
        visited[i]=0;
        DFS2(G,1,vn,en);
        if (vn==G->n && en==2*(G->n-1))
            return 1;               //遍历顶点为G->n个,边数为2(g->n-1),则为树
        else
            return 0;
    }

4,假设一个连通图采用邻接表作为存储结构，试设计一个算法，判断其中是否存在回路。

void Cycle(AGraph *G,int v,bool &has)
    {   //调用时has置初值false
        ArcNode *p;
        int w;
        visited[v]=1;                    //置已访问标记
        p=G->adjlist[v].firstarc;        //p指向顶点v的第一个邻接点
        while (p!=NULL)
        {   w= p->adjvex;
            if (visited[i]==0)           //若顶点w未访问,递归访问它
                Cycle(G,w,has);
            else                         //又找到了已访问过的顶点说明有回路
                has=true;
            p=p->nextarc;                //找下一个邻接点
        }
    }

5，假设图G采用邻接表存储，设计一个算法判断图G中顶点u到顶点v之间是否有简单路径。

void ExistPath(AGraph *G,int u,int v,int &has)
    {   //has表示u到v是否有路径,初值为0
        int w;
        ArcNode *p;
        visited[u]=1;                    //置已访问标记
        if (u==v)                        //找到了一条路径
        {   has=1;
            return;
        }
        p=G->adjlist[u].firstarc;        //p指向顶点u的第一个相邻点
        while (p!=NULL)
        {   w=p->adjvex;            //w为顶点u的相邻顶点
            if (visited[w]==0)           //若w顶点未访问,递归访问它
                ExistPath(G,w,v,has);
            p=p->nextarc;                //p指向顶点v的下一个相邻点
        }
    }

6，假设图G采用邻接表存储，设计一个算法，输出图G中从顶点u到v的所有简单路径。

 void FindPath(AGraph *G,int u,int v,int path[ ],int d)
    //d是到当前为止已走过的路径长度,调用时初值为-1
 {   int w,i;
        ArcNode *p;
        d++;                                    //路径长度增1
      path[d]=u;                                //将当前顶点添加到路径中</p>
        visited[u]=1;                           //置已访问标记
        if (u==v)                               //找到一条路径则输出
        {   for (i=0;i<=d;i++)
                printf("%2d",path[i]);
            printf("\n");
        }
        p=G->adjlist[u].firstarc;               //p指向v的第一个相邻点
        while (p!=NULL)
        {   w=p->adjvex;                        //w为顶点u的相邻顶点
            if (visited[w]==0)                  //若w顶点未访问,递归访问它
                FindPath(G,w,v,path,d);
            p=p->nextarc;                       //p指向v的下一个相邻点
        }
        visited[u]=0;                           //恢复环境,使该顶点可重新使用
    }

7，假设不带权图G采用邻接表存储，设计一个算法，采用BFS方式输出图G中从顶点u到v的最短路径。

typedef struct
    {   int data;                             //顶点编号
        int parent;                           //前一个顶点的位置
    } QUERE;                                  //非循环队列类型
    void ShortPath(AGraph *G,int u,int v)
    {   //输出从顶点u到顶点v的最短逆路径
        ArcNode *p;
        int w,i;
        QUERE qu[MAXV];                       //非环形队列
        int front=-1,rear=-1;                 //队列的头、尾指针
        int visited[MAXV];
        for (i=0;i<G->n;i++)                  //访问标记置初值0
            visited[i]=0;
        rear++;                               //顶点u进队
        qu[rear].data=u;
        qu[rear].parent=-1;
        visited[u]=1;
        while (front!=rear)                   //队不空循环
        {   front++;                          //出队顶点w
            w=qu[front].data;
            if (w==v)                         //找到v时输出路径之逆并退出
            {   i=front;                      //通过队列输出逆路径
                while (qu[i].parent!=-1)
                 {   printf("%d<-",qu[i].data);
                    i=qu[i].parent;
                }
                printf("%2d\n",qu[i].data);
                break;
            }
            p=G->adjlist[w].firstarc;         //找w的第一个邻接点
            while (p!=NULL)
            {   if (visited[p->adjvex]==0)
                {   visited[p->adjvex]=1;
                    rear++;                   //将w的未访问过的邻接点进队
                    qu[rear].data=p->adjvex;
                    qu[rear].parent=front;
                }
                p=p->nextarc;                 //找w的下一个邻接点
            }
        }
    }