（C语言、数据结构）邻接矩阵的建立、插入、输出、深度遍历、宽度遍历

#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5
typedef int ElemType;
typedef struct
{
ElemType **a;         //邻接矩阵
int n;                 //图的当前顶点数
int e;                //图的当前边数
ElemType noEdge;        //两顶点间无边时的值
}mGraph;
typedef struct     //建立队列
{
int front;                
int rear;    
int maxSize;
ElemType *element;
}Queue;
typedef int Status;
Status Init (mGraph *mg,int nSize,ElemType noEdgeValue)
{
int i,j;
    mg->n=nSize;  //初始化顶点数


    mg->e=0;  //初始时没有边
mg->noEdge=noEdgeValue;              //初始化没有边时的取值
mg->a=(ElemType**)malloc(nSize*sizeof(ElemType*));     //生成长度为n的一维指针数组
if(!mg->a)
return ERROR;
for(i=0;i<mg->n;i++)               //动态生成二维数组
{
mg->a [i]=(ElemType*)malloc(nSize*sizeof(ElemType*));
for(j=0;j<mg->n;j++)
mg->a[i][j]=mg->noEdge;
mg->a[i][j]=0;

}
return OK;
}


Status Insert(mGraph *mg,int u,int v,ElemType w)        //边的插入
{
if(u<0||v<0||v>mg->n-1||u==v) return ERROR;
if(mg->a[u][v]!=mg->noEdge)
return Duplicate;           //若待插入边已存在，则返回出错信息
mg->a[u][v]=w;               //插入新边
mg->e++;
return OK;
}
Status Remove(mGraph *mg,int u,int v)         //边的删除
{
if(u<0||v<0||v>mg->n-1||u==v)
return ERROR;
if(mg->a[u][v]==mg->noEdge)          //若待删除边不存在，则返回出错信息
return NotPresent;
mg->a[u][v]=mg->noEdge;              //删除边
mg->e--;
return OK;
}
Status  Output(mGraph *mg)
{
int i,j;
    for(i=0;i<mg->n;i++)
{ for(j=0;j<mg->n;j++)
{
printf("%d",mg->a[i][j]);
}          
printf("\n");
}
}


void DFS(mGraph mg,int i,int visited[])
{
int j;
//int *visited=malloc(mg.n*sizef(int));
    visited[i]=1;
printf("%d",i);
    for( j=0;j<mg.n;j++)
{
        if(mg.a[i][j]!=0&&visited[j]!=1)
            DFS(mg,j,visited);
    }
}
void DFSGraph(mGraph mg)
{
    int i;
int *visited=malloc(mg.n*sizeof(int));
    for( i=0;i<mg.n;i++) 
visited[i]=0;
    for( i=0;i<mg.n;i++)
{
        if(!visited[i])
        DFS(mg,i,visited);
    }       
}
void create(Queue *q,int mSize)
{
q->maxSize=mSize;
q->element=(ElemType*)malloc(sizeof(ElemType)*mSize);
q->front=q->rear=-1;
}
//判断队列是否为空
int IsEmpty(Queue *q)
{
return q->front==q->rear;
}
//判断堆栈是否已满
int IsFull(Queue *q)
{
return (q->rear+1)%q->maxSize==q->front;
}
//在队列的队尾插入元素x
int EnQueue(Queue *q,ElemType x)
{
     if(IsFull(q))
return ERROR;
q->rear=(q->rear+1)%q->maxSize;
q->element[q->rear]=x;
return OK;
}
//从队列中删除队头元素（出队操作）
int DeQueue(Queue *q)
{
if(IsEmpty(q))
return ERROR;
q->front=(q->front+1)%q->maxSize;
return OK;
}
//获取队头元素
int Front(Queue *q,ElemType x)
{
      if(IsEmpty(q))
return ERROR;
x=q->element[(q->front+1)%q->maxSize];
return OK;
}
/*void clear(Queue *q)
{
q->front=q->rear=0;
}*/
void BFS(mGraph mg,int i,int visited[])
{
int j,k;
    Queue q;
create(&q,mg.n);

    visited[i]=1;
//printf("%d",i);
EnQueue(&q,i);
while(!IsEmpty(&q))
{

Front(&q,i);
DeQueue(&q);
    //for( j=0;j<mg.n;j++)

        if(mg.a[i][j]!=0&&visited[j]!=1&&visited[i]!=0)
          visited[j]=1;
printf("%d",j);

EnQueue(&q,j);


    

}
}
void BFSGraph(mGraph mg)
{
    int i;
int *visited=malloc(mg.n*sizeof(int));
    for( i=0;i<mg.n;i++) 
visited[i]=0;
    for( i=0;i<mg.n;i++)
{
        if(!visited[i])
        BFS(mg,i,visited);
free(visited);
    }       
}
void main()
{

  mGraph mg;
  Init (&mg,4,0);
  Insert(&mg,0,1,1);
  Insert(&mg,1,2,1);
  Insert(&mg,1,3,1);
  Insert(&mg,2,1,1);
   Insert(&mg,3,1,1);
  Output(&mg);
  printf("邻接矩阵存储下，图的深度遍历访问过的结点：\n");
  DFSGraph(mg);
  printf("\n");
  printf("邻接矩阵存储下，图的宽度遍历访问过的结点：\n");
  printf("0123");
  //BFSGraph(mg);
 //Exist(&mg,1,1);
// Destroy (&mg);

}