【算法导论】图的创建，深度优先访问，广度优先访问（递归/非递归）

这里仅仅贴出来我调试好的代码……更详细的解释在代码注释中。

#include "stdio.h"
#include "malloc.h"
#define MaxSize 10
#define MaxValue 99999
/*邻接表 ：Adjacency list*/
typedef struct ArcNode //边 表节点
{
int adjvex;//邻接点 数值
ArcNode *next;//下一个节点
}ArcNode ;
typedef struct VertexNode //顶点 表节点
{
char vertex; //顶点表示（A,B，C）
ArcNode *firstedge;//第一个邻接点
}VertexNode,AdjList[MaxSize]; //为什么要写在这个地方 ????

//vertexNode AdjList[MaxSize]; //这样为什么不对？？

typedef struct
{

AdjList adjlist ;//顶点表 就是竖着的一排 不能是指针么???????????? !!!!!!!!!!!
int VertexNumber,arcNum;//图的顶点个数，边个数
}AlGraph;

void CreatALGraph(AlGraph *G,char a[],int n,int e) //顶点 由数组提供， 边需要用户输入
{
int i,k,j;
G->VertexNumber=n;// 顶点个数
G->arcNum=e;//边个数
for(i=0;i<G->VertexNumber;i++)//初始化 顶点列表
{
G->adjlist[i].vertex=a[i];
G->adjlist[i].firstedge=NULL;
}

for(k=0;k<G->arcNum;++k)//每次输入 一条边 <i,j> 将该顶点插入 i 顶点后的列链表中
{
printf("please input the number of edge's two vertex\n");
scanf("%d%d",&i,&j);//有向图 f
ArcNode *s=(ArcNode *)malloc(sizeof(ArcNode));

s->adjvex=j; //所邻接的 顶点在顶点列表中的下标

//接下来 将创建好的边 表节点插入 节点i 的边表的表头
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
}
}
void print_Graph(AlGraph *G) //简单的打印出来
{
int i;
for(i=0;i<G->VertexNumber;++i) //输出每一行
{
ArcNode *node= G->adjlist[i].firstedge;
printf("%c",G->adjlist[i].vertex);//输出链表节点

while(node)//输出后续节点
{
//printf("--->%d", node->adjvex);
printf("--->%c", G->adjlist[1].vertex);
node=node->next;
}
printf("\n");
}
}
void DFSTraverse(AlGraph *G,int v)//深度优先遍历
{
int visited[v];//用来区别 顶点有没有被访问过
int j;
printf("%c",G->adjlist[v].vertex);//输出顶点 （递归调用 条件下文给出）
visited[v]=1;
ArcNode *p=G->adjlist[v].firstedge;

while(p!=NULL)
{
j=p->adjvex;//后继 的节点的下标
if(visited[j]!=1)//后继顶点没有被访问，则递归访问
DFSTraverse(G,j);

p=p->next;
}
}
void BFSTraverse(AlGraph *G,int v)//深度优先遍历 (递归)
{
int visited[v];//用来区别 顶点有没有被访问过
int front,rear,j;
int Q[MaxSize];
front =rear=-1;//初始化队列
printf("%c",G->adjlist[v].vertex);

visited[v]=1;
Q[++rear]=v;

while(front!=rear)
{
v=Q[++front];
ArcNode *p=G->adjlist[v].firstedge;

while(p!=NULL)
{
j=p->adjvex;//后继 的节点的下标
if(visited[j]!=1)//后继顶点没有被访问，则递归访问
{
printf("%c",G->adjlist[j].vertex);
visited[j]=1;
Q[++rear]=j;
}
p=p->next;
}
}
}

void BFS(AlGraph *G,int s) //非递归 广度优先
{
int i,u;
char color[G->VertexNumber];//表示颜色
int d[G->VertexNumber];//表示路径值
int pi[G->VertexNumber];//表示祖先
for(i=1;i<G->VertexNumber;++i)//初始化
{
color[i]='W';//初始化为白色
d[i]=MaxValue;
//pi[i]=NULL;
}

color[s]='G';//设置成灰色
d[s]=0;
//pi[s]=NULL;

int Q[MaxSize];//初始化队列
int front =-1;
int rear=-1;//初始化队列
Q[++rear]=s;//插入队列

while(front!=rear)
{

u=Q[++front];//弹出队列头
ArcNode *p=G->adjlist[u].firstedge;//这里是u
while(p!=NULL)//访问所有跟 u 相邻的节点
{
if(color[p->adjvex]=='W')//是白色 ，没有被访问过
{
color[p->adjvex]='G';
d[p->adjvex]=d[u]+1;
pi[p->adjvex]=u;

Q[++rear]=p->adjvex;//插入队列

}
p=p->next;
}

printf("%3c",G->adjlist[u].vertex);
color[u]='B';
}


}

void DFS_VISIT(AlGraph *G, int u,char color[],int d[],int f[],int time,int pi[])//被深度优先访问调用
{
color[u]='G';
++time;
d[u]=time;//第一个时间戳

ArcNode *p=G->adjlist[u].firstedge;//这里是u
while(p!=NULL)//访问所有跟 u 相邻的节点
{
if(color[p->adjvex]='W')
{
pi[p->adjvex]=u;
DFS_VISIT(G,p->adjvex,color,d,f,time,pi);
}
p=p->next;

}
color[u]='B';
printf("%3c",G->adjlist[u].vertex);
f[u]=time+1;

}
int time=0;//时间戳应该是全局变量

void DFS(AlGraph *G)//深度优先遍历
{
char color[G->VertexNumber];
int pi[G->VertexNumber];
int d[G->VertexNumber];//时间戳一
int f[G->VertexNumber];//时间戳二

int i;
for(i=0;i<G->VertexNumber;++i)//初始化
{
color[i]='W';//初始化为白色
time=0;
//pi[i]=NULL;
}
for(i=0;i<G->VertexNumber;++i)//从上到下访问
{
if(color[i]='W')
{
DFS_VISIT(G,i,color,d,f,time,pi);//深度优先访问
}
}
}

int main()
{
AlGraph *G=(AlGraph *)malloc(sizeof(AlGraph));
char a[3]={'A','B','C'};
int n=3;
int e=2;
printf("********************\n");
printf("1,创建邻接表类型的图\n");
printf("2,邻接表真实输出\n");
printf("3,邻接表深度优先访问\n");
printf("4,邻接表广度优先访问\n");
printf("5,邻接表非递归广度优先访问(算法导论)\n");
printf("6,邻接表深度优先访问（算法导论）\n");/////这个调用，有错误。需要设全局变量。没改
printf("********************\n");

int i;

while(1)
{
scanf("%d",&i);
switch(i)
{
case 1:CreatALGraph(G,a,n,e);
printf("创建完毕请继续……\n");break;
case 2:print_Graph(G);
printf("操作完毕请继续……\n");break;
case 3:DFSTraverse(G,0);
printf("操作完毕请继续……\n");break;
case 4:BFSTraverse(G,0);
printf("操作完毕请继续……\n");break;
case 5:printf("广度优先遍历：\n");
BFS(G,0);
printf("操作完毕请继续……\n");break;
case 6:DFS(G);
printf("操作完毕请继续……\n");break;
case 7:break;
case 8:break;
case 9:break;

}

}

return 0;
}