六度空间(C语言)

Global variables.h(全局变量的声明):

//存放全局变量的声明,注意加extern

extern int Graph[100][100];     //邻接矩阵 
extern int V, W;                //点和边
extern int visited[100];        //判断是否访问 

Global variables.cpp(全局变量的设置):

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"Global variables.h"

//设置全局变量

int Graph[100][100];     //邻接矩阵 
int V, W;                //点和边
int visited[100];        //判断是否访问 

head.h(头文件):

void BuildGraph();
void SDS();
int BFS(int v);

head.cpp(头文件中函数的实现):

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"head.h"
#include"Global variables.h"


void BuildGraph() {              //建立图
	int i, j, n1, n2;

	for (i = 0; i < V; i++) {   //初始化
		for (j = 0; j < V; j++) {
			Graph[i][j] = 0;
		}
	}

	for (i = 0; i < W; i++) {   //建立图
		scanf("%d%d", &n1, &n2);
		Graph[n1][n2] = 1;
		Graph[n2][n1] = 1;
	}
}

void SDS() {
	int i, j;
	float rate;
	for (i = 0; i < V; i++) {

		for (j = 0; j < V; j++)
			visited[j] = 0;

		rate = (float)BFS(i) / V;
		printf("%d: %.2f%%\n", i + 1, rate * 100);
	}
}

int BFS(int v) {
	int cnt = 1, level = 0, last = v, i, n, tail;
	int que[1000] = {}, rear, front;    //模拟队列 
	rear = front = 0;
	visited[v] = 1;
	que[rear] = v;
	rear++;
	while (rear > front) {
		n = que[front];
		front++;
		for (i = 0; i < V; i++) {
			if (visited[i] == 0 && Graph[n + 1][i + 1] == 1) {
				visited[i] = 1;
				que[rear] = i;
				rear++;
				cnt++;
				tail = i;
			}
		}
		if (n == last) {
			level++;
			last = tail;
		}
		if (level == 6) {
			break;
		}
	}
	return cnt;
}

ceshi1.cpp(主函数):

#define _CRT_SECURE_NO_WARNINGS    //六度空间
#include<stdio.h>
#include<stdlib.h>
#include"head.h"
#include"Global variables.h"


int main() { 
	scanf("%d%d", &V, &W);
	BuildGraph();
	SDS();
	return 0;
}

测试结果:

六度空间(C语言)

 

上一篇:分层图池化:Hierarchical Graph Representation Learning with Differentiable Pooling


下一篇:AntV G6鼠标移入、单击、双击节点,获取节点信息