int Visited[MAX_VERTEX_NUM]; int PrintCheck(ALGraph* pag) {
int i; ArcNode* p; printf("\nCheck the Graph!\n"); printf("No\tdata\tnext\tnext\t.....\n"); for(i=0; i<pag->vexnum; i++) {
ag.arcnum = i;
printf("\n 初始化图的边，结点从 0 开始计，最大为%d\n",n-1); for(i=1; i<=ag.arcnum; i++) {
while(1) {
printf("第<%d>条边的起点: ",i); fflush(stdin); scanf("%d",&start);
m = (n-2)*(n+1)/2+1;
while(1) {
printf("请输入边的数量: "); fflush(stdin); scanf("%d",&i);
if(i<=m && i>=0) break; else printf("\n 请注意边的数量不能大于%d,并且不能小于 1!\n",m); }
所有节点都搜索到了之后才向下一层搜索。
四、实验步骤 1．建立图的存储结构； 2．输入图的基本接点与信息，初始化图； 3．编写图的深度优先搜索（DFS）和广度优先搜索算法（BFS）程序； 4.采用菜单形式进行显示与选择。 5.测试数据和结果显示 （1）从键盘输入顶点数和边数； （2）输入顶点信息； （3）输入边的信息，以（a,b）的形式输入边的信息，构建一个无向图； （4）对此无向图进行深度优先搜索和广度优先搜索，并输出正确的序列。
char cData; ArcNode* firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum; int arcnum; }ALGraph; typedef struct LinkNode{ ArcNode* parc; struct LinkNode* next; }LinkNode;
return 1; } void DFS(ALGraph ag,int start) {
LinkNode* Stack = (LinkNode*)malloc(sizeof(LinkNode)); LinkNode* pStack = (LinkNode*)malloc(sizeof(LinkNode)); LinkNode* temp; ArcNode* p; int i; if(!pStack||!Stack)
课程名称 实验项目
实验报告 数据结构 实现深度优先搜索与广度优先搜索算法
一、实验目的 1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历； 2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。
二、实验内容 1、建立图的存储方式； 2、图的深度优先搜索算法； 3、图的广度优先搜索算法。
{
if(!Visited[i])
printf(" %c ",ag.vertices[i].cData);
p = ag.vertices[i].firstarc;
}
if(i = ag.vexnum)
break;
}
printf("\n\n");
}
void main()
{
ALGraph ag;
int i,n,m;
return; Stack->next=NULL; p=ag.vertices[start].firstarc; Visited[start]=1; printf("\n 输出深度优先遍历顺序:"); printf(" %c ",ag.vertices[start].cData); while(1) {
五、程序源代码及注释
#include<stdio.h> #include<malloc.h> #include<windows.h> #define MAX_VERTEX_NUM 20 typedef struct ArcNode{
int adjvex;
struct ArcNode* nextarc; }ArcNode; typedef struct VNode{
last->next = pQueue;
last = last->next;
}
p = p->nextarc;
}
temp = Queue->next;
p = ag.vertices[temp->parc->adjvex].firstarc;
Queue ->next = temp->next;
}
for(i=0; i<ag.vexnum; i++)
Visited[start] = 1;
while(1)
{
pQueue->parc = p;
Queue->next = pQueue;
pQueue->next = NULL;
last = pQueue;
while(p && Queue->next)
{
while(p)
{
if(!Visited[p->adjvex])
DFS(ag,choose);
i = 0; while(Visited[i]!='\0') {
arcNodes->nextarc = pag->vertices[start].firstarc; pag->vertices[start].firstarc = arcNodes; } else{ while(p->nextarc) p = p->nextarc; p->nextarc = arcNodes; arcNodes->nextarc = NULL; } arcNodee->adjvex = start; p = pag->vertices[end].firstarc; if(!p) { arcNodee->nextarc = pag->vertices[end].firstarc; pag->vertices[end].firstarc = arcNodee; } else{ while(p->nextarc) p = p->nextarc; p->nextarc = arcNodee; arcNodee->nextarc = NULL; }
printf("%d\t%c\t",i,pag->vertices[i].cData); p = pag->vertices[i].firstarc; while(p) {
printf("%d\t",p->adjvex); p = p->nextarc; } printf("\n"); } return 1; } int CreateGraph(ALGraph* pag,int start,int end) { ArcNode* arcNodes = (ArcNode*)malloc(sizeof(ArcNode)); ArcNode* arcNodee = (ArcNode*)malloc(sizeof(ArcNode)); ArcNode* p; if(!arcNodes || !arcNodee) return 0; arcNodes->adjvex = end; p = pag->vertices[start].firstarc; if(!p) {
{
LinkNode* Queue = (LinkNode*)malloc(sizeof(LinkNode));
LinkNode* pQueue = (LinkNode*)malloc(sizeof(LinkNode));
LinkNode* temp;
LinkNode* last;
ArcNode* p;
pStack->parc = p; pStack->next = Stack->next; Stack->next = pStack; while(p && (Stack->next)) {
while(p) {
if(Visited[p->adjvex]) p=p->nextarc;
else
{
Visited[p->adjvex]=1;
int choose;
int start,end;
while(1)
{
printf("请输入图的结点个数,并回车: ");
scanf("%d",&n);
if(n<MAX_VERTEX_NUM && n>0)
break; else printf("\n 请注意结点个数不能大于 20,并且不能为 0!\n"); }
ag.vexnum = n;
printf("\n 初始化图的结点，输入字符并回车:\n"); for(i=0; i<ag.vexnum; i++) {
printf("No.%d = ",i); fflush(stdin); scanf("%c",&ag.vertices[i].cData); ag.vertices[i].firstarc = NULL; }