NOJ数据结构020——基于图的广度优先搜索策略

一时失言乱红尘 2023-01-23 01:05 22阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]

本题要求采用邻接表来表示图，图的广度优先搜索类似于树的层序遍历，本质上来说是树的按层次遍历的推广，其中需要用到队列。

代码：

#include <stdio.h>
    #include <stdlib.h>
    #define MAX_VERTEX_NUM 20//最多顶点数
    
    int visited[MAX_VERTEX_NUM];//遍历标志数组
    
    typedef enum {
         DG, UDG, DN, UDN }GraphKind;
    
    typedef struct ArcNode {
        
    	int adjvex;             //弧指向的顶点
    	struct ArcNode* nextarc;//下一个弧
    }ArcNode;
    
    typedef struct {
        
    	int data;         //顶点数据
    	ArcNode* firstarc;//第一条弧
    }VertexNode;
    
    typedef struct {
        
    	VertexNode vertex[MAX_VERTEX_NUM];
    	int num_ver, num_arc;//图的顶点数、弧数
    	GraphKind kind;      //图的种类
    }AdjList;
    
    typedef struct {
        
    	int data[MAX_VERTEX_NUM];
    	int front;//队首
    	int last; //队尾
    	int len;  //队长
    }Queue;
    
    int Search(AdjList A, int v);             //找到顶点对应位置
    void CreateList(AdjList* A, int n, int m);//创建图
    void InitQueue(Queue* q);                //初始化队列
    void EnterQueue(Queue* q, int n);        //入队
    void DeleteQueue(Queue* q, int *tmp);    //出队
    int BFS(AdjList A, int loc1, int loc2);  //广度优先搜索
    
    int main()
    {
        
    	int n, m;
    	scanf("%d%d", &n, &m);
    	AdjList A;
    	CreateList(&A, n, m);
    	for (int i = 0; i < A.num_ver; i++) {
        
    		visited[i] = 0;
    	}
    	int v1, v2;
    	scanf("%d%d", &v1, &v2);
    	if(BFS(A, Search(A, v1), Search(A, v2))) {
        
            printf("yes");
    	}
    	else {
        
            printf("no");
    	}
    	return 0;
    }
    
    int Search(AdjList A, int v)
    {
           //找到顶点对应位置
    	for (int i = 0; i < A.num_ver; i++) {
        
    		if (A.vertex[i].data == v) {
        
    			return i;
    		}
    	}
    	return -1;
    }
    
    void CreateList(AdjList* A, int n, int m)
    {
           //创建图
    	if (A == NULL) {
        
    		return;
    	}
    	A->num_ver = n;
    	A->num_arc = m;
    	A->kind = DG;
    	for (int i = 0; i < A->num_ver; i++) {
        
    		scanf("%d", &A->vertex[i].data);
    		A->vertex[i].firstarc = NULL;
    	}
    	int tmp1, tmp2, loc;
    	for (int i = 0; i < A->num_arc; i++) {
        
    		scanf("%d%d", &tmp1, &tmp2);
    		ArcNode* tmp;
    		tmp = (ArcNode*)malloc(sizeof(ArcNode));
    		if (tmp == NULL) {
        
    			return;
    		}
    		tmp->adjvex = tmp2;
    		loc = Search(*A, tmp1);
    		tmp->nextarc = A->vertex[loc].firstarc;
    		A->vertex[loc].firstarc = tmp;
    	}
    }
    
    void InitQueue(Queue* q)
    {
           //初始化队列
    	q->front = 0;
    	q->last = -1;
    	q->len = 0;
    }
    
    void EnterQueue(Queue *q, int n)
    {
           //入队
    	if (q->len > MAX_VERTEX_NUM) {
        
    		return;
    	}
    	q->last = (q->last + 1) % MAX_VERTEX_NUM;
    	q->data[q->last] = n;
    	q->len++;
    }
    
    void DeleteQueue(Queue* q, int *tmp)
    {
           //出队
    	if (q->len == 0) {
        
    		return;
    	}
    	*tmp = q->data[q->front];
    	q->front = (q->front + 1) % MAX_VERTEX_NUM;
    	q->len--;
    }
    
    int BFS(AdjList A, int loc1, int loc2)
    {
           //广度优先搜索
    	Queue *q;
        q = (Queue*)malloc(sizeof(Queue));
    	InitQueue(q);
    	visited[loc1] = 1;
    	EnterQueue(q, loc1);
    	if (loc1 == loc2) {
        
    		return 1;
    	}
        int del, loc;
    	while (q ->len != 0) {
        
    		DeleteQueue(q, &del);
    		ArcNode *tmp;
    		tmp = A.vertex[del].firstarc;
    		loc = Search(A, tmp->adjvex);
    		while (tmp != NULL) {
        
    			loc = Search(A, tmp->adjvex);
    			if (visited[loc] != 1) {
        
                    if (loc == loc2) {
        
                        return 1;
                    }
                    visited[loc] = 1;
                    EnterQueue(q, loc);
                    tmp = tmp->nextarc;
    			}
    		}
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221020/aae14ffdc5044a0a8495d95ad4b6d6b2.png