通信网中的算法问题—深入优先算法和广度优先算法

Question

实验名称：（用C语言实现）
通信网中的算法问题—深入优先算法和广度优先算法（节点遍历）

实验内容：
1、以任意节点为起点，利用深度优先搜索算法，计算附图的遍历顺序并打印输出（是否可以用2种不同的实现方法）；
2、以任意节点为起点，利用广度优先搜索算法，计算附图的遍历顺序并打印输出（是否可以用2种不同的实现方法）；

注意：
1、请转换附件的图形为输入数据格式（附在实验报告上）；
2、请打印的时候把节点编号、节点名称按照遍历的顺序打印.

具体显示内容：
1、节点数**
2、节点编号及名称**
3、边数**
4、深度优先搜索结果：（例如：1、重庆；4、上海）
5、广度优先搜搜结果：
6、是连通图，所有节点都遍历；
不是连通图，**节点无法遍历；

Answer 1

参考一下

#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");

}