#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
#include<cstdlib>
using namespace std;

#define MaxInt 32767
#define MVNum 100
bool visited[MaxInt];
typedef int VerTexType;
typedef int ArcType,OtherInfo;
typedef struct ArcNode{//边 
    int adjvex;//顶点序号 
    struct ArcNode *nextarc;//下一条边的指针 
    OtherInfo info;// 
}ArcNode;

typedef struct VNode{//顶点 
    VerTexType data;
    ArcNode *firstarc; 
}VNode,AdjList[MVNum];

typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;


int LocateVex(ALGraph G,int u){//图G存在，u和G中顶点有相同特征。若G中存在顶点u,则返回该顶点在图中的位置；否则返回其他信息。 
    for(int i=0;i<G.vexnum;i++){
        if(G.vertices[i].data==u){
            return i;
        }
    }
    return -1;
} 

void CreateGraph(ALGraph &G){//V是图的顶点集，VR是图中弧的集合。按V和R的定义构造图G。 
    cout<<"请输入顶点数，边数:"<<"\n";
    cin>>G.vexnum>>G.arcnum;
    cout<<"\n请输入每个顶点的值："<<"\n"; 
    for(int i=0;i<G.vexnum;i++){
        cin>>G.vertices[i].data;
        G.vertices[i].firstarc=NULL;
    }
    cout<<"输入边:"<<"\n"; 
    for(int k=0;k<G.arcnum;k++){
        int v1,v2;
        cin>>v1>>v2;
        int i=LocateVex(G,v1);
        int j=LocateVex(G,v2);
        ArcNode *p1,*p2;
        p1=new ArcNode;
        p1->adjvex=j;
        p1->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p1;
        p2=new ArcNode;
        p2->adjvex=i;
        p2->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p2;
    }
    return;
}

void DestroyGraph(ALGraph &G){//图G存在。销毁图G。 
    ArcNode *p, *q;
    G.vexnum = 0;
    G.arcnum = 0;
    for( int i = 0; i < G.vexnum; i++ ){
        p = G.vertices[i].firstarc;
        while( p!=NULL ){
            q = p->nextarc;
            free( p );
            p = q;
        }
    }
    return;
} 

int GetVex(ALGraph G,int v){//图G存在，v是G中某个顶点。返回v的值。 
    for(int i=0;i<G.vexnum;i++){
        if(i==v){
            return G.vertices[i].data;
        }
    }
    return 0;
} 

void PutVex( ALGraph &G, VerTexType v, VerTexType value){//图G存在，v是G中某个顶点。对v赋值value。 
    for(int i=0;i<G.vexnum;i++){
        if(i==v){
            G.vertices[i].data=value;
        }
    }
    return;
} 

int FirstAdjVex( ALGraph G, VerTexType v ){//图G存在，v是G中某个顶点。返回v的第一个邻接顶点，若v在G中没有邻接顶点，则返回“空”。 
    ArcNode *p;
    int v1;
    v1 = LocateVex( G,v );
    p = G.vertices[v1].firstarc;
    if( p!=NULL )
        return p->adjvex;
    else
        return -1;
}

int NextAdjVex(ALGraph G, VerTexType v, VerTexType w){//图G存在，v是G中某个顶点,w是v的邻接顶点。 返回v的（相对于w的)下一个邻接顶点。若w是v的最后一个邻接顶点，则返回“空”。 
    ArcNode *p;
    int v1, w1;
    v1 = LocateVex( G, v );     //v1为顶点v在图G中的序号
    w1 = LocateVex( G, w );     //w1为顶点w在图G中的序号
    p = G.vertices[v1].firstarc;
    while( p!=NULL && p->adjvex != w1 )  //指针p不空且所指针表结点不是w
        p = p->nextarc;
    if( p==NULL || p->nextarc==NULL )      //没找到w或w是最后一个邻接顶点
        return -1;
    else
        return p->nextarc->adjvex;
} 

void InsertVex(ALGraph &G, VerTexType v ){//图G存在，u和G中顶点有相同特征。在图G中增添新顶点v. 
    G.vertices[G.vexnum].data = v;   //构造新顶点向量
    G.vertices[G.vexnum].firstarc = NULL;
    G.vexnum++;                              //图G的顶点数加1
    return;
} 

