（数据结构、C语言）邻接表的建立、插入、输出、深度遍历、宽度遍历
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5
typedef int ElemType;
typedef struct eNode
{
int adjVex; //图的当前顶点数
ElemType w;
struct eNode* nextArc;
}eNode;
typedef struct
{
int n;
int e;
eNode **a;
}LGraph;
typedef struct //建立队列
{
int front;
int rear;
int maxSize;
ElemType *element;
}Queue;
typedef int Status;
Status Init(LGraph *lg,int nSize)
{
int i;
lg->n=nSize;
lg->e=0;
lg->a=(eNode**)malloc(nSize*sizeof(eNode*)); //生成长度为n的一维指针数组
if(!lg->a)
return ERROR;
else
{
for(i=0;i<lg->n;i++)
lg->a[i]=NULL;
return OK;
}
}
Status Exist(LGraph *lg,int u,int v) //边的搜索
{
eNode *p;
if(u<0||v<0||u>lg->n-1||u==v||v>lg->n-1)
return ERROR;
p=lg->a[u];//指针p指向顶点u的单链表的第一个边结点
while(p&&p->adjVex!=v) p=p->nextArc;
if(!p)
return ERROR;
else
return OK;
}
Status Insert(LGraph *lg,int u,int v,ElemType w) //边的插入
{
eNode *p;
if(u<0||v<0||v>lg->n-1||u>lg->n-1||u==v) return ERROR;
if(Exist(lg,u,v))
return Duplicate;
p=(eNode *)malloc(sizeof(eNode));
p->adjVex=v;
p->w=w; //插入新边
p->nextArc=lg->a[u];
lg->a[u]=p;
lg->e++;
return OK;
}
Status Remove(LGraph *lg,int u,int v) //边的删除
{
eNode *p,*q;
if(u<0||v<0||v>lg->n-1||u==v||u>lg->n-1)
return ERROR;
p=lg->a[u],q=NULL;
while(p&&p->adjVex!=v)
{
p=q; //删除边
p=p->nextArc;
}
if(!p) return NotPresent;
if(q) q->nextArc=p->nextArc;
else lg->a[u]=p->nextArc;
free(p);
lg->e--;
return OK;
}
Status Output(LGraph lg)
{
int i;
eNode *p;
p=(eNode *)malloc(sizeof(eNode));
//p->adjVex=lg.a[i];
//p=lg.a[i];
printf("图的邻接表表示为:\n");
// printf("%d")
for(i=0;i<lg.n;i++)
{
printf("%d",i);
p=lg.a[i];
// for(j=0;j<lg.n;j++)
while(p!=NULL)
{
printf("%5d", p->adjVex);
p=p->nextArc;
}
//p=p->nextArc;
printf("\n");
}
//p=p->nextAr;
printf("\n");
}
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 DFS(LGraph lg,int v,int visited[])
{
eNode *w;
// int i;
//printf("%d",v);
// visited[v]=1;
w=(eNode *)malloc(sizeof(eNode));
//for(w=lg.a[v];w;w=w->nextArc)
//for( i=0;i<lg.n;i++)
w=lg.a[v];
printf("%d",v);
visited[v]=1;
if(visited[w->adjVex]==0)
DFS(lg,w->adjVex,visited);
}
void DFSGraph(LGraph lg)
{
int i;
int *visited=malloc(lg.n*sizeof(int));
for( i=0;i<lg.n;i++)
visited[i]=0;
for( i=0;i<lg.n;i++)
{
if(!visited[i])
DFS(lg,i,visited);
//free(visited);
}
}
void BFS(LGraph lg,int v,int visited[])
{
eNode *w;
Queue q;
w=lg.a[v];
create(&q,lg.n);
visited[v]=1;
printf("%d",v);
EnQueue(&q,v);
while(!IsEmpty(&q))
{
Front(&q,v);
DeQueue(&q);
visited[w->adjVex]=1;
printf("%d",w->adjVex);
if(visited[w->adjVex]==0)
EnQueue(&q,w->adjVex);
}
}
void BFSGraph(LGraph lg)
{
int i;
int *visited=malloc(lg.n*sizeof(int));
for( i=0;i<lg.n;i++)
visited[i]=0;
for( i=0;i<lg.n;i++)
{
if(!visited[i])
BFS(lg,i,visited);
//free(visited);
}
}
void main()
{
LGraph lg;
Init (&lg,4);
Insert(&lg,0,1,1);
Insert(&lg,1,2,1);
Insert(&lg,2,3,1);
Insert(&lg,3,0,1);
Insert(&lg,3,1,1);
Output(lg);
printf("邻接表存储下，图的深度遍历访问过的结点：\n");
DFSGraph(lg);
printf("\n");
printf("邻接表存储下，图的宽度遍历访问过的结点：\n");
BFSGraph(lg);
//Exist(&mg,1,1);
// Destroy (&mg);
#include<stdlib.h>
#define ERROR 0
#define OK 1
#define Overflow 2
#define Underflow 3
#define NotPresent 4
#define Duplicate 5
typedef int ElemType;
typedef struct eNode
{
int adjVex; //图的当前顶点数
ElemType w;
struct eNode* nextArc;
}eNode;
typedef struct
{
int n;
int e;
eNode **a;
}LGraph;
typedef struct //建立队列
{
int front;
int rear;
int maxSize;
ElemType *element;
}Queue;
typedef int Status;
Status Init(LGraph *lg,int nSize)
{
int i;
lg->n=nSize;
lg->e=0;
lg->a=(eNode**)malloc(nSize*sizeof(eNode*)); //生成长度为n的一维指针数组
if(!lg->a)
return ERROR;
else
{
for(i=0;i<lg->n;i++)
lg->a[i]=NULL;
return OK;
}
}
Status Exist(LGraph *lg,int u,int v) //边的搜索
{
eNode *p;
if(u<0||v<0||u>lg->n-1||u==v||v>lg->n-1)
return ERROR;
p=lg->a[u];//指针p指向顶点u的单链表的第一个边结点
while(p&&p->adjVex!=v) p=p->nextArc;
if(!p)
return ERROR;
else
return OK;
}
Status Insert(LGraph *lg,int u,int v,ElemType w) //边的插入
{
eNode *p;
if(u<0||v<0||v>lg->n-1||u>lg->n-1||u==v) return ERROR;
if(Exist(lg,u,v))
return Duplicate;
p=(eNode *)malloc(sizeof(eNode));
p->adjVex=v;
p->w=w; //插入新边
p->nextArc=lg->a[u];
lg->a[u]=p;
lg->e++;
return OK;
}
Status Remove(LGraph *lg,int u,int v) //边的删除
{
eNode *p,*q;
if(u<0||v<0||v>lg->n-1||u==v||u>lg->n-1)
return ERROR;
p=lg->a[u],q=NULL;
while(p&&p->adjVex!=v)
{
p=q; //删除边
p=p->nextArc;
}
if(!p) return NotPresent;
if(q) q->nextArc=p->nextArc;
else lg->a[u]=p->nextArc;
free(p);
lg->e--;
return OK;
}
Status Output(LGraph lg)
{
int i;
eNode *p;
p=(eNode *)malloc(sizeof(eNode));
//p->adjVex=lg.a[i];
//p=lg.a[i];
printf("图的邻接表表示为:\n");
// printf("%d")
for(i=0;i<lg.n;i++)
{
printf("%d",i);
p=lg.a[i];
// for(j=0;j<lg.n;j++)
while(p!=NULL)
{
printf("%5d", p->adjVex);
p=p->nextArc;
}
//p=p->nextArc;
printf("\n");
}
//p=p->nextAr;
printf("\n");
}
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 DFS(LGraph lg,int v,int visited[])
{
eNode *w;
// int i;
//printf("%d",v);
// visited[v]=1;
w=(eNode *)malloc(sizeof(eNode));
//for(w=lg.a[v];w;w=w->nextArc)
//for( i=0;i<lg.n;i++)
w=lg.a[v];
printf("%d",v);
visited[v]=1;
if(visited[w->adjVex]==0)
DFS(lg,w->adjVex,visited);
}
void DFSGraph(LGraph lg)
{
int i;
int *visited=malloc(lg.n*sizeof(int));
for( i=0;i<lg.n;i++)
visited[i]=0;
for( i=0;i<lg.n;i++)
{
if(!visited[i])
DFS(lg,i,visited);
//free(visited);
}
}
void BFS(LGraph lg,int v,int visited[])
{
eNode *w;
Queue q;
w=lg.a[v];
create(&q,lg.n);
visited[v]=1;
printf("%d",v);
EnQueue(&q,v);
while(!IsEmpty(&q))
{
Front(&q,v);
DeQueue(&q);
visited[w->adjVex]=1;
printf("%d",w->adjVex);
if(visited[w->adjVex]==0)
EnQueue(&q,w->adjVex);
}
}
void BFSGraph(LGraph lg)
{
int i;
int *visited=malloc(lg.n*sizeof(int));
for( i=0;i<lg.n;i++)
visited[i]=0;
for( i=0;i<lg.n;i++)
{
if(!visited[i])
BFS(lg,i,visited);
//free(visited);
}
}
void main()
{
LGraph lg;
Init (&lg,4);
Insert(&lg,0,1,1);
Insert(&lg,1,2,1);
Insert(&lg,2,3,1);
Insert(&lg,3,0,1);
Insert(&lg,3,1,1);
Output(lg);
printf("邻接表存储下，图的深度遍历访问过的结点：\n");
DFSGraph(lg);
printf("\n");
printf("邻接表存储下，图的宽度遍历访问过的结点：\n");
BFSGraph(lg);
//Exist(&mg,1,1);
// Destroy (&mg);
}