#include <iostream>
#include <cstdio>
#include "graph.h"
using namespace std;


int main()
{
    freopen("data.in" , "r" , stdin);

//    cout << "\n ** 生成邻接矩阵图,并进行DFS遍历输出: "<< endl;
//    MGraph mg  ;
//    createMGraph(mg);
//    DFSTraverse(mg) ;

    cout << "\n ** 生成邻接表图,并进行DFS遍历输出: "<< endl;
    ALGraph alg ;
    createAdjList(alg);

    DFSTraverse(alg) ;

    cout << "\n ** BFS遍历输出: "<< endl;
    BFSTraverse(alg);

    cout << "\n ** From NO.1 To No.4: " <<endl;
    if( !GetOnePath(alg, 1, 4))
        cout << " NO Path " << endl;

    cout << endl;
    return 0 ;
}

#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED

#define N 20


typedef enum{UDG = 0,DG = 1} GraphKind ; // 图类型：UDG无向图,DG有向图
typedef  char T ;
/***************************邻接矩阵 ****************************/

typedef struct{
    T   vexs[N];      // 顶点向量
    int arcs[N][N];   // 邻接矩阵
    int vexnum, arcnum; //顶点数,边数
    GraphKind kind ;    // 图类型
}MGraph ;


/**********************邻接表****************************/
/** 弧结点类型 */
typedef struct ArcNode
{
	int      adjvex;
	ArcNode  *nextArc;
}ArcNode ;

/** 头结点VNode,头结点向量AdjList类型*/
typedef struct VNode
{
	T         data ;
	ArcNode * firstarc ;
}AdjList[N] ;

//VNode,
/** 邻接图类型*/
typedef struct {
	AdjList vertices;  //头结点向量
	int vexnum, arcnum;
	GraphKind kind;    // UDG无向图 ； DG有向图
}ALGraph;

/**************************基本操作 *******************************/
void createAdjList( ALGraph &g);
void createMGraph( MGraph &g);

void DFS( ALGraph g , int v );
void DFS( MGraph g , int v );

void DFSTraverse( MGraph g );
void DFSTraverse( ALGraph g );

bool GetOnePath( ALGraph g , int v ,int d );

/**输出邻接表图中第v个顶点*/
inline void PrintNode(ALGraph g, int v);


void BFSTraverse(ALGraph g);


#endif // GRAPH_H_INCLUDED

/**
  createGraph.cpp
  读入数据，分别建立图的两种存储"邻接矩阵"和"邻接表"
  操作简单但繁琐，能用它们建立图相应存储结构，非重点
*/

#include "iostream"
#include "graph.h"
using namespace std ;

/* 建立图的 邻接表结构g */
void createAdjList( ALGraph &g)
{
    int i ;

    cin >>(int&)g.kind;
    cin >> g.vexnum ; // 输入顶点数
    cin >> g.arcnum ; // 输入弧数

    /* 输入结点数据，建立头结点向量*/
    for ( i = 1 ; i <= g.vexnum ; i++ )
    {
        cin >> g.vertices[i].data ;
        g.vertices[i].firstarc = NULL ;
    }

    /*输入弧(头,尾)，建立邻接表*/
    for ( i= 0 ; i < g.arcnum ; i++ )
    {
        int head , tail ;
        cin >> head >> tail ;

        //生成边结点
        ArcNode * p = new ArcNode ;
        p->adjvex = tail ;

        //头插
        p->nextArc = g.vertices[head].firstarc ;
        g.vertices[head].firstarc = p ;

        if ( g.kind == UDG )  //无向图,还需在尾结点的边链表中插入结点
        {
            ArcNode * p = new ArcNode ;
            p->adjvex = head ;
            p->nextArc = g.vertices[tail].firstarc ;
            g.vertices[tail].firstarc = p ;
        }
    }
}

/* 建立图的 邻接矩阵结构g */
void createMGraph( MGraph &g)
{
    int i , j;

    cin >> (int&)g.kind;
    cin >> g.vexnum; // 输入顶点数
    cin >> g.arcnum; // 输入弧数

    /* 输入结点数据，建立顶点向量*/
    for ( i = 1 ; i <= g.vexnum ; i++ )
    {
        cin >> g.vexs[i];
    }

    /*输入弧(头,尾)，建立邻接表*/
    for (i = 1 ; i <= g.vexnum ; i++)
        for (j = 1 ; j <= g.vexnum ; j++)
           g.arcs[i][j] = 0 ;

    for ( i= 1 ; i <= g.arcnum ; i++ )
    {
        int head , tail ;
        cin >> head >> tail ;
        g.arcs[head][tail] = 1 ;

        if ( g.kind == UDG ) // 无向图为对称阵
        {
             g.arcs[tail][head] = 1 ;
        }
    }
}

