写出对给定的无定向图从V1结点开始广度优先搜索历序列和广度优先生成树.
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:综合作业 时间:2024/07/30 21:17:48
写出对给定的无定向图从V1结点开始广度优先搜索历序列和广度优先生成树.
![写出对给定的无定向图从V1结点开始广度优先搜索历序列和广度优先生成树.](/uploads/image/z/18151770-66-0.jpg?t=%E5%86%99%E5%87%BA%E5%AF%B9%E7%BB%99%E5%AE%9A%E7%9A%84%E6%97%A0%E5%AE%9A%E5%90%91%E5%9B%BE%E4%BB%8EV1%E7%BB%93%E7%82%B9%E5%BC%80%E5%A7%8B%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E5%8E%86%E5%BA%8F%E5%88%97%E5%92%8C%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E7%94%9F%E6%88%90%E6%A0%91.)
#include
#define QueueSize 100
typedef int DataType;
typedef struct{
int front;
int rear;
int count;
DataType data[QueueSize];
}CirQueue;
void InitQueue(CirQueue *Q){
Q->front=Q->rear=0;
Q->count=0;
}
int QueueEmpty(CirQueue *Q){
return Q->count==0;
}
int QueueFull(CirQueue *Q){
return Q->count==QueueSize;
}
void EnQueue(CirQueue *Q,DataType x){
if(QueueFull(Q)){
printf("Queue overflow!");
exit(1);
}
Q->count++;
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
}
DataType DeQueue(CirQueue *Q){
DataType temp;
if(QueueEmpty(Q)){
printf("Queue underflow!");
exit(1);
}
temp=Q->data[Q->front];
Q->count--;
Q->front=(Q->front+1)%QueueSize;
return temp;
}
DataType QueueFront(CirQueue *Q){
if(QueueEmpty(Q)){
printf("Queue is empty!");
exit(1);
}
return Q->data[Q->front];
}
#include "CirQueue.h"
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
typedef struct node{
int adjvex;
struct node *next;
}EdgeNode;
typedef struct vnode{
VertexType vertex;
EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef struct{
AdjList adjlist;
int n,e;
}ALGraph;
void CreateALGraph(ALGraph *G){
int i,j,k;
EdgeNode *s;
scanf("%d%d",&G->n,&G->e);
getchar();
printf("Enter the name of the nodes:\n");
for(i=0;in;i++){
G->adjlist[i].vertex=getchar();
G->adjlist[i].firstedge=NULL;
getchar();
}
for(k=0;ke;k++){
printf("Enter the edge of the graph:\n");
scanf("%d%d",&i,&j);
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=j;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=i;
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s;
}
}
void DFS(ALGraph *G,int i){
EdgeNode *p;
printf("visit vertex:%c\n",G->adjlist[i].vertex);
visited[i]=TRUE;
p=G->adjlist[i].firstedge;
while(p){
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void DFSTraverse(ALGraph *G){
int i;
for(i=0;in;i++)
visited[i]=FALSE;
for(i=0;in;i++)
if(!visited)
DFS(G,i);
}
void BFS(ALGraph *G,int k){
int i;
CirQueue Q;
EdgeNode *p;
InitQueue(&Q);
printf("visit vertex:%c\n",G->adjlist[k].vertex);
visited[k]=TRUE;
EnQueue(&Q,k);
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);
p=G->adjlist[i].firstedge;
while(p){
if(!visited[p->adjvex]){
printf("visit vertex:%c\n",G->adjlist[p->adjvex].vertex);
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex);
}
p=p->next;
}
}
}
void main(){
ALGraph G;
CreateALGraph(&G);
BFS(&G,0);
}
#define QueueSize 100
typedef int DataType;
typedef struct{
int front;
int rear;
int count;
DataType data[QueueSize];
}CirQueue;
void InitQueue(CirQueue *Q){
Q->front=Q->rear=0;
Q->count=0;
}
int QueueEmpty(CirQueue *Q){
return Q->count==0;
}
int QueueFull(CirQueue *Q){
return Q->count==QueueSize;
}
void EnQueue(CirQueue *Q,DataType x){
if(QueueFull(Q)){
printf("Queue overflow!");
exit(1);
}
Q->count++;
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;
}
DataType DeQueue(CirQueue *Q){
DataType temp;
if(QueueEmpty(Q)){
printf("Queue underflow!");
exit(1);
}
temp=Q->data[Q->front];
Q->count--;
Q->front=(Q->front+1)%QueueSize;
return temp;
}
DataType QueueFront(CirQueue *Q){
if(QueueEmpty(Q)){
printf("Queue is empty!");
exit(1);
}
return Q->data[Q->front];
}
#include "CirQueue.h"
#define MaxVertexNum 100
typedef char VertexType;
typedef int EdgeType;
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
typedef struct node{
int adjvex;
struct node *next;
}EdgeNode;
typedef struct vnode{
VertexType vertex;
EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];
typedef struct{
AdjList adjlist;
int n,e;
}ALGraph;
void CreateALGraph(ALGraph *G){
int i,j,k;
EdgeNode *s;
scanf("%d%d",&G->n,&G->e);
getchar();
printf("Enter the name of the nodes:\n");
for(i=0;in;i++){
G->adjlist[i].vertex=getchar();
G->adjlist[i].firstedge=NULL;
getchar();
}
for(k=0;ke;k++){
printf("Enter the edge of the graph:\n");
scanf("%d%d",&i,&j);
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=j;
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;
s=(EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex=i;
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s;
}
}
void DFS(ALGraph *G,int i){
EdgeNode *p;
printf("visit vertex:%c\n",G->adjlist[i].vertex);
visited[i]=TRUE;
p=G->adjlist[i].firstedge;
while(p){
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->next;
}
}
void DFSTraverse(ALGraph *G){
int i;
for(i=0;in;i++)
visited[i]=FALSE;
for(i=0;in;i++)
if(!visited)
DFS(G,i);
}
void BFS(ALGraph *G,int k){
int i;
CirQueue Q;
EdgeNode *p;
InitQueue(&Q);
printf("visit vertex:%c\n",G->adjlist[k].vertex);
visited[k]=TRUE;
EnQueue(&Q,k);
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);
p=G->adjlist[i].firstedge;
while(p){
if(!visited[p->adjvex]){
printf("visit vertex:%c\n",G->adjlist[p->adjvex].vertex);
visited[p->adjvex]=TRUE;
EnQueue(&Q,p->adjvex);
}
p=p->next;
}
}
}
void main(){
ALGraph G;
CreateALGraph(&G);
BFS(&G,0);
}
已知一个有向图如图,请分别写出从顶点a出发进行深度优先遍历和广度优先遍历所得到的顶点序列及生成树.
已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是
深度优先搜索和广度优先搜索、A星算法三种算法的区别和联系?
(求解C程序高手)用正向表存储图的数据,并实现图的深度优先搜索和广度优先搜索.
邻接矩阵、邻接表表示图时的深度优先序列、广度优先序列
2、设某个图的邻接表如图2,根据该临界表执行从顶点A出发的广度优先搜索算法,则经历的
求一个源代码要求显示图的邻接矩阵图的邻接表,深度广度优先遍历最小生成树PRIM算法KRUSCAL算法图的连通分
已知二维数组表示的图的邻接矩阵如下图所示.试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优
1.用邻接表表示图 广度优先搜索 通常采用什么实现算法 a 栈 b 队列 c 树 d图
dijkstra算法是深度优先还是广度优先?
用邻接表表示的图进行广度优先遍历时,通常是采用()来实现算法的.
已知图的邻接矩阵,根据算法思想,则从顶点0出发按深度优先遍历的结点序列是