05-图3. 六度空间 (30)

Posted on   |   In   |  

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图6.4所示。
图6.4 六度空间示意图
“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式说明：

输入第1行给出两个正整数，分别表示社交网络图的结点数N （1<N<=104，表示人数）、边数M（<=33*N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。

输出格式说明：

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

样例输入与输出：

序号 输入 输出
1 10 9 1: 70.00%
1 2 2: 80.00%
2 3 3: 90.00%
3 4 4: 100.00%
4 5 5: 100.00%
5 6 6: 100.00%
6 7 7: 100.00%
7 8 8: 90.00%
8 9 9: 80.00%
9 10 10: 70.00%
2 10 8 1: 70.00%
1 2 2: 80.00%
2 3 3: 80.00%
3 4 4: 80.00%
4 5 5: 80.00%
5 6 6: 80.00%
6 7 7: 80.00%
7 8 8: 70.00%
9 10 9: 20.00%
10: 20.00%
3 11 10 1: 100.00%
1 2 2: 90.91%
1 3 3: 90.91%
1 4 4: 100.00%
4 5 5: 100.00%
6 5 6: 100.00%
6 7 7: 100.00%
6 8 8: 100.00%
8 9 9: 100.00%
8 10 10: 100.00%
10 11 11: 81.82%
4 2 1 1: 100.00%
1 2 2: 100.00%

代码如下：

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
#include<iostream>
#include<vector>
#include<queue>
#include<iomanip>

using namespace std;

class Graph
{
public:

    Graph(int vertexNum, int edgeNum):vertexNum(vertexNum), edgeNum(edgeNum)
    {
        m_graph.resize(vertexNum + 1);          //initialize values
        visited.resize(vertexNum + 1, 0);
        countNum = 0;
        int startVertex = 0, endVertex = 0;
        for(int i = 0; i < edgeNum; ++i)    //create graph
        {
            cin >> startVertex >> endVertex;
            m_graph[startVertex].push_back(endVertex);
            m_graph[endVertex].push_back(startVertex);
        }
    };
    void Traversal();
    void DFS(int index);
    void BFS(int index);
    int CountVisitedNum();
private:
    int vertexNum;
    int edgeNum;
    int countNum;       // the number of level
    vector<int> visited;
    vector<vector<int> > m_graph;
};

void Graph::Traversal()
{
    for(int i = 1; i < vertexNum + 1; ++i)      //for each element , traversal
    {
        BFS(i);         //DFS(i);
        countNum = 0;
        int visitedNum = CountVisitedNum();     //compute visited element number
        cout << i << ": ";
        cout << fixed << setprecision(2) << (float)visitedNum  / (float)vertexNum * 100.0 << "%" << endl;
    }
}

void Graph::DFS(int index)
{
    if(!visited[index])
    {
        visited[index] = 1;
        if(6 == countNum)   //µ½´ïµÚÁù²ã
        {
            return;
        }
        for(int i = 0; i < m_graph[index].size(); ++i)
        {
            ++countNum;
            DFS(m_graph[index][i]);
            --countNum;
        }
    }
}

void Graph::BFS(int index)
{
    queue<int> queueGraph;
    queueGraph.push(index);
    int level = 0;
    int last = index;    //标记到达这一层的末尾元素
    int num = 0;        //num 表示这一层元素有多少个
    while(!queueGraph.empty())
    {
        if(!visited[queueGraph.front()])
        {
            visited[queueGraph.front()] = 1;

            for(int i = 0; i < m_graph[queueGraph.front()].size(); ++i)
            {
                queueGraph.push(m_graph[queueGraph.front()][i]);
            }
        }
        if(last == queueGraph.front() && !num)  //当这一层元素到达末尾且这一层元素即将遍历完时，更新
            //为什么用两个条件一起判断呢，因为在这一层元素未遍历完之前，可能前面会有和末尾元素相同的值，所以额外加一个num值为0作为辅助判断
        {
            ++level;
            num = queueGraph.size() - 1;
            last = queueGraph.back();
        }
        --num;
        if(7 == level)  //我将初始元素作为第一层，所以等于7，break
        {
            break;
        }
        queueGraph.pop();
    }
}
int Graph::CountVisitedNum()    //计算他所能访问的元素个数，顺便将visited恢复到初始状态
{
    int num = 0;
    for(int i = 1; i < vertexNum + 1; ++i)
    {
        if(visited[i])
        {
            ++num;
            visited[i] = 0;
        }
    }
    return num;
}
int main()
{
    int N = 0, M = 0;
    cin >> N >> M;
    Graph graph(N, M);
    graph.Traversal();
    return 0;
}

