저장 성 빅 데이터 구조 연습 문제 노트: 06 - 그림 3 6 도 공간 (30 분)

06 - 그림 3 6 도 공간 (30 분)
원제
'6 도 공간' 이론 은 '6 도 분리 (Six Degrees of Separation)' 이론 이 라 고도 부른다.이 이론 은 "당신 과 어떤 낯 선 사람 사이 에 간격 이 있 는 사람 은 여섯 명 을 넘 지 않 는 다. 즉, 최대 다섯 명 을 통 해 어떤 낯 선 사람 도 알 수 있다" 고 통속 적 으로 논술 할 수 있다. 그림 1 참조.
그림 1 6 도 공간 설명도 '6 도 공간' 이론 은 광범 위 한 인정 을 받 았 지만 점점 더 많은 응용 을 얻 고 있다.그러나 수 십 년 간 이 이론 이 많은 사회학 자 들 이 추구 하 는 목표 라 는 것 을 검증 하려 고 노력 해 왔 다.그러나 역사적 인 이유 로 이런 연 구 는 한계 와 어려움 이 크다.현대인 의 연락 은 주로 전화, 문자, 위 챗 과 인터넷 에서 실시 간 통신 등 도구 에 의존 하면 서 소 셜 네트워크 관 계 를 나 타 낼 수 있 는 데이터 가 '6 도 공간' 이론의 검증 을 가능 하 게 만 들 었 다.
만약 에 소 셜 네트워크 서 비 스 를 제공한다 면 모든 노드 에 대해 '6 도 공간' 이론 에 부합 되 는 결점 이 결점 총수 의 백분율 을 계산 하 십시오.
입력 형식: 첫 번 째 줄 을 입력 하여 두 개의 정 수 를 제시 하고 각각 소 셜 네트워크 그림 의 결산 포인트 N (1 3, 인원 표시), 변 수 M (≤ 33×N, 사교 관계 수 를 나타 낸다).그 다음 에 M 줄 은 M 개의 변 에 대응 하고 각 줄 은 한 쌍 의 정 수 를 제시 하 는데 각각 이 변 이 직접 연 결 된 두 개의 결점 의 번호 (노드 는 1 에서 N 번호) 이다.
출력 형식: 각 노드 의 출력 과 이 노드 의 거리 가 6 을 초과 하지 않 는 노드 수 는 노드 총수 의 백분율 을 차지 하고 소수점 뒤의 2 자리 까지 정확 합 니 다.각 노드 마다 한 줄 을 출력 합 니 다. 형식 은 '노드 번호: (빈 칸) 백분율%' 입 니 다.
입력 예시:

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

출력 예시:

1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%

분석 하 다.
인접 표를 만 든 다음 에 BFS 방식 으로 6 층 을 옮 겨 다 니 면 몇 개의 노드 를 찾 을 수 있 는 지 기록 하고 비례 를 계산 한 후에 출력 할 수 있 습 니 다.관건 은 6 층 이 몇 번 을 옮 겨 다 니 는 지 기록 하 는 것 입 니 다. 우 리 는 이때 세 가지 변 수 를 도입 해 야 합 니 다. last 이 층 의 마지막 방문 노드 tail 는 매번 에 변 하 는 꼬리 노드 입 니 다. 방문 할 때마다 추진 대열 의 노드 의 값 을 이 곳 으로 옮 깁 니 다 level. BFS 가 몇 층 구간 에 옮 겨 다 니 는 것 을 기록 합 니 다. 매번 에 튕 겨 나 오 는 노드 와 last노드 와 동시에 이 층 이 이미 끝 났 고 다음 층 에 들 어 갔다 는 것 을 증명 한다.
이후 level = 6 시, 순환 이 끝나 고 되 돌아 오기 count주요 난점 은 이 세 변 수 를 통 해 층 수 를 어떻게 파악 하 느 냐 하 는 것 이다.다른 부분 과 구조 도 는 별 차이 가 없 으 며 인접 행렬 로 도 마찬가지다.
구체 적 인 코드 구현

#include 
#include 
#include 
#define MAX_VERTEX 10005

typedef int vertex;
typedef struct Node *AdjList;

struct Node{
    vertex Adjv;
    AdjList next;
};

AdjList G[MAX_VERTEX];
bool visit[MAX_VERTEX];
int N,M;
using namespace std;

//   visit  
void initVisit()
{
    for(int i=1;i<=N;i++)
        visit[i] = false;
}

void init()
{
    vertex v1,v2;
    AdjList NewNode;
    cin>>N>>M;
    //     1--N-1
    for(int i=1; i<=N ; i++){
        G[i] = (AdjList)malloc(sizeof(struct Node));
        G[i]->Adjv = i;
        G[i]->next = NULL;
    }
    //    
    for(int i=0;i<M;i++){
        cin>>v1>>v2;
        //    ，v2 v1 
        NewNode = (AdjList)malloc(sizeof(struct Node));
        NewNode->Adjv = v2;
        NewNode->next = G[v1]->next;
        G[v1]->next = NewNode;
        //    ，v1 v2 
        NewNode = (AdjList)malloc(sizeof(struct Node));
        NewNode->Adjv = v1;
        NewNode->next = G[v2]->next;
        G[v2]->next = NewNode;
    }
}

int BFS(vertex v)
{
    queue<vertex> q;
    vertex temp;
    int level = 0;
    int last = v;   //           
    int tail = v;   //        
    AdjList node;
    visit[v] = true;
    int count = 1;
    q.push(v);
    while(!q.empty()){
        temp = q.front();
        q.pop();
        node = G[temp]->next;
        while(node){
            if(!visit[node->Adjv]){
                visit[node->Adjv] = true;
                q.push(node->Adjv);
                count++;
                tail = node->Adjv;
            }
            node = node->next;
        }
        if(temp == last){
            level++;
            last = tail;
        }
        if(level == 6)
            break;
    }
    return count;
}

void print(double result,int i)
{
    printf("%d: %.2f%%
",i,result);
}

void SDS()
{
    int count;
    for(int i=1;i<=N;i++){
        initVisit();
        count = BFS(i);
        print((100.0 * count)/N,i);
    }
}

int main()
{
    init();
    SDS();
    return 0;
}