#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20

int visited[MAX_VERTEX_NUM];

typedef char Vertex_Type[5];

typedef enum
{
    DG, DN, UDG, UDN
}Graph_Kind;

typedef struct Arc_Node
{
    int adj_vertex;//邻接定点所在定点向量表中的位置
    int weight;//权值
    struct Arc_Node *next_arc;//指向下一个邻接点
}Arc_Node;

typedef struct Vertex_Node
{
    Vertex_Type data;//表示顶点的类型
    struct Arc_Node *first_arc;//指向第一个邻接顶点
}Vertex_Node;

typedef struct
{
    Vertex_Node vertexs_vectors[MAX_VERTEX_NUM];//顶点向量
    int vertex_num;//顶点数
    int arc_num;//边数
    Graph_Kind kind;//图的类型
}ALGraph;

void Init_ALGraph( ALGraph &G )
{
    printf("输入图的边数:");
    scanf("%d", &G.arc_num);
    printf("输入图的顶点数:");
    scanf("%d", &G.vertex_num);
    printf("输入图的类型(0:DG 1:DN 2:UDG 3:UDN): ");
    scanf("%d", &G.kind);

    printf("初始化顶点向量(例如:v1 v2 v3):");
    for( int i=0; i<G.vertex_num; ++i )
    {
        scanf("%s", G.vertexs_vectors[i].data);
        G.vertexs_vectors[i].first_arc = NULL;//初始值指向空
    }
}

int Get_Vertex_Location( ALGraph G, Vertex_Type V )
{
    for( int i=0; i<G.vertex_num; ++i )
        if( strcmp( G.vertexs_vectors[i].data, V )==0 )
            return i;
    exit(0);//表示操作错误就结束
}
void Create_ALGraph( ALGraph &G )
{
    Init_ALGraph( G );

    Vertex_Type v1, v2;
    int i, v1_site, v2_site;

    printf("输入与弧相关联的顶点和相关信息(v1 -- v2或v1 -> v2)\n");
    for( i=0; i<G.arc_num; ++i )
    {
        scanf("%s %*s %s", v1, v2);
        v1_site = Get_Vertex_Location( G, v1 );
        v2_site = Get_Vertex_Location( G, v2 );

        Arc_Node *p1, *p2;
        p1 = (Arc_Node*) malloc (sizeof(Arc_Node));
        p1->next_arc = G.vertexs_vectors[v1_site].first_arc;
        G.vertexs_vectors[v1_site].first_arc = p1;
        p1->adj_vertex = v2_site;
        p1->weight = 0;//设置不带权的权值全为零

        switch( G.kind )
        {
        case DG://有向图
            break;
        case DN://有向网
            printf("输入权值:");
            scanf("%d", &p1->weight);
            break;
        case UDN://无向网
            printf("输入权值:");
            scanf("%d", &p1->weight);
        case UDG://无向图
            p2 = (Arc_Node*) malloc (sizeof(Arc_Node));
            p2->next_arc = G.vertexs_vectors[v2_site].first_arc;
            G.vertexs_vectors[v2_site].first_arc = p2;
            p2->adj_vertex = v1_site;
            p2->weight = p1->weight;
            break;
        default://表示出错
            exit(0);
        }
    }
}

void Print_ALGraph( ALGraph G )
{
    Arc_Node *p;
    for( int i=0; i<G.vertex_num; ++i )
    {
        p = G.vertexs_vectors[i].first_arc;

        while( p )
        {
            switch( G.kind )
            {
            case DG:
                printf("< %s ->", G.vertexs_vectors[i].data);
                printf(" %s >\n", G.vertexs_vectors[p->adj_vertex].data);
                break;
            case DN:
                printf("< %s ->", G.vertexs_vectors[i].data);
                printf(" %s , %d >\n", G.vertexs_vectors[p->adj_vertex].data, p->weight);
                break;
            case UDG:
                printf("( %s --", G.vertexs_vectors[i].data);
                printf(" %s )\n", G.vertexs_vectors[p->adj_vertex].data);
                break;
            case UDN:
                printf("( %s --", G.vertexs_vectors[i].data);
                printf(" %s , %d )\n", G.vertexs_vectors[p->adj_vertex].data, p->weight);
                break;
            default:
                exit(0);
            }
            p = p->next_arc;
        }
    }
}

int First_Adj_Vertex( ALGraph G, int v )
{
    Arc_Node *p = G.vertexs_vectors[v].first_arc;

    if( !p )
        return -1;
    else
        return Get_Vertex_Location( G, G.vertexs_vectors[p->adj_vertex].data);
}

int Next_Adj_Vertex( ALGraph G, int v, int w )
{
    Arc_Node *p = G.vertexs_vectors[v].first_arc;

    while( p )
    {
        if( p->adj_vertex == w )
            break;
        p = p->next_arc;
    }
    if( !p )
        exit(0);//因为正常情况下w是一定可以找到的
    p = p->next_arc;
    if( p )
        return p->adj_vertex;
    else
        return -1;
}

void DFS( ALGraph G, int v )
{
    visited[v] = 1; printf("%s ", G.vertexs_vectors[v].data);
    for( int w=First_Adj_Vertex( G, v); w>=0; w=Next_Adj_Vertex( G, v, w ) )
        if( !visited[w] )
            DFS( G, w );
}

void DFS_Traverse( ALGraph G )
{
    for( int v=0; v<G.vertex_num; ++v )
        visited[v] = 0;// 表示没有被访问过
    printf("DFS图的遍历序列:");
    for( v=0; v<G.vertex_num; ++v )
        if( !visited[v] )
            DFS( G, v );
    printf("\n");
}

int main()
{
    ALGraph G;

    Create_ALGraph( G );

    Print_ALGraph( G );

    DFS_Traverse( G );

    return 0;
}