7-7 六度空间

预备知识

  • 六度空间理论:社交关系图中,任一两个节点总可以在六步之内相互关联。

题目描述

用深度优先搜索一幅图的每一个节点相对于其他所有节点满足六度空间理论的百分率。

思路

用上次写的邻接表表示的图,基本没什么多的操作,就是控制一下BFS的层数就结束了。

难点

没有难点

体会与感想

  • 在Clion中调试的时候,想看new出来的一片连续空间时,需要在new watch中添加命令
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    - c++想要控制输出固定位小数时,先用fixed固定好小数点,在用setprecesion控制保留几位小数
    - setprecesion本来是用来控制有效数字的

    # 源代码
    ```C++
    #include <iostream>
    #include <iomanip>

    using namespace std;

    struct node {
    int element;
    node * next;
    };

    struct Queue {
    int * queue;
    int head;
    int tail;
    int size;
    };

    node * createGraph(int n);
    void readGraph(node * G, int e);
    int BFSvalid(node * G, int i, int n);
    void deleteGraph(node * G, int n);

    int main(int argc, char const *argv[]) {
    freopen("D:\\SJTU\\Freshman Summer\\DS\\test.txt", "r", stdin);
    int n, m;cin >> n >> m;
    node * G = createGraph(n);
    readGraph(G,m);
    for (int i = 0; i < n; i++) {
    int valid = BFSvalid(G,i,n);
    double percentage = valid / (double)n;
    cout << i + 1 << ": ";
    cout << fixed << setprecision(2) << 100 * percentage;
    cout << '%' << endl;
    }
    deleteGraph(G,n);
    return 0;
    }

    int findMin(node * ptr, bool * visited) {
    int min;
    while (ptr->next && visited[ptr->next->element])
    {
    ptr = ptr->next;
    }
    if (ptr->next==NULL) return -1;
    else min = ptr->next->element;
    ptr = ptr->next->next;
    while (ptr) {
    if (ptr->element<min && !visited[ptr->element]) {
    min = ptr->element;
    }
    ptr = ptr->next;
    }
    return min;
    }

    bool remains(node * ptr, bool * visited) {
    while (ptr->next) {
    if (!visited[ptr->next->element]) {
    return true;
    }
    ptr = ptr->next;
    }
    return false;
    }

    Queue * creatQueue(int n) {
    Queue * q = new Queue;
    q->size = n;
    q->queue = new int [n];
    q->head = 0;
    q->tail = -1;
    return q;
    }

    void deleteQueue(Queue * q) {
    delete [] q->queue;
    delete q;
    }

    void enQueue(Queue * q, int element) {
    q->queue[++q->tail] = element;
    }

    int deQueue(Queue * q) {
    return q->queue[q->head++];
    }

    void push(Queue * q, node * ptr, bool * visited, int * cnt) {
    while (remains(ptr,visited)) {
    int min = findMin(ptr,visited);
    if (min==-1) return;
    enQueue(q,min);
    (*cnt)++;
    visited[min] = true;
    }
    }

    int BFSvalid(node * G, int start, int n) { //return the number of valid nodes
    Queue * q = creatQueue(n); //of the BFS of node i
    bool * visited = new bool [n];
    for (int i = 0; i < n; i++) {
    visited[i] = false;
    }
    int cnt = 1, degree = 6;
    enQueue(q,start);
    visited[start] = true;
    int sentry = q->tail;
    while (q->head!=q->tail+1 && degree>0) {
    while (q->head!=sentry+1) {
    int popelement = deQueue(q);
    push(q,&G[popelement],visited,&cnt);
    }
    sentry = q->tail;
    degree--;
    }

    delete [] visited;
    deleteQueue(q);
    return cnt;
    }

    void deleteGraph(node * G, int n) {
    for (int i = 0; i < n; i++) {
    node * ptr = G[i].next;
    while (ptr) {
    node * temp = ptr->next;
    delete ptr;
    ptr = temp;
    }
    }
    delete [] G;
    }

    void insertEdge(node * G, int i, int j) {
    node * ptr = &G[i];
    while (ptr->next) {
    ptr = ptr->next;
    }
    ptr->next = new node;
    ptr = ptr->next;
    ptr->element = j;
    ptr->next = NULL;

    ptr = &G[j];
    while (ptr->next) {
    ptr = ptr->next;
    }
    ptr->next = new node;
    ptr = ptr->next;
    ptr->element = i;
    ptr->next = NULL;
    }

    void readGraph(node * G, int e) {
    int vi, vj;
    for (int i = 0; i < e; i++) {
    cin >> vi >> vj;
    insertEdge(G, vi-1, vj-1);
    }
    }

    node * createGraph(int n) {
    node * G = new node [n];
    for (int i = 0; i < n; i++) {
    G[i].element = i;
    G[i].next = NULL;
    }
    return G;
    }