刚开始用DFS写的，但是写完之后，测试点4过不了，但是速度快，DFS测试点4我的用时只有20ms，虽然没过，但是BFS就是其10倍还不止，而且我现在还是没有把DFS的bug修复好。
最后一个测试数据，问陈越老师，陈越老师说是1000个点组成一个环，然后前面64个点一次与后面500个点相连，也就是1000个点，1000+64*500=33000个边。根据这个数据，我知道bug出在哪里，后面就看了一下陈越老师的解法，看完之后只知道要做个标记，具体给忘了，然后就自己想想，写了个四不像的，核心思想应该跟陈越老师的是一样的。

做完这道题，PAT成绩终于进第二页了，争取开学之前进首页。
测试数据如下：

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 308 18/18
1 答案正确 1 308 3/3
2 答案正确 1 180 3/3
3 答案正确 1 180 3/3
4 答案正确 224 1056 3/3

在看陈越老师讲最短路径又提到了BFS算法，发现这道题当时解法有点耗时，因为我把重复元素加进来了，如果把visited位置换掉，耗时更短。
代码如下：

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
#include<iostream>
#include<vector>
#include<queue>
#include<iomanip>

using namespace std;

class Graph
{
public:

    Graph(int vertexNum, int edgeNum):vertexNum(vertexNum), edgeNum(edgeNum)
    {
        m_graph.resize(vertexNum + 1);          //initialize values
        visited.resize(vertexNum + 1, 0);
        countNum = 0;
        int startVertex = 0, endVertex = 0;
        for(int i = 0; i < edgeNum; ++i)    //create graph
        {
            cin >> startVertex >> endVertex;
            m_graph[startVertex].push_back(endVertex);
            m_graph[endVertex].push_back(startVertex);
        }
    };
    void Traversal();
    void DFS(int index);
    void BFS(int index);
    int CountVisitedNum();
private:
    int vertexNum;
    int edgeNum;
    int countNum;       // the number of level
    vector<int> visited;
    vector<vector<int> > m_graph;
};

void Graph::Traversal()
{
    for(int i = 1; i < vertexNum + 1; ++i)      //for each element , traversal
    {
        BFS(i);         
        countNum = 0;
        int visitedNum = CountVisitedNum();     //compute visited element number
        cout << i << ": ";
        cout << fixed << setprecision(2) << (float)visitedNum  / (float)vertexNum * 100.0 << "%" << endl;
    }
}

void Graph::BFS(int index)
{
    visited[index] = 1;
    queue<int> queueGraph;
    queueGraph.push(index);
    int level = 0;
    int last = index;    //标记到达这一层的末尾元素
    int num = 0;        //num 表示这一层元素有多少个
    while(!queueGraph.empty())
    {
        for(int i = 0; i < m_graph[queueGraph.front()].size(); ++i)
        {
            if(!visited[m_graph[queueGraph.front()][i]])		//判断是否被访问过，被访问过，就不加进队列
			//之前那种判断方式是把if判断放在外面，这样虽然那个结点没被访问过，但是其邻接点可能被访问过，所以当时后面加了num来计数辅助判断，这样因为没有重复元素，所以不需要num辅助判断了
            {
                visited[m_graph[queueGraph.front()][i]] = 1;
                queueGraph.push(m_graph[queueGraph.front()][i]);
            }
        }
        if(last == queueGraph.front())
        {
            ++level;
            last = queueGraph.back();
        }
        if(6 == level)			//这里的level改成6了，
        {
            break;
        }
        queueGraph.pop();
    }
}
int Graph::CountVisitedNum()    //计算他所能访问的元素个数，顺便将visited恢复到初始状态
{
    int num = 0;
    for(int i = 1; i < vertexNum + 1; ++i)
    {
        if(visited[i])
        {
            ++num;
            visited[i] = 0;
        }
    }
    return num;
}
int main()
{
    int N = 0, M = 0;
    cin >> N >> M;
    Graph graph(N, M);
    graph.Traversal();
    return 0;
}

代码中if(6 == level)改为6，而不是原来的7，经过的我的思考，我认为原因是这样的：之前是只有当前结点没被访问过，才会将执行visited[m_graph[queueGraph.front()][i]] = 1;，并且将当前的结点push进队列时，并没有将当前push进去的结点的visited设为1；
而在这里，不需要判断当前结点是否被访问过，就会把当前结点的所有未被访问的邻接结点的visited设为1，并push进队列，相对于之前的那种做法，他向前多做了一步把实际上还未访问的结点的visited设为1，而在我的代码中统计结点是否被访问恰好就是看visited的值是否为1，为1代表访问了，算入累计值，所以这里到6就要停下了，因为他提前就把第六层的结点的visited设为1了，就不需要在访问第六层结点了。
个人理解，如果有误，欢迎指正！

测试结果：

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 308 18/18
1 答案正确 1 308 3/3
2 答案正确 1 308 3/3
3 答案正确 1 308 3/3
4 答案正确 64 820 3/3