06-图3 六度空间

​ “六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图所示。

​ “六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

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

输入格式:

​ 输入第1行给出两个正整数，分别表示社交网络图的结点数N（1<N≤103，表示人数）、边数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%

分析：

1. 输入图的顶点数Nv和边数Ne
2. 根据顶点数Nv创建零图Graph
3. 循环输入Ne条边，并插入到图Graph中
4. 遍历所有的顶点，查找层级6级以内的顶点数与总顶点数的百分比

关键算法BSF

1. 定义变量层级level,6级内的顶点数count，
2. 定义变量上一层级最后一个顶点last，当前遍历最后一个顶点tail，
3. 创建队列Q，并将当前结点S加入队列
4. 遍历队列至空
5. 将头元素移除出队列Q得到当前顶点V
6. 遍历当前顶点V所有相交的点
7. 如果V的邻接点W未被访问过，则加入队列Q，count加1，tail指向当前顶点，数组标记该顶点为true
8. 判断当前遍历的顶点是否为上一层遍历的最末顶点，如果是，层级level加1，last重新指向当前层的最后一个元素
9. 判断是否满6层，是则跳出所有遍历，返回访问过的顶点数count

编码：

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>

typedef int Vertex;
typedef struct QNode *PtrToQNode;

struct QNode {
    // 1.数组Data存放元素，循环存放实现循环队列
    Vertex *Data;
    // 2.设置队头front与rear队尾两个指针
    int front, rear;
    // 3.队列的最大容量
    int MaxSize;
};
typedef PtrToQNode Queue;

// 创建
Queue CreateQueue(int MaxSize) {
    Queue queue;
    // 1.动态申请队列Queue的空间
    queue = (Queue) malloc(sizeof(struct QNode));
    // 2.动态申请队列中数组Data的空间,
    queue->Data = (Vertex *) malloc(sizeof(Vertex) * MaxSize);
    // 3.最大长度为MaxSize
    queue->MaxSize = MaxSize;
    // 4.初始化队头front与队尾rear指针为0
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

// 是否为空
bool IsEmpty(Queue queue) {
    // 1. 队头front与队尾rear相等，则为空队列
    return queue->rear == queue->front;
}

// 是否已满
bool IsFull(Queue queue) {
    // 1.队尾rear+1模以容量等于队头front，则队列已满
    return (queue->rear + 1) % queue->MaxSize == queue->front;
}

// 入列 - 队尾rear
bool AddQ(Queue queue, Vertex item) {
    // 1. 判断队列是否已满
    if (IsFull(queue)) {
        printf("queue is full!");
        return false;
    }
    // 2.找到队列尾rear指针，在原指针加1后模以容量，以防在最队尾，重回队头
    queue->rear = (queue->rear + 1) % queue->MaxSize;
    // 3.在队列的数组Data的第rear个位置插入元素item
    queue->Data[queue->rear] = item;
    return true;
}

//出列 - 队头front
Vertex DeleteQ(Queue queue) {
    // 1.判断队列是否为空
    bool IsEmpty(Queue queue);
    if (IsEmpty(queue)) {
        printf("queue is empty!");
        return -1;
    }
    // 2.找到队头指针front,在原有指针上加1模以容量，如果在最末位，则重返数组第1位
    queue->front = (queue->front + 1) % queue->MaxSize;
    // 3.返回队头front指针的元素
    return queue->Data[queue->front];
}

#define MaxVertexNum 1001

//typedef int Vertex;// 用整形表示顶点
typedef int WeightType; // 权重
typedef char DataType;// 顶点数据，字符型
bool Visited[MaxVertexNum];

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
//边的定义
struct ENode {
    WeightType Weight;
    Vertex V1, V2;
};

typedef struct AdjVNode *PtrToAdjVNode;
// 邻接点的定义
struct AdjVNode {
    Vertex AdjV;//邻结点下标
    WeightType Weight;
    PtrToAdjVNode Next;
};

// 表头结点的定义
typedef struct Vnode {
    PtrToAdjVNode FirstEdge; // 边表头指针
    DataType Data; // 顶点的数据
} AdjList[MaxVertexNum]; // Vnode类型的数组，大小为MaxVertexNum个

typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv, Ne;
    AdjList G;// 邻接表，所有表头结点的数组 - 链表
};
typedef PtrToGNode LGraph;

