b-20-5.cpp

数据结构168个实验程序,很全面

#include<stdio.h>
#include<stdlib.h>
#define vertexnum 9
#define queuemax 10
struct node 
{int vertex;
struct node *next;
};
typedef struct node *graph;
struct node head[vertexnum];
int queue[queuemax];
int front=-1;
int rear=-1;
int visited[vertexnum];
int enqueue(int vertex)
{if(rear>=queuemax)
return -1;
else
{rear++;
queue[rear]=vertex;
return 1;
}
}
int dequeue()
{if(front==rear)
return -1;
else
{front++;
return queue[front];
}
}
void bfs(int vertex)
{graph pointer;
enqueue(vertex);
visited[vertex]=1;
printf("[%d]==>",vertex);
	   while(front!=rear)
	   {vertex=dequeue();
	   pointer=head[vertex].next;
	   while(pointer!=NULL)
	   {if(visited[pointer->vertex]==0)
	   {enqueue(pointer->vertex);
	   visited[pointer->vertex]=1;
	   printf("[%d]==>",pointer->vertex);
	   }
	   pointer=pointer->next;
	   }
	   }
}
void create_l_graph(int vertex1,int vertex2)
{graph pointer;
graph NEW;
NEW=(graph)malloc(sizeof(struct node));
if(NEW!=NULL)
{NEW->vertex=vertex2;
NEW->next=NULL;
pointer=&(head[vertex1]);
while(pointer->next!=NULL)
pointer=pointer->next;
pointer->next=NEW;
}
}
void print_l_graph(struct node *head)
{graph pointer;
pointer=head->next;
while(pointer!=NULL)
{printf("[%d]",pointer->vertex);
pointer=pointer->next;
}
printf("\n");
}
void main()
{int i;
int node[20][2]={{1,2},{2,1},{1,3},{3,1},{2,4},{4,2},{2,5},{5,2},{3,6},{6,3},{3,7},{7,3},{4,8},{8,4},{5,8},{8,5},{6,8},{8,6},{7,8},{8,7}};
for(i=0;i<vertexnum;i++)
{head[i].vertex=i;
head[i].next=NULL;
}
for(i=0;i<vertexnum;i++)
visited[i]=0;
for(i=0;i<20;i++)
create_l_graph(node[i][0],node[i][1]);
printf("##已知图为##\n");
for(i=1;i<vertexnum;i++)
{printf("vertex[%d]:",i);
print_l_graph(&head[i]);
}
printf("广度优先搜索的结果为:\n");
printf("[begin]==>");
bfs(4);
printf("[end]");
}