|
/*
======================================== */
/*
图形的遍历
*/
/* ======================================== */
#include <stdlib.h>
#define MAXQUEUE
70
/* 伫列的最大容量
*/
struct
node
/* 图形顶点结构宣告
*/
{
int
vertex;
/* 顶点资料
*/
struct node
*nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node
head[61];
/* 图形顶点结构数组
*/
int
visited[61];
/* 遍历记录数组
*/
int
queue[MAXQUEUE];
/* 伫列的数组宣告
*/
int front =
-1;
/* 伫列的前端
*/
int rear =
-1;
/* 伫列的后端
*/
/* ----------------------------------------
*/
/* 建立图形
*/
/* ---------------------------------------- */
void creategraph(int *node,int num)
{
graph
newnode;
/* 新顶点指标
*/
graph ptr;
int
from;
/* 边线的起点
*/
int
to;
/* 边线的终点
*/
int i;
for ( i
= 0; i < num; i++ ) /* 读取边线的回路 */
{
from =
node[i*2]; /* 边线的起点
*/
to =
node[i*2+1]; /*
边线的终点
*/
/* 建立新顶点记忆体 */
newnode = ( graph ) malloc(sizeof(struct
node));
newnode->vertex =
to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值
*/
ptr =
&(head[from]); /* 顶点位置
*/
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr =
ptr->nextnode; /* 下一个顶点
*/
ptr->nextnode =
newnode; /* 插入结尾
*/
}
}
/*
---------------------------------------- */
/* 伫列资料的存入
*/
/* ---------------------------------------- */
int enqueue(int value)
{
if ( rear >= MAXQUEUE
) /* 检查伫列是否全满 */
return
-1;
/* 无法存入
*/
rear++;
/* 后端指标往前移
*/
queue[rear] =
value; /* 存入伫列
*/
}
/*
---------------------------------------- */
/* 伫列资料的取出
*/
/* ---------------------------------------- */
int dequeue()
{
if ( front == rear
) /* 检查伫列是否是空 */
return
-1;
/* 无法取出
*/
front++;
/* 前端指标往前移
*/
return
queue[front];
/* 伫列取出
*/
}
/*
---------------------------------------- */
/* 图形的广度优先搜寻法
*/
/* ---------------------------------------- */
void bfs(int current)
{
graph ptr;
/* 处理第一个顶点 */
enqueue(current);
/* 将顶点存入伫列
*/
visited[current] =
1; /* 记录已遍历过
*/
printf("[%d]
",current); /* 印出遍历顶点值 */
while ( front != rear
) /* 伫列是否是空的
*/
{
current =
dequeue(); /* 将顶点从伫列取出 */
ptr = head[current].nextnode; /*
顶点位置
*/
while ( ptr != NULL
) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex]
== 0 ) /* 如过没遍历过 */
{
enqueue(ptr->vertex); /* 递回遍历呼叫 */
visited[ptr->vertex] = 1; /* 记录已遍历过 */
/* 印出遍历顶点值 */
printf("[%d]
",ptr->vertex);
}
ptr = ptr->nextnode;
/* 下一个顶点
*/
}
}
}
/*
---------------------------------------- */
/* 图形的深度优先搜寻法
*/
/* ---------------------------------------- */
void dfs(int current)
{
graph ptr;
visited[current] = 1;
/* 记录已遍历过
*/
printf("[%d]
",current); /* 印出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置
*/
while ( ptr != NULL
) /* 遍历至链表尾
*/
{
if ( visited[ptr->vertex] == 0 ) /*
如过没遍历过 */
dfs(ptr->vertex);
/* 递回遍历呼叫 */
ptr =
ptr->nextnode;
/* 下一个顶点 */
}
}
/*
---------------------------------------- */
/* 主程式: 建立图形后,将遍历内容印出. */
/* ---------------------------------------- */
void main()
{clrscr();
while(1)
{
char c,a;
graph ptr;
int i;
int node[60][2] = { {1, 10}, {10, 1}, /* 边线数组
*/
{2, 10}, {10, 2},
{2, 3}, {3, 2},
{3, 4}, {4, 3},
{3, 12}, {12, 3},
{4, 13}, {13, 4},
{4, 5}, {5, 4},
{5, 6}, {6, 5},
{5, 7}, {7, 5},
{7, 8}, {8, 7},
{9, 10}, {10, 9},
{10, 11}, {11, 10},
{11, 14}, {14, 11},
{11, 12}, {12, 11},
{12, 15}, {15, 12},
{12, 13}, {13, 12},
{13, 16}, {16, 13},
{14, 17}, {17, 14},
{14, 18}, {18, 14},
{15, 19}, {19, 15},
{16, 20}, {20, 16},
{17, 18}, {18, 17},
{18, 23}, {23, 18},
{18, 19}, {19, 18},
{19, 23}, {23, 19},
{19, 24}, {24, 19},
{19, 20}, {20, 19},
{20, 21}, {21, 20},
{22, 23}, {23, 22},
{24, 25}, {25,24}
};
clrscr();
printf("\n\n\n");
printf("/*------------------------------------------------------*/\n");
printf("/*
欢 迎 使 用 本 程 序
*/\n");
printf("/*------------------------------------------------------*/\n");
printf(" 本 程 序 是 有 关 图 的 遍 历 的 算 法 演 示,\n");
printf("如 果 有 不 足 之 处 敬 请 原 谅!\n\n");
printf("请 问 你 是 否 要 运 行 以 下 的 程 序:\n\n");
printf(" 图 的 深 度 遍 历 和 广 度 遍 历? Y/N?\n");
c=getch();
if(c!='y'&&'Y')
exit(0);
clrscr();
printf("\n\n");
printf("请 注 意 以 下 为 各 城 市 的 代 码:\n\n");
printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");
printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");
printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");
printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");
printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");
for
(i=1;i<=25;i++ )
{
head[i].vertex=i; /* 设定顶点值
*/
head[i].nextnode=NULL; /* 清除图形指标
*/
visited[i]=0;
/* 设定遍历初值
*/
}
creategraph(node,60);
/* 建立图形
*/
printf("图 形 的 邻 接 链 表 内 容:\n");
for (i=1;i<=25;i++)
{ if(i%3==0)printf("\n");
printf("顶点%d=>",head[i].vertex); /* 顶点值
*/
ptr=head[i].nextnode;
/* 顶点位置
*/
while(ptr!=NULL) /* 遍历至链表尾
*/
{
printf("%d ",ptr->vertex); /* 印出顶点内容 */
ptr=ptr->nextnode; /* 下一个顶点
*/
}
}
printf("\n\n");
printf("请 选 择 你 需 要 的 操 作\n");
printf("1、图形的广度优先遍历请输入:'g'或'G'\n");
printf("2、图形的深度优先遍历请输入:'s'或'S'\n");
c=getch();
switch(c)
{
case'g':case'G':
printf("\n请 你 输 入 你 需 要 的 起 始 顶 点:\n");
scanf("%d",&i);
clrscr();
printf("\n\n");
printf("请 注 意 以 下 为 各 城 市 的 代 码:\n\n");
printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");
printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");
printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");
printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");
printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");
printf("图 形 的 广 度 优 先 遍 历 的 顶 点 内 容:\n");
bfs(i);
/* 印出遍历过程
*/
printf("\n");
/* 换行
*/
break;
case's':case'S':
printf("\n请 输 入 你 需 要 的 起 始 顶 点:\n");
scanf("%d",&i);
clrscr();
printf("\n\n");
printf("请 注 意 以 下 为 各 城 市 的 代 码:\n\n");
printf("1:乌鲁木齐; 2:呼和浩特; 3:北京; 4:天津; 5:沈阳; \n");
printf("6:大连; 7:长春; 8:哈尔滨; 9:西宁; 10:兰州;\n");
printf("11:西安; 12:郑州; 13:徐州; 14:成都; 15:武汉; \n");
printf("16:上海; 17:昆明; 18:贵阳; 19:株州; 20:南昌;\n");
printf("21:福州; 22:南宁; 23:柳州; 24:广州; 25:深圳.\n");
printf("图 形 的 深 度 优 先 遍 历 的 顶 点 内 容:\n");
dfs(i);
/* 印出遍历过程
*/
printf("\n");
/* 换行
*/
break;
}
printf("\n请 问 你 是 否 要 继 续:y/n");
a=getch();
if(a!='y'&&'Y')
exit(0);
}
}
|