首页 > 代码库 > network of emergency contacts---BFS

network of emergency contacts---BFS

2024-09-09 23:20:12   219人阅读

本题目的主要难点在如何寻找最后一层的数，利用book标记数组可以很好的解决问题。book=0的时候说明没被连接过，若要连接时，将book等于上一层book+1.

需要注意的是，对于图的问题建立邻接矩阵是非常省时间的方法。类似这个道题，我没有用邻接矩阵，因此每次都要进入150的for循环。但是如果用矩阵，最多则是每次100的循环。这样对于n*n*n.....来说则会剩下很多时间。

#include<stdio.h>
#include<stdlib.h>
typedef struct{
    int a[300];
    int rear;
    int head;
}queue;
queue q;
int A[150],B[150];
int book[300];
int test(int data[300],int startNum);
void build(int data[300]){
    for(int i=0;i<300;i++)
        data[i]=rand()%100+1;
}
void main(){
    //freopen("intput.txt","r",stdin);
    int data[300];
    for(int l=0;l<10;l++){
        build(data);
        printf("%d\n",test(data,data[0]));
    }
}
int test(int data[300],int startNum){
    for(int i=0;i<300;i++)
        book[i]=0;
    for(int i=0,j=0;i<299;j++){　　　　　　　　　　//将数据分为两个数组中A表示边的出发点，B表示边的终点
        A[j]=data[i];
        B[j]=data[i+1];
        i=i+2;
    }
    q.rear=0;
    q.head=0;
    q.a[q.rear++]=startNum;
    book[startNum]=1;
    while(q.head<q.rear){
        int temp=q.a[q.head++];
        for(int i=0;i<150;i++){
            if(A[i]==temp&&book[B[i]]==0){
                q.a[q.rear++]=B[i];
                book[B[i]]=book[A[i]]+1;　　　　　//标记层数
            }
        }
    }
    int c=0;
    int max=0;
    for(int i=0;i<=299;i++){　　　　　　　　　　　　//寻找最大层数
        if(c<book[i]){
            c=book[i];
        }
    }
    for(int i=299;i>=0;i--){　　　　　　　　　　　　//寻找最大层数总最大值
        if(book[i]==c){
            max=i;
            break;
        }
    }
    return max;
}

 

network of emergency contacts---BFS


联系
我们