图的深度优先遍历

深度优先遍历(Depth First Search)的主要思想是：

1、首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；

2、当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。

在此我想用一句话来形容 “不到南墙不回头”。

//图的深度优先遍历
#include<stdio.h>
#include<stdlib.h>
#define maxv 5//最大顶点个数
#define inf 32767 //考虑若是带权图的其它情况是∞
typedef struct
{
    int no;//顶点的编号
    int num;//顶点的值
}VertexType;//顶点类型

typedef struct
{
    int edges[maxv][maxv];//邻接矩阵数组；
    int n,e;//顶点数。边数
    VertexType verxs[maxv];//顶点信息
}MatGraph;//邻接矩阵类型

typedef struct Anode
{
    int sdjvex;//邻接点的编号
    struct Anode *nextarc;//指向下一条边的指针
}ArcNode;//边结点类型

typedef struct Vnode
{
    int no;//顶点的编号
    int num;//顶点的值
    ArcNode *fistarc;//指向第一个边结点
}VNode;//邻接表的头结点类型；

typedef struct
{
    int  n,e;//定点数，边数
    VNode adjlist[maxv];//头结点数组
}AdjGraph;//邻接表类型

void CreateAdj(AdjGraph *&G,int A[maxv][maxv],int n,int e)//创建图的邻接表
{
    int i,j;//用于循环的临时变量
    ArcNode *p;//边结点类型指针
    G=(AdjGraph *)malloc(sizeof(AdjGraph));//这里默认我在主函数里面仅仅定义了一个结构体指针，
    //                                      没有为结构体分配空间，在这里为它分配空间
    for(i=0;i<n;i++)//n是顶点数，这里是给所有头结点指针域置初值
    {
        G->adjlist[i].fistarc=NULL;
    }
    for(i=0;i<n;i++)//这里不要把邻接矩阵的定义搞错了，n个顶点最多是n*n的矩阵。
    {
        for(j=n-1;j>=0;j--)//这里递减循环，因为采用了头插法
        {
            if(A[i][j]!=0 && A[i][j]!=inf)
            {
                p=(ArcNode*)malloc(sizeof(ArcNode));
                p->sdjvex=j;//i到j有连线，则邻接点为j，即点的编号是j
                p->nextarc=G->adjlist[i].fistarc;//头插法插入结点p；
                G->adjlist[i].fistarc=p;
            }
        }
    }
    G->e=e;
    G->n=n;
}

int visited[maxv]={0};
void DFSTree(AdjGraph *G,int v)
{
ArcNode *p;
visited[v]=1;//置已访问标记
printf("%d",v);

p=G->adjlist[v].fistarc;
while(p!=NULL)//这个顶点有邻接顶点
{
    if(visited[p->sdjvex]==0)//这个邻接顶点未被访问
    {
       // printf("(");
        DFSTree(G,p->sdjvex);//递归访问当前这个顶点的邻接顶点
       // printf(")");
    }
    
    p=p->nextarc;
}
}
void DispAdj(AdjGraph *G)//输出邻接表G
{ 
    int i;
    ArcNode *p;
    for(i=0;i<G->n;i++)
    {
        p=G->adjlist[i].fistarc;//p是一个边结点类型的指针，把一个头结点数组元素指向的边结点指针赋给它
        printf("%3d:",i);//输出这是第几个顶点，这个顺序是由你输入的邻接矩阵决定的，算法只是按序扫描
        while(p!=NULL)
        {
            printf("%3d-→",p->sdjvex);
            p=p->nextarc;
        }
        printf("Λ\n");
    }
}


int main()
{
    int A[5][5]={{0,1,0,1,1},{1,0,1,1,0},{0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}};
    AdjGraph *G;
    CreateAdj(G,A,5,8);
    DispAdj(G);
    DFSTree(G,2);
}