通信网中的算法问题—深入优先算法和广度优先算法
实验名称：（用C语言实现）
通信网中的算法问题—深入优先算法和广度优先算法（节点遍历）
实验内容：
1、以任意节点为起点，利用深度优先搜索算法，计算附图的遍历顺序并打印输出（是否可以用2种不同的实现方法）；
2、以任意节点为起点，利用广度优先搜索算法，计算附图的遍历顺序并打印输出（是否可以用2种不同的实现方法）；
注意：
1、请转换附件的图形为输入数据格式（附在实验报告上）；
2、请打印的时候把节点编号、节点名称按照遍历的顺序打印.
具体显示内容：
1、节点数**
2、节点编号及名称**
3、边数**
4、深度优先搜索结果：（例如：1、重庆；4、上海）
5、广度优先搜搜结果：
6、是连通图，所有节点都遍历；
不是连通图，**节点无法遍历；
参考一下
#include
#include
#include
#define MAXNODE 30//最大节点数
int graph[MAXNODE][MAXNODE]={{0,1,1,0,0,0},{1,0,0,1,0,0},{1,0,0,0,0,1},\
{0,1,0,0,1,0},{0,0,0,1,0,0},{0,0,1,0,0,0}};//默认无向图
char sign[MAXNODE]={'a','b','c','d','e','f'};//默认节点标志
int num_node=6,num_edge=7;//节点数 边数
int queue[MAXNODE],stack[MAXNODE],stack_2[MAXNODE];//队列 栈
int *end_queue=NULL,*end_stack=NULL,*end_stack_2=stack_2;//队列指针 栈指针
void in_queue(int a);//入队函数
int out_queue();//出队函数
int insearch_queue(int i);//查找队列
void display_queue();//显示队列
void in_stack(int a);//入栈函数
int out_stack();//出栈函数
int insearch_stack(int i);//查找栈
void display_stack();//显示栈
void main()
{
/* // There are declarations! void display_graph();//显示无向图 void init(int choose);//初始化函数 void build();//建立无向图 void DFS(char a);//深度优先 void BFS(char a);//广度优先 */
int i,j,k;
int choose;
char c;
while (choose!=1 && choose!=2)
{
printf("**********************************************************\n");
printf(" 1、构建无向路径图 2、使用默认无向路径图 3、退出程序\n");
printf("**********************************************************\n");
printf("请选择：");
scanf("%d",&choose);
switch(choose)
{
case 1:
init(choose);
build();
break;
case 2:
init(choose);
break;
case 3:exit(0);
break;
default:printf("请输入1-3!\n");
break;
}
}
display_graph();
while (1)
{
printf("******************************************\n");
printf(" 1、广度优先 2、深度优先 3、退出程序\n");
printf("******************************************\n");
printf("请选择：");
scanf("%d",&choose);
getchar();
switch(choose)
{
case 1:
printf("输入起点：");
scanf("%c",&c);
getchar();
BFS(c);
break;
case 2:
printf("输入起点：");
scanf("%c",&c);
getchar();
DFS(c);
break;
case 3:exit(0);
break;
default:printf("请输入1-3!\n");
break;
}
}
}
void init(int choose)
{
int i,j;
if (choose==1)
{
for (i=0;i
{
for (j=0;j
{
graph[i][j]=0;
}
}
}
for (i=0;i<20;i++)
{
queue[i]=-1;
}
for (i=0;i<20;i++)
{
stack_2[i]=stack[i]=-1;
}
}
void build()
{
void link(char a,char b);//连接节点
int i,j;
char a,b;
printf("请输入顶点数,边数(用逗号分开，例如：8,5)：");//输入节点数边数
scanf("%d,%d",&num_node,&num_edge);
getchar();
for (i=0;i
{
printf("输入NO.%d标志(一个字符):",i+1);
scanf("%c",&sign[i]);
getchar();
}
printf("请输入边(用逗号分开，例如：a,b)：");
for (i=0;i
{
printf("输入第%d条边:",i+1);
scanf("%c,%c",&a,&b);
getchar();
printf("%c %c\n",a,b);
link(a,b);
}
}
void link(char a,char b)
{
int a_num,b_num,i;
for (i=0;i
{
if (a==sign[i])
{
a_num=i;
break;
}
}
for (i=0;i
{
if (b==sign[i])
{
b_num=i;
break;
}
}
graph[a_num][b_num]=1;
graph[b_num][a_num]=1;
}
void display_graph()
{
int i,j;
printf("构建的无向图如下：\n ");
for (j=0;j
{
printf("%-2c",sign[j]);
}
printf("\n");
for (i=0;i
{
printf("%-2c",sign[i]);
for (j=0;j
{
printf("%-2d",graph[i][j]);
}
printf("\n");
}
}
void DFS(char a)
{
int i,a_num,j,repect;
for (i=0;i
{
if (a==sign[i])
{
a_num=i;
break;
}
}
in_stack(a_num);
for (j=0;j<30;j++)
{
for(i=0;i
{
if(graph[*end_stack][i]==1)
{
if (insearch_stack(i)!=1)
{
in_stack(i);
i=-1;
}
}
}
if (out_stack()==1)
{
break;
}
}
printf("深度优先：");
for (i=0;stack_2[i]!=-1;i++)
{
printf("%c ",sign[stack_2[i]]);
}
printf("\n\n");
}
void BFS(char a)
{
int a_num,i,j,repect;
int *p;
for (i=0;i
{
if (a==sign[i])
{
a_num=i;
break;
}
}
in_queue(a_num);
for (j=0;j<30;j++)
{
for(i=0;i
{
if(graph[*end_queue][i]==1)
{
if (insearch_queue(i)!=1)
{
in_queue(i);
}
}
}
if (out_queue()==1)
{
break;
}
}
p=queue;
printf("广度优先：");
for (i=num_node;i>0;i--)
{
printf("%c ",sign[*(p+i-1)]);
}
printf("\n\n");
}
void in_queue(int a)
{
int *p;
if (end_queue==NULL)
{
end_queue=queue;
*end_queue=a;
}
else
{
for (p=queue;*p!=-1;p++)
{
}
p--;
for (;;p--)
{
*(p+1)=*p;
if (p==queue)
{
*p=a;
break;
}
}
end_queue++;
}
// printf("in:");
//display_queue();
}
int out_queue()
{
if (end_queue!=queue)
{
end_queue--;
// printf("out:");
// display_queue();
return 0;
}
else
{
end_queue=NULL;
// printf("out:");
// display_queue();
return 1;
}
}
int insearch_queue(int i)
{
int j;
for(j=0;j<20;j++)
{
if(i==queue[j])
{
return 1;
}
}
return 0;
}
void display_queue()
{
int *p,i;
p=queue;
for (i=0;i<20;i++)
{
printf("%d ",*(p+i));
}
printf("\n");
}
void in_stack(int a)
{
*end_stack_2=a;
end_stack_2++;
if (end_stack==NULL)
{
end_stack=stack;
*end_stack=a;
// printf("in:");
// display_stack();
}
else
{
end_stack++;
*end_stack=a;
// printf("in:");
// display_stack();
}
}
int out_stack()
{
if (end_stack!=stack)
{
*end_stack=-1;
end_stack--;
// printf("out:");
// display_stack();
return 0;
}
else
{
*end_stack=-1;
end_stack=NULL;
// printf("out:");
// display_stack();
return 1;
}
}
int insearch_stack(int i)
{
int j;
for(j=0;j<20;j++)
{
if(i==stack_2[j])
{
return 1;
}
}
return 0;
}
void display_stack()
{
int *p,i;
p=stack;
for (i=0;i<20;i++)
{
printf("%d ",*(p+i));
}
printf("\n");
}