/*
   DFS：访问邻接顶点，再访问邻接顶点方式
*/

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char VertexType[4];
#define MAX 10

typedef   struct   ArcNode
{
     int   vexIndex;     //顶点在顶点数组中的序号
     struct   ArcNode* next;    
}Node,*LPNODE;

//链表操作
LPNODE   createNode(int    vexIndex)
{
     LPNODE  newNode = (LPNODE)malloc(sizeof(NODE));
     newNode->vexIndex = vexIndex;
     newNode->next = NULL;
     return    newNode;
}

//无表头链表的表头法插入
//LPNODE *headNode这里用的是二级指针，因为无表头的插入会修改表头的指向
void   insertNodeByHead(LPNODE *headNode,int  vexIndex)
{
       LPNODE  newNode = createNode(vexIndex);
       newNode->next = *headNode;
       *headNode = newNode;
}

//图结构：数组，链表
//顶点信息描述出来
typedef  struct   VNode
{
      VertexType   data;       //数据
      LPNODE  firstNode;    //每个数据都带有一个指针
}VNODE,ARRAY[MAX],*LPVNODE;

//图
typedef  struct   GRAPH
{
     int   arcNum;          //边数
     int   vexnum;          //顶点数
     ARRAY   vextex;    //结构体数组
}GRAPH,*LPGRAPH;

//创建图
int  searchPos(LPGRAPH  G,VertexType   X)
{
     for(int  i=0;i<G->vexnum;i++)
     {
             if(strcmp(G->vextex[i].data,x)==0)
             {
                    return  i;
             }
     }
     return  -1;
}

//创建图
LPGRAPH   createGraph()
{
     LPGRAPH    G = (LPGRAPH)malloc(sizeof(GRAPH));
     printf("输入边数和顶点数：",&G->arcnum,&G->vexnum);
     printf("请输入 %d 个顶点：\n"G->vexnum);
     for(int i=0;i < G->vexnum; i++)
     {
            scanf("%s",G->vextex[i].data);
            G->vextex[i].firstNode = NULL;    //指针需要初始化         
     }
     VertexType   v1,v2;
     int   posV1;
     int   posV2;
     printf("请输入边的信息：\n");
     for(int  i=0;i<G->arcnum;i++)
     {
           scanf("%s%s",v1,v2);
           posV1 = searchPos(G,v1);
           posV2 = searchPos(G,v2);
           //把v2插到以v1为顶点的链表中去
           insertNodeByHead(&G->vextex[posV1].firstNode,posV2);
           //把v1插到以v2为顶点的链表中去
           insertNodeByHead(&G->vextex[posV2].firstNode,posV1);
     }
     return  G;
}

//访问
void    visitVextex(VertexType   x)
{
      printf("%s-->",x);
]

void   BFSTravers(LGPRAPH   G, int   inPos)
{
       int   visited[MAX] = {0};   //访问标记
       //对列三要素
       int  queue[MAX];     //顶点的序号
       int  front; = -1;         //队头的元素
       int  rear = -1;           //队尾的元素
       //1.选定入口
       visitVextex(G->vextex[inPos].data);
       viseted[inPos] = 1;         //把访问标记置为 1 
        
       queue[++rear] = inPos;   //把走过的元素入队
       LPNODE  pMove = NULL;
       while(front < rear)
       {
                //出队
                inPos = queue[++front];
                pMove = G->vextex[inPos].firstNode;
                while(pMove)
                {
                        //没有被访问，就访问一次
                        if(visited[pMove->vexIndex] == 0)
                        {
                               vistVextex(G->vextex[pMove->vexIndex].data);
                               visited[pMove->vexIndex] = 1;
                               //把访问的元素入队
                               queue[++rear] = pMove->vexIndex;
                        }
                        pMove = pMove->next;   //被打印就不再做打印处理
                ]
       }
}

void   DFSTraverse(LPGRAPH  G,int   inPos)
{
    //栈要素
    LPNODE  stack[MAX];
    int  top = -1;
     
    //访问标记
    int    visited[MAX] = { 0 }；
     
    //选定入口
    visitVextex(G->vextex[inPos].data);
    visited[inPos] = 1;
    //打印入口的链表，打印一个节点，跳转
    LPNODE  pMove = G->vextex[inPos].firstNode;
    while(top > -1 || pMove != NULL)
    {
         while(pMove)
         {
               if(visited[pMove->vexIndex] == 1)
               {
                      //被访问直接跳过
                      pMove = pMove->next; 
               } 
               else   //访问标记置为1，入栈
               {
                        visitVextex(G->vextex[pMove->vexIndex].data);
                        visited[pMove->vexIndex] = 1;
                        stack[++top] = pMove;
                        //跳到当前访问过的序号的哪个链表中去
                        pMove = G->vextex[pMove->vexIndex].firstNode;
               }
         } 
         //访问到空的时候，要去出栈
         if(top > -1)
         {
                pMove = stack[top--];
                pMove = pMove->next;
         }
    }
}

int main()
{
		LPGAPH G = createGraph();
		printf("广度优先");
		BFSTravers(G,0);
		printf("\n");
         printf("深度优先：\n");
         DFSTraverse(G,0);
	    system("pause");
	    return  0;

}