#include<stdio.h>
#include<malloc.h>
#define VEXTYPE int
#define ADJTYPE int
#define MAXLEN 40
#define MAX 10000
#define MAX_VERtEX_NUM 20
#define VRType int
#define InfoType char
#define VertexType int
typedef enum{DG=1,DN,UDG,UDN}GraphKind;
bool visited[MAX_VERtEX_NUM];
typedef struct {
VRType adj;
InfoType *info;
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];
typedef struct{
int vexs[20];
int arcs[20][20];
int vexnum,arcnum;
GraphKind kind;
}MGraph;
//int visited[20];
typedef struct{
int front;
int rear;
int *base;
}SqQueue;
int InitQueue(SqQueue *Q){
Q->base=(int *)malloc(20*sizeof(int));
Q->front=Q->rear=0;
return(1);
}
int QueueEmpty(SqQueue Q){
return !((Q.rear-Q.front+20)%20);
}
int EnQueue(SqQueue *Q,int e){
if((Q->rear+1)%20==Q->front) return (0);
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%20;
return (1);
}
int DeQueue(SqQueue *Q,int *e){
if(Q->front==Q->rear) return 0;
*e=Q->base[Q->front];
Q->front=(Q->front+1)%20;
return 1;
}
void CreateUDG(MGraph *G){
int i,j,k;
int v1,v2;
printf("\n\t\tinput vexnum and arcnum(输入节点个数与边的条数)：");
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
for(i=0;i<G->vexnum;i++){
printf("\n\t\tinput %d vexs：",i+1);
scanf("%d",&(G->vexs[i]));
}
for(i=0;i<G->vexnum;i++){
for(j=0;j<G->vexnum;j++)
G->arcs[i][j]=0;
}
for(k=0;k<G->arcnum;k++){
printf("\t\t input %d side and vexs(输入哪两个结点间有边)以,分隔：",k+1);
scanf("%d,%d",&v1,&v2);
for(i=0;v1!=G->vexs[i];i++);
for(j=0;v2!=G->vexs[j];j++);
G->arcs[i][j]=1;G->arcs[j][i]=G->arcs[i][j];
}
}
void CreateUDN(MGraph *G){
int i,j,k,w;
int v1,v2;
printf("\n\t\tinput vexnum and arcnum： ");
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
for(i=0;i<G->vexnum;i++){
for(j=0;j<G->vexnum;j++)
G->arcs[i][j]=1000;
}
for(k=0;k<G->arcnum;k++){
printf("\t\t input %d side and vexs and weight： 以,分隔：",k+1);
scanf("%d,%d",&v1,&v2);
for(i=0;v1!=G->vexs[i];i++);
for(j=0;v2!=G->vexs[j];j++);
G->arcs[i][j]=w;
G->arcs[j][i]=G->arcs[i][j];
}
}
void CreateDG(MGraph *G){//gai
int i,j,k;
int v1,v2;
printf("\n\t\tinput vexnum and arcnum： ,");
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
for(i=0;i<G->vexnum;i++){
printf("\n\t\tinput %d vexs： ",i+1);
scanf("%d",&(G->vexs[i]));
}
for(i=0;i<G->vexnum;i++){
for(j=0;j<G->vexnum;j++)
G->arcs[i][j]=0;
}
for(k=0;k<G->arcnum;k++){
printf("\t\t input %d side and vexs： 以,分隔：",k+1);
scanf("%d,%d",&v1,&v2);
for(i=0;v1!=G->vexs[i];i++);
for(j=0;v2!=G->vexs[j];j++);
G->arcs[i][j]=1;
}
}
void CreateDN(MGraph *G){
int i,j,k,w;
int v1,v2;
printf("\n\t\tinput vexnum and arcnum： ");
scanf("%d,%d",&(G->vexnum),&(G->arcnum));
for(i=0;i<G->vexnum;i++){
printf("\n\t\tinput %d vexs： ",i+1);
scanf("%d",&(G->vexs[i]));
}
for(i=0;i<G->vexnum;i++){
for(j=0;j<G->vexnum;j++)
G->arcs[i][j]=1000;
}
for(k=0;k<G->arcnum;k++){
printf("\t\t input %d side and vexs and weight： 以,分隔：",k+1);
scanf("%d,%d,%d",&v1,&v2,&w);
for(i=0;v1!=G->vexs[i];i++);
for(j=0;v2!=G->vexs[j];j++);
G->arcs[i][j]=w;
}
}
void print(MGraph *G){
int i,j;
printf("\n\n MGraph is： \n");
for(i=0;i<G->vexnum;i++){
printf("\n");
for(j=0;j<G->vexnum;j++)
printf("\t%d",G->arcs[i][j]);
}
}
int FirstAdjVex(MGraph G,int v){
for(int i=0;i<G.vexnum;i++){
if(G.arcs[v][i].adj) return i;
}
return -1;
}
int NextAdjVex(MGraph G,int v,int w){
for(int i=w+1;i<G.vexnum;i++){
if(G.arcs[v][i].adj) return i;
}
return -1;
}
void visitVex(MGraph G, int v){
printf("%d ",G.vexs[v]);
}
void DFS(MGraph G,int v){
visited[v] = true;
visitVex(G,v);
for(int w = FirstAdjVex(G,v); w>=0; w = NextAdjVex(G,v,w)){
if(!visited[w]) DFS(G,w);
}
}
void DFSTraverse(MGraph G){
int v;
for( v = 0; v < G.vexnum; ++v) visited[v]=false;
for( v = 0; v < G.vexnum; v++){
if(!visited[v]) DFS( G, v);
}
}