/**
 traverse.cpp
 邻接矩阵图和邻接表图的 深度优先搜索（遍历）
 邻接表图广度优先搜索（遍历）
 邻接表图的指定起点和终点的路径搜索
 （有路则向前探索,无路则回溯.即为迷宫问题）*/

#include "iostream"
#include "graph.h"
#include <queue>

using namespace std ;

bool VISITED[N]; //访问标志向量

/**访问标志数组全部初始化为“未访问” */
inline void InitVisited( )
{
    for(int i=0; i<N; i++)
        VISITED[i] = false;
}

/**从某顶点出发,深度优先搜索“邻接矩阵”存储的图
 *@g 邻接矩阵
 *@v 出发顶点编号 */
void DFS( MGraph g , int v )
{
    VISITED[v] = true ;
    cout << g.vexs[v] << "  " ;

    for ( int w = 1 ; w <= g.vexnum ; w++ )
    {
        if ( g.arcs[v][w] && !VISITED[w] )
            DFS( g , w ) ;
    }
}


/** 深度优先搜索遍历,"邻接矩阵”图
 * @g 邻接矩阵 */
void DFSTraverse( MGraph g )
{
    int v ;

    InitVisited();//标志数组初始化为false

    for ( v = 1 ; v <= g.vexnum ; v++)
        if ( !VISITED[v] ) DFS(g,v) ;
}


/************* 以下为邻接表图的操作**************

/**输出邻接表图中第v个顶点*/
inline void PrintNode(ALGraph g, int v)
{
    cout << g.vertices[v].data << " " ;
}


/**从某顶点出发,深度搜索”邻接表“存储的图
 * @g 邻接表
 * @v 出发顶点编号*/
void DFS( ALGraph g , int v )
{
    ArcNode * p ;

    VISITED[v] = true ;
    PrintNode(g,v) ;  //输出第v个顶点
    for ( p = g.vertices[v].firstarc ; p ; p = p->nextArc )
    {
        int w  = p->adjvex ;
        if ( !VISITED[w] )
            DFS( g , w ) ;
    }
}


/** 深度优先搜索遍历,"邻接表”表示的图
 * @g 邻接表*/
void DFSTraverse( ALGraph g )
{
    int v ;

    InitVisited();//标志数组初始化为false

    for ( v = 1 ; v <= g.vexnum ; v++)
        if ( !VISITED[v] )
            DFS(g,v);
}


/**BFS 广度优先遍历图 (需使用队列,这里使用STL的queue）
 *@g 邻接表图
 */
void BFSTraverse(ALGraph g)
{
    int v,w;
    queue<int> q;

    InitVisited();//标志数组初始化为false

    for(v=1; v<=g.vexnum; v++)
    {
        if( !VISITED[v])
        {
            VISITED[v] = true;
            PrintNode(g,v) ;  //输出第v个顶点
            q.push(v);
            while(q.size()!=0)
            {
                w = q.front();
                q.pop();
                for(ArcNode *p=g.vertices[w].firstarc; p; p=p->nextArc)
                {
                    w = p->adjvex;
                    if(!VISITED[w])
                    {
                        VISITED[w] = true;
                        PrintNode(g,w) ;  //输出第w个顶点
                        q.push(w);
                    }
                }//for
            }//while
        }
    }
}


int PATH[100] ;// 存储路径
/** 基于DFS,输出从v号到d号顶点的一条路径 (即为迷宫问题)
 * @g 邻接表存储的图
 * @v 起点编号
 * @d 终点编号
 * @len 从len开始存储,即起点距当前顶点的距离
 * @return 存在v到s路径true，否则false */
bool GetOnePath( ALGraph g, int s, int d, int len )
{
    ArcNode * p ;

    //到达终点,则输出路径并返回
    if ( d == s )
    {
        PATH[len] = s ;
        for (int i = 1 ; i <= len ; i++)
            PrintNode(g,PATH[i]) ;
        return true;
    }
    //访问（记入路径）并标记
    VISITED[s] = true ;
    PATH[len] = s ;

    for ( p = g.vertices[s].firstarc ; p ; p = p->nextArc )
    {
        // 从v的各个尚未访问的邻接点w出发 搜索d
        int nextNode  = p->adjvex ;
        if ( !VISITED[nextNode] )
            if( GetOnePath(g, nextNode, d, len+1) )
                return true ;
    }
    return false; //从起点s的各邻接点出发（各方向）均无路可达，则无路
}

/** 寻路径的包装函数*/
bool GetOnePath( ALGraph g, int s, int d )
{
     InitVisited();
     return GetOnePath(g,s,d,1);
}

0 8 9
A B C D E F G H
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 8
6 7



1 4  4
A B C D
1 2
1 3
3 4
4 1