创建边链表，进行深度优先搜索和广度优先搜索

#include<stdio.h>#include<stdlib.h>#define MAXSIZE 100//深度遍历标记数组 intDfsVist[MAXSIZE]; 
//广度遍历标记数组 intBfsVist[MAXSIZE];
//  边链表 typedefstructEdgeLink{
intLocal;                  //  存放该顶点对应边链表中数据                        structEdgeLink*next;      //  边链表节点指针  }Edge,*ELINK;
//  顶点表 typedefstructVertexLink{
intVertex;                 //  存放一条边链表对应的顶点 ELINKFirstNode;            //  指向该顶点对应边链表的头节点 }Vertex[MAXSIZE],*VLINK;
//  存放顶点和边，指向顶点表结构体数组 typedefstructMyGraph{
intVnum;   //  存放顶点数 intEnum;   //  存放边数 VertexList;    //  边链表对应的顶点表中顶点结构体 }MyGraph;
//  创建边链表voidCreateLink(MyGraph*T)
{
inti,j;
intv1,v2;
ELINKp;        //  边链表指针 ELINKq;
printf("请输入顶点数和边数(空格隔开):\n");
scanf("%d%d",&(T->Vnum),&(T->Enum));
//  初始化顶点表结构体数组 for(i=0;i<T->Vnum;i++)
    {
printf("请输入第%d个顶点的信息:\n",i+1);
scanf("%d",&(T->List[i].Vertex));       //  存放顶点在顶点表中 T->List[i].FirstNode=NULL;        //  让每个顶点表第一个指向边链表的指针为NULL     }
//  打印顶点坐标和顶点表中顶点数据 printf("---------------------------\n"); 
for(i=0;i<T->Vnum;i++)
    {
printf("顶点下标为:%d   顶点数据为: %d\n",i,T->List[i].Vertex);   
    }
printf("---------------------------\n");
//  插入边链表数据 for(i=0;i<T->Enum;i++)
    {
//  因为顶点表为顺序表，所以要按顶点顺序输入相连边 printf("请输入两个连接顶点下标(空格隔开):\n");
scanf("%d%d",&v1,&v2);
getchar(); 
q= (ELINK)malloc(sizeof(Edge));    //  创建边链表节点，分配内存 q->Local=v2;  //  记录与该顶点连接边的顶点坐标q->next=NULL;                     //  让尾巴指向NULL if(!T->List[v1].FirstNode){ //  判断是否为这个顶点第一个指向的数据 T->List[v1].FirstNode=q;
        }else{
//  这个顶点已经指向了一条边，以这条边为头节点，尾插法 p=T->List[v1].FirstNode;  //  临时存放头节点 while(p->next)  //  让节点指针遍历到尾巴上             {
p=p->next;
            }
p->next=q;    //  让新插的节点连接到之前边节点的尾巴上         }
q= (ELINK)malloc(sizeof(Edge));    //  创建边链表节点，分配内存 q->Local=v1;  //  记录与该顶点连接边的顶点坐标q->next=NULL;                     //  让尾巴指向NULL if(!T->List[v2].FirstNode){ //  判断是否为这个顶点第一个指向的数据 T->List[v2].FirstNode=q;
        }else{
//  这个顶点已经指向了一条边，以这条边为头节点，尾插法 p=T->List[v2].FirstNode;  //  临时存放头节点 while(p->next)  //  让节点指针遍历到尾巴上             {
p=p->next;
            }
p->next=q;    //  让新插的节点连接到之前边节点的尾巴上         }
    } 
}
//  打印邻接表 voidPrintLink(MyGraph*S) 
{
MyGraph*T=S;
ELINKQ;            //  防止边链表指针指到NULL ，用临时指针代替遍历打印 inti;
printf("打印邻接表结果如下:\n");
for(i=0;i<T->Vnum;i++)
    {
Q=T->List[i].FirstNode;   //  接受每个顶点指向对应边链表的头节点指针 printf("%d--->",i);
while(1)
        {
if(Q==NULL)
            {
putchar('\n');
break;
            }
printf("------->%3d",Q->Local);
Q=Q->next;    //！！BUG         }
    }
putchar('\n');
}
//***************** 深度优先遍历算法—邻接表 *****************//voidDFS_Link(MyGraph*T,intn)
{   
inti,j;
ELINKq;    //  指向边链表节点指针 if(n<0||n>=T->Vnum)
    {
printf("输入有误\n");
return; 
    }
DfsVist[n] =1;     //  遍历一个顶点，做下标记 1  printf(" %d",T->List[n].Vertex);
q=T->List[n].FirstNode;   //q指向下标为i所对顶点 对应的边链表的第一个边结点 while(q!=NULL)  
        {   
if(DfsVist[q->Local]!=1)
            {
j=q->Local;
DFS_Link(T,j);
            } 
q=q->next;
        }
} 
//  初始化深度遍历—邻接表 voidInit_DFSLINK(MyGraph*Q)
{
inti;
for(i=0;i<Q->Vnum;i++)
    {
DfsVist[i] =0;
    }
for(i=0;i<Q->Vnum;i++)
    {
if(!DfsVist[i])
        {
DFS_Link(Q,i); //  此顶点没有被标记，开始递归遍历        }
    }
putchar('\n'); 
}
//  广度遍历 voidBFS(MyGraph*S,intt)
{
ELINKP;            //  指向顶点所对应的边链表中 inti;
intv;      //  用来接收边链表对应的顶点//  为了不和广度搜素—邻接矩阵冲突//  创建一个数组队列 intQueue[MAXSIZE];
intfront=0;          //  队头 intrear=0;           //  队尾 printf("%d ",S->List[t].Vertex);    //  输出当前遍历边链表的顶点 BfsVist[t] =1;     //  将该顶点作标记rear= (rear+1)%MAXSIZE;    //  入队一个让队尾指向后移一位Queue[rear] =t;            //  将该顶点入队 while(front!=rear)    //  若front == rear，表明这个顶点在边链表上连接的顶点已经遍历完毕     {
front= (front+1)%MAXSIZE;      //  出队 v=Queue[front];           //  得到此时遍历到顶点坐标 P=S->List[v].FirstNode;   //  遍历当前顶点指向边链表中连接的其他顶点//  也就是换个顶点的边链表继续遍历查找剩余顶点 while(P!=NULL)
        {
if(BfsVist[P->Local] ==0)
            {           
printf("%d ",P->Local+1);   //  输出连接边顶点 BfsVist[P->Local] =1;      //  作标记,表示这个顶点已经搜索过 rear= (rear+1)%MAXSIZE;        //  将该下标入队 Queue[rear] =P->Local; //  把遍历到新的边链表对应的顶点坐标入队             }
P=P->next;    //  遍历这个顶点的边链表         }   
    } 
} 
//  BFS广度遍历初始化voidInit_BFS(MyGraph*S)
{
inti;
for(i=0;i<S->Vnum;i++)
    {
BfsVist[i] =0; //  初始化标记符     }
for(i=0;i<S->Vnum;i++)
    {
if(BfsVist[i]==0)
BFS(S,i);
    }
} 
intmain()
{
MyGraph*S;
S= (MyGraph*)malloc(sizeof(MyGraph));
//  创建边链表 CreateLink(S);
//  打印边链表 PrintLink(S);
//  深度遍历printf("深度遍历搜索为：\n");
Init_DFSLINK(S); 
//  广度遍历 printf("广度遍历搜索为：\n");
Init_BFS(S);
return0;   
}