LGraph CreateGraph(int VertexNum) {
    Vertex V;
    LGraph Graph;
    Graph = (LGraph) malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    // 从顶点1开始初始化，包含最末位的元素
    for (V = 1; V <= Graph->Nv; V++) {
        // 初始化各个结点的表头指针
        Graph->G[V].FirstEdge = NULL;
        // 初始化结点未被访问
        Visited[V] = false;
    }
    return Graph;
}

void InsertEdge(LGraph Graph, Edge E) {
    // 插入边<V1,V2>
    PtrToAdjVNode NewNode;
    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    // 将新的邻边结点V2插入V1的表头
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;

    NewNode = (PtrToAdjVNode) malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    // 将V1插入v2的表头
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}

// 广度优先搜索
int BFS(LGraph Graph, Vertex S) {
    // 1.定义变量层级level,6级内的顶点数count，
    int count, level = 0;
    Queue Q;
    // 2.定义变量上一层级最后一个顶点last，当前遍历最后一个顶点tail，
    Vertex V, last = S, tail;
    PtrToAdjVNode W;
    // 3.创建队列Q，并将当前结点S加入队列
    Q = CreateQueue(MaxVertexNum);
    Visited[S] = true;
    count = 1;
    AddQ(Q, S);
    // 4.遍历队列至空
    while (!IsEmpty(Q)) {
        // 5.将头元素移除出队列Q得到当前顶点V
        V = DeleteQ(Q);
        // 6.遍历当前顶点V所有相交的点
        for (W = Graph->G[V].FirstEdge; W; W = W->Next) {
            // 7.如果V的邻接点W未被访问过，则加入队列Q，count加1，tail指向当前顶点，
            // 数组标记该顶点为true
            if (!Visited[W->AdjV]) {
                Visited[W->AdjV] = true;
                AddQ(Q, W->AdjV);
                count++;
                tail = W->AdjV;
            }
        }
        // 8.判断当前遍历的顶点是否为上一层遍历的最末顶点，如果是，层级level加1，last重新指向当前层的最后一个元素
        if (V == last) {
            level++;
            last = tail;
        }
        // 9.判断是否满6层，是则跳出所有遍历，返回访问过的顶点数count
        if (level == 6)
            break;
    }
    return count;
}

int main() {
    int j, Nv, Ne, V1, V2, count;
    Edge E;
    Vertex i;
    // 1. 输入图的顶点数Nv和边数Ne
    scanf("%d %d", &Nv, &Ne);
    // 2.根据顶点数Nv创建零图Graph
    LGraph Graph = CreateGraph(Nv);
    // 3.循环输入Ne条边，并插入到图Graph中
    for (i = 0; i < Ne; i++) {
        scanf("%d %d", &V1, &V2);
        E = (Edge) malloc(sizeof(struct ENode));
        E->V1 = V1;
        E->V2 = V2;
        E->Weight = 1;
        InsertEdge(Graph, E);
    }
    // 4.遍历所有的顶点，查找层级6级以内的顶点数与总顶点数的百分比
    for (i = 1; i <= Nv; i++) {
        count = BFS(Graph, i);
        printf("%d: %.2f%\n", i, (float) count * 100 / (float) Nv);
        for (j = 0; j <= Nv; j++) {
            Visited[j] = false;
        }
    }
    return 0;
}

小结：

1. 图结构的选择，邻接矩阵还是邻接表？这里索性用邻接表；
2. 遍历某个顶点时，如何判断是否遍历完当前层，这里加了两个字段last和tail，用以标记上一层最后一个顶点和当前层遍历末位顶点；
3. 初始化图顶点，或是遍历所有顶点，需要注意上下限值，顶点从1开始，至第Nv个。