基于图的广度优先搜索策略（耿7.11）--------西工大noj.20
2024-10-20 16:20:03
目录
代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct ArcNode{
int to;
struct ArcNode *next;
int w;
}ArcNode;
typedef struct VertexNode
{
int data;
ArcNode *arc;
}VertexNode;
typedef struct Graph
{
int max;
VertexNode *vertex;
}Graph;
//这是全局变量
int dream;
int find;
//这个是手写的队列
typedef struct QNode{
int data;
struct QNode*next;
}QNode;
typedef struct Queue{
QNode*head, *tail;
}Queue;
Queue *Create_Queue()
{
Queue *Q = (Queue*)malloc(sizeof(Queue));
Q->tail = NULL;
Q->head = NULL;
return Q;
}
int Empty(Queue*Q)
{
if(Q->head)
return 0;
else
return 1;
}
void Push(Queue* Q,int x)
{
QNode*s = (QNode*)malloc(sizeof(QNode));
s->data = x;
s->next = NULL;
if(Empty(Q))
{
Q->head = s;
Q->tail = s;
}
else
{
Q->tail->next = s;
Q->tail = s;
}
}
int Top(Queue*Q)
{
return Q->head->data;
}
void Pop(Queue*Q)
{
QNode* d = Q->head;
Q->head = Q->head->next;
free(d);
}
Graph *Create(int n)
{
Graph *G = (Graph*)malloc(sizeof(Graph));
G->max = n;
G->vertex = (VertexNode*)calloc(n+1,sizeof(VertexNode));
for(int i = 0; i <= n; i++)
{
G->vertex[i].arc = NULL;
}
return G;
}
int Locate(Graph *G,int x)
{
int i = 1;
for(; i<=G->max; i++)
{
if(G->vertex[i].data == x)
break;
}
if(i > G->max)
return -1;
else
return i;
}
void Fill_VertexNode(Graph *G, int n)
{
for(int i = 1; i <= n; i++)
{
scanf("%d",&G->vertex[i].data);
}
}
void Add(Graph *G,int x, int y)
{
int a = Locate(G,x);
int b = Locate(G,y);
ArcNode *A = (ArcNode*)malloc(sizeof(ArcNode));
A->to = b;
A->next = G->vertex[a].arc;
G->vertex[a].arc = A;
}
void BFS(Graph* G,int * arr, int x)
{
if(arr[x])
return;
Queue *Q = Create_Queue();
Push(Q,x);
while(!Empty(Q))
{
int t = Top(Q);
Pop(Q);
if(G->vertex[t].data == dream)
{
find = 1;
return;
}
for(ArcNode *A = G->vertex[t].arc; A; A = A->next)
{
if(arr[A->to])
continue;
Push(Q,A->to);
}
}
}
int BFS_search(Graph*G, int x,int dre)
{
find = 0;
x = Locate(G,x);
dream = dre;
int *arr = (int *)calloc(G->max+1, sizeof(int));
for(int i = 0; i <= G->max; i++)
{
arr[i] = 0;
}
BFS(G,arr,x);
return find;
}
int main()
{
int begin, end;
int n,m;
scanf("%d%d",&n,&m);
Graph *G = Create(n);
Fill_VertexNode(G,n);
for(int i = 1; i <= m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
Add(G,x,y);
}
scanf("%d%d",&begin,&end);
int ret = BFS_search(G,begin,end);
if(ret) printf("yes");
else printf("no");
return 0;
}
/*
4 4
4 2 1 3
1 2
1 3
1 4
2 3
2 3
*/
最新文章
- SQL Server 2000 sp2 及更低版本不受此版本的 Windows 支持
- class && struct
- 1、android源代码下载及目录分析，和eclipser的跟踪
- Sprint第三个冲刺（第七天）
- 向MySql中插入中文时出现乱码
- Linux学习笔记（7）-系统资源查看
- Flume学习——Flume的架构
- Android 如何更换屏幕上锁界面背景图片
- Frequent values
- MYSQL数据备份与还原学习笔记
- （转） CS0234: 命名空间“System.Web.Mvc”中不存在类型或命名空间名称“Ajax”(是否缺少程序集引用?)
- EasyUI datagrid简单运用
- 多点触控插件Hammer.js
- 苹果新的编程语言 Swift 语言进阶（十三）－－类型检查与类型嵌套
- 【洛谷P2822 组合数问题】
- 【 P3952】 时间复杂度 大模拟题解
- iOS开发简记（2）：自定义tabbar
- php 原生文件下载
- wps 批量调整图片大小 宏