#include <iostream.h>
#include<malloc.h>
#define Vnum 20
typedef struct arcnode   //边结构
{
    int adjvex; //下一条边的始点编号
    struct arcnode *nextarc;//下一条边的指针
}arcnode;
typedef struct vexnode  //顶点数组
{
    int vertex;
    arcnode *firstarc;//指向每一条边的指针
}adjlist[Vnum];
typedef struct graphs
{
    adjlist adjlist;
    int vexnum,arcnum;//顶点个数和边条数
}graph;
void create(graph *g) //用户输入一个图
{
    int n,e,i,j,k;
    arcnode *p;
    cout<<"创建一个图:\t";
    cout<<"顶点数:";
    cin>>n;
    cout<<"\t\t边数:";
    cin>>e;
    g->vexnum=n;g->arcnum=e;
    for(i=0;i<n;i++)
    {
         g->adjlist[i].vertex=i;
        g->adjlist[i].firstarc=NULL;
    }
for(k=0;k<e;k++)
{
    cout<<"第"<<k+1<<"条边(节点号从0到)"<<n-1<<"):";
    cin>>i>>j;
    p=new arcnode;
    p->adjvex=j;
    p->nextarc=g->adjlist[i].firstarc;
    g->adjlist[i].firstarc=p;
}
}
void disp(graph *g)
{
    int i,have;
    arcnode *p;
    cout<<"输出图:"<<endl;
    for(i=0;i<g->vexnum;i++)
    {
        p=g->adjlist[i].firstarc;
        have=0;
        while(p!=NULL)
        {
            cout<<"("<<i<<", "<<p->adjvex<<")";
            p=p->nextarc;
            have=1;
        }
        if(have==1)
            cout<<endl;
    }
}
void dfs(graph g,int v,int visited[])
{
    arcnode *p;
    cout<<v<<" ";
    visited[v]=1;
    p=g.adjlist[v].firstarc;
    while(p!=NULL)
    {
        if(!visited[p->adjvex])
            dfs(g,p->adjvex,visited);
        p=p->nextarc;
    }
}
//void bfs(graph g,int v)//从顶点V开始广度优先搜索图g
void main()
{
    graph g;
    int visited[Vnum],i,v;
    for(i=0;i<Vnum;i++)
        visited[i]=0;
    create(&g);// 建立一个有向图
    disp(&g);
    cout<<"输入顶点";
    cin>>v;
    cout<<"深度优先序列";
    dfs(g,v,visited);cout<<endl;
//    cout<<"广度优先序列";
//  bfs(g,v);cout<<endl;
}