void DeleteVex( ALGraph &G, VerTexType v ){//图G存在，v是G中某个顶点。删除G中顶点v及其相关的弧。 
    int i, j;
    ArcNode *p, *q;
    j = LocateVex( G, v );         //j是定点v的序号
    if( j < 0 ){ //v不是图G的顶点
        return;
    }                   
    p = G.vertices[j].firstarc;    //删除以v为出度的弧或边
    while( p ){
        q = p;
        p = p->nextarc;
        free( q    );
        G.arcnum--;               //弧或边数减1
    }
    G.arcnum--;                   //顶点数减1
    for( i = j; i < G.vexnum; i++ ){//顶点v后面的顶点前移
        G.vertices[i] = G.vertices[i+1];
    }
        
    for( i = 0; i < G.vexnum; i++ ){//删除以v为入度的弧或边且必要是修改表结点的顶点位置
        p = G.vertices[i].firstarc;    //指向第1条弧或边
        while( p!=NULL ){//有弧
            if( p->adjvex == j ){
                if( p == G.vertices[i].firstarc ){//待删结点是第1个结点
                    G.vertices[i].firstarc = p->nextarc;
                    free( p );
                    p = G.vertices[i].firstarc;
                }else{
                    q->nextarc = p->nextarc;
                    free( p );
                    p = p->nextarc;
                }
            }else{
                if( p->adjvex > j ){
                    p->adjvex--; //修改表结点的顶点位置值
                } 
                q = p;
                p = p->nextarc;
            }
        }
    }
    return;
}

void InsertArc( ALGraph &G, VerTexType v, VerTexType w){//图G存在，v和w是G中两个顶点。在G中增添<v,w>，若G是无向图，则还增添对称弧<w,v>。 
    ArcNode *p;
    int w1, i, j;
    i = LocateVex( G, v);    //弧尾或边的序号
    j = LocateVex( G, w );   //弧头或边的序号
    if( i < 0 || j < 0 ){
        return;
    }
    G.arcnum++;
    p = new ArcNode;
    p->adjvex = j;
    p->nextarc = G.vertices[i].firstarc;    //插在表头
    G.vertices[i].firstarc = p;             //无向，生产另一个表结点
    return;
} 

void DeleteArc(ALGraph &G, VerTexType v, VerTexType w){//图G存在，v和w是G中两个顶点。在G中删除<v,w>，若G是无向图，则还删除对称弧<w,v>。
    ArcNode *p, *q;
    int i, j;
    i = LocateVex( G, v );          //i是定点(弧尾)的序号
    j = LocateVex( G, w );          //j是定点(弧头)的序号
    if( i < 0 || j < 0 || i == j ){
        return; 
    }
    p = G.vertices[i].firstarc;     //p指向顶点v的第一条弧尾
    while( p && p->adjvex != j ){     //p不空且所指之弧不是待删除<v,w>                  
        q = p;//p指向下一条弧
        p = p->nextarc;
    }
    if( p && p->adjvex == j ){       //找到弧<v,w>
        if( p == G.vertices[i].firstarc ){//p是指第1条弧
            G.vertices[i].firstarc = p->nextarc;  //指向下一条弧
        }else{
            q->nextarc = p->nextarc;  //指向下一条弧
        }
        free( p );                   //弧或边数减1
        G.arcnum--;
    }
    return;
}

void DFSTraverse(ALGraph G,VerTexType v){//图G存在。对图进行深度优先遍历，在遍历过程中对每个顶点访问一次。 
    cout<<v<<" ";
    visited[v]=true;
    ArcNode *p;
    p=new ArcNode;
    int vi=LocateVex(G,v);
    p=G.vertices[vi].firstarc;
    while(p!=NULL){
        int w=G.vertices[p->adjvex].data;
        if(visited[w]==0){
            DFSTraverse(G,w);
        }
        p=p->nextarc;
    }
    return;
}

void BFSTraverse(ALGraph G,VerTexType v){//图G存在。对图进行广度优先遍历，在遍历过程中对每个顶点访问一次。 
    cout<<v<<" ";
    visited[v]=true;
    queue<int>Q;
    Q.push(v);
    while(Q.empty()==0){
        int u=Q.front();
        Q.pop();
        for(int w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,G.vertices[w].data)){
            int x=G.vertices[w].data;
            if(visited[x]==0){
                cout<<x<<" ";
                visited[x]=true;
                Q.push(x);
            }
        }
    }
    return;
} 

int VertexDegree(ALGraph &G, VerTexType v){
    ArcNode *p;
    p=new ArcNode;
    for(int i=0;i<G.vexnum;i++){
        if(v==G.vertices[i].data){
            p=G.vertices[i].firstarc;
            break;
        }
    }
    int num=0;
    while(p!=NULL){
        num++;
        p=p->nextarc;
    }
    return num;
} 

int main(){
    ALGraph G;
    int v;
    
    cout<<"18软件轨道信号一班石启隆\n"; 
    CreateGraph(G);
    cout<<"对图进行广度优先遍历,输入历遍起点："<<"\n";
    cin>>v;
    memset(visited,0,sizeof(visited));
    BFSTraverse(G,v);
    cout<<"\n对图进行深度优先遍历,输入历遍起点："<<"\n";
    cin>>v;
    memset(visited,0,sizeof(visited));
    DFSTraverse(G,v);
    cout<<"\n求一个结点的度，输入一个结点：\n";
    cin>>v;
    cout<<"该结点的度为：\n"<<VertexDegree(G,v)<<"\n"; 
    return 0;
}