06-圖3 六度空間 (30分)(資料結構)(C語言實作)(鄰接連結清單)

“六度空間”理論又稱作“六度分隔（Six Degrees of Separation）”理論。這個理論可以通俗地闡述為：“你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過五個人你就能夠認識任何一個陌生人。”如圖1所示。

圖1 六度空間示意圖

“六度空間”理論雖然得到廣泛的認同，并且正在得到越來越多的應用。但是數十年來，試圖驗證這個理論始終是許多社會學家努力追求的目标。然而由于曆史的原因，這樣的研究具有太大的局限性和困難。随着當代人的聯絡主要依賴于電話、短信、微信以及網際網路上即時通信等工具，能夠展現社交網絡關系的一手資料已經逐漸使得“六度空間”理論的驗證成為可能。

假如給你一個社交網絡圖，請你對每個節點計算符合“六度空間”理論的結點占結點總數的百分比。

輸入格式:

輸入第1行給出兩個正整數，分别表示社交網絡圖的結點數N（1<N≤10

​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%
           

六度空間想必大家都有所了解，這道題目我們需要用鄰接連結清單實作。首先給出我們需要定義的結構體

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 10005

typedef struct VNode* Vertex;
struct VNode {
	Vertex Next;
	int V;
};

typedef struct LNode {
	Vertex FirstEdge;
	
}List[MAXN];//數組指針

typedef struct GNode* Graph;
struct GNode {
	int Nv,Ne;//頂點，邊
	List Head;
};

Graph G;
int visit[MAXN];
           

首先我們來看函數主入口

int main()
{
	int i;
	int v,w;
	G = (Graph)malloc(sizeof(struct GNode));
	scanf("%d%d",&G->Nv,&G->Ne);
	for(i=1;i<=G->Nv;i++)
		G->Head[i].FirstEdge = NULL;//創造輸入的頂點那麼多的頭指針
	for(i=1;i<=G->Ne;i++) {
		scanf("%d%d",&v,&w);
		Insert(v,w);//插入邊
	}
	for(i=1;i<=G->Nv;i++) {
		memset(visit,0,sizeof(visit));
		BFS(i);
	}
	return 0;
	
}
           

插入邊函數

void Insert(int v,int w) {
	Vertex NewNode = (Vertex)malloc(sizeof(struct VNode));
	NewNode->V = v;
	NewNode->Next = G->Head[w].FirstEdge;
	G->Head[w].FirstEdge = NewNode;
	
	NewNode = (Vertex) malloc(sizeof(struct VNode));
	NewNode->V = w;
	NewNode->Next = G->Head[v].FirstEdge;
	G->Head[v].FirstEdge = NewNode;
}
           

因為是找到一個節點就把這個節點的附近點都存入，是以用廣度優先周遊。

void BFS(int s) {
	int Q[MAXN],front = 0,rear = 0,v,i;
	int tail,last = s,cnt = 0,level = 0,kase = s;
	Vertex p;
	double perc;
	Q[++rear] = s;//入隊
	visit[s] = 1;//這個節點已通路
	cnt ++;//計算這個節點一共有多少聯系
	while(rear!=front) {
		v = Q[++front];//出隊
		for(p = G->Head[v].FirstEdge;p;p = p->Next)//對這個節點進行循環 
		{
			if(!visit[p->V]) //某個節點沒被通路過
			{
				Q[++rear] = p->V;//入隊
				visit[p->V] =1;//已通路了
				cnt ++;
				tail = p->V;//tail是指每次存的那個元素
			}
		}
		if(v==last) //如果出隊的這個元素等于我們設定的last
		{
			level ++;//進入到下一層了
			last = tail;//last指向上一層的最後一個元素
		}
		if(level == 6) break;//到第六層了
	}
	perc = ((double)cnt)/((double)G->Nv) * 100;//計算百分比
	printf("%d: %.2lf%%\n",kase,perc);
}
           

總代碼如下

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 10005

typedef struct VNode* Vertex;
struct VNode {
	Vertex Next;
	int V;
};

typedef struct LNode {
	Vertex FirstEdge;
	
}List[MAXN];

typedef struct GNode* Graph;
struct GNode {
	int Nv,Ne;
	List Head;
};

Graph G;


void Insert(int v,int w) {
	Vertex NewNode = (Vertex)malloc(sizeof(struct VNode));
	NewNode->V = v;
	NewNode->Next = G->Head[w].FirstEdge;
	G->Head[w].FirstEdge = NewNode;
	
	NewNode = (Vertex) malloc(sizeof(struct VNode));
	NewNode->V = w;
	NewNode->Next = G->Head[v].FirstEdge;
	G->Head[v].FirstEdge = NewNode;
}

int visit[MAXN];

void BFS(int s) {
	int Q[MAXN],front = 0,rear = 0,v,i;
	int tail,last = s,cnt = 0,level = 0,kase = s;
	Vertex p;
	double perc;
	Q[++rear] = s;
	visit[s] = 1;
	cnt ++;
	while(rear!=front) {
		v = Q[++front];
		for(p = G->Head[v].FirstEdge;p;p = p->Next) {
			if(!visit[p->V]) {
				Q[++rear] = p->V;
				visit[p->V] =1;
				cnt ++;
				tail = p->V;
			}
		}
		if(v==last) {
			level ++;
			last = tail;
		}
		if(level == 6) break;
	}
	perc = ((double)cnt)/((double)G->Nv) * 100;
	printf("%d: %.2lf%%\n",kase,perc);
}
int main()
{
	int i;
	int v,w;
	G = (Graph)malloc(sizeof(struct GNode));
	scanf("%d%d",&G->Nv,&G->Ne);
	for(i=1;i<=G->Nv;i++)
		G->Head[i].FirstEdge = NULL;
	for(i=1;i<=G->Ne;i++) {
		scanf("%d%d",&v,&w);
		Insert(v,w);
	}
	for(i=1;i<=G->Nv;i++) {
		memset(visit,0,sizeof(visit));
		BFS(i);
	}
	return 0;
	
}