MOOC 06 - Figure 3 six dimensional space

The "six degree space" theory is also known as the "Six Degrees of Separation" theory. This theory can be popularly stated as: "there will be no more than six people between you and any stranger, that is, you can know any stranger through up to five people." As shown in Figure 1:

Although the "six dimensional space" theory has been widely recognized, it is being used more and more. But for decades, trying to verify this theory has always been the goal of many sociologists. However, due to historical reasons, such research has too many limitations and difficulties. As the contact of contemporary people mainly depends on tools such as telephone, SMS, wechat and instant messaging on the Internet, the first-hand data that can reflect the relationship of social networks has gradually made the verification of the "six dimensional space" theory possible.

If you are given a social network diagram, please calculate the percentage of nodes that comply with the "six dimensional space" theory in the total number of nodes for each node.

Input format:

Input the first line to give two positive integers, which respectively represent the number of nodes n (1 < n ≤ 103, indicating the number of people) and the number of edges M (≤ 33) of the social network graph × N. Indicates the social correlation coefficient). The subsequent M lines correspond to M edges, and each line gives a pair of positive integers, which are the numbers of the two nodes directly connected to the edge (nodes are numbered from 1 to n).

Output format:

The exact distance between each node and the total number of decimal points should not exceed 2. One line is output for each nodal point in the format of "node number: (space) percentage%".

Input sample:

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

Output example:

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%

Summary:

This is a BFS exercise of a graph. You should master the BFs of the graph skillfully. The difficulty is how to traverse only the sixth layer; The method given by the teacher is very ingenious. It is a clever little routine. There are two variables: last and Tail. Last is the last of each layer, and Tail is the one that has recently entered the queue. When the value of out of the queue = = last, it indicates that the traversal of this layer is completed, and last = Tail;

The overall difficulty is not big. I practice hard and can't make a little progress every day. I hope you can encourage me together;

A little knowledge: in C language,% is a special character. If you want to print it, you need to use "%%"

printf("%%");

Complete code (I'm used to pointer with *, so I don't define pointer as graph like the teacher)

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

typedef int Vertex; //vertex

typedef struct _Edge{ //edge
	Vertex V1,V2;
}Edge;

typedef struct _AdjV AdjV; //Adjacency point
struct _AdjV{
	Vertex V;
	AdjV* Next;
};

typedef struct _LGraph{ //Graph represented by adjacency table
	int Nv;
	int Ne;
	AdjV** G;  //Adjacency table; G is a pointer array, the size is determined according to Nv, and each element of the array is a pointer AdjV*
}LGraph;

typedef struct _Queue{ //queue
	Vertex* QueArray;
	int front;
	int rear;
}Queue;

LGraph* BuildGraph( );

void InsertEdge( LGraph* Graph,Edge E );

void SixDegrees( LGraph* Graph );

int BFS( LGraph* Graph,Vertex V );

Queue* CreateQ( int Nv );

void AddQ( Queue* Q,Vertex V );

Vertex DeleteQ( Queue* Q );

bool IsEmpty( Queue* Q );

void InitilizeVisited( bool Visited[],int Nv );

int NumTrueOfVisited( bool Visited[],int Nv );

void FreeGraph( LGraph* Graph );

int main()
{
	LGraph* Graph = BuildGraph( );
	
	SixDegrees( Graph );
	
	FreeGraph( Graph );
	
	return 0;
}

//Build a map according to the input data
LGraph* BuildGraph( )
{
	int N,M;
	scanf("%d %d",&N,&M);
	
	LGraph* Graph = (LGraph*)malloc(sizeof(LGraph));
	
	Graph->Nv = N+1; //The problem is that the vertex starts from 1, so + 1, G[0] is wasted
	Graph->Ne = M;
	
	Graph->G = malloc((Graph->Nv)*sizeof(AdjV*));
	
	Vertex V;
	for(V=0;V<Graph->Nv;V++){
		
		Graph->G[V] = NULL;
	}
	
	Edge E;
	int i;
	for(i=0;i<Graph->Ne;i++){
		
		scanf("%d %d",&E.V1,&E.V2);
		
		InsertEdge( Graph,E );
	}
	
	return Graph;
}

//Insert edge function
void InsertEdge( LGraph* Graph,Edge E )
{
	AdjV* NewNode;
	
	NewNode = (AdjV*)malloc(sizeof(AdjV));
	NewNode->V = E.V2;
	NewNode->Next = Graph->G[E.V1];
	Graph->G[E.V1] = NewNode;
	
	NewNode = (AdjV*)malloc(sizeof(AdjV));
	NewNode->V = E.V1;
	NewNode->Next = Graph->G[E.V2];
	Graph->G[E.V2] = NewNode;
}

//Algorithm for verifying six dimensional space theory
void SixDegrees( LGraph* Graph )
{
	int NumsConformToSixDegrees;
	double Proportion;
	Vertex V;
	for(V=1;V<Graph->Nv;V++){
		
		NumsConformToSixDegrees = BFS( Graph,V );
		
		Proportion =(1.0*NumsConformToSixDegrees/(Graph->Nv-1))*100;
		
		printf("%d: %.2lf%%\n",V,Proportion);
	}	
}

//Core BFS
int BFS( LGraph* Graph,Vertex V )
{
	bool Visited[Graph->Nv];
	InitilizeVisited( Visited,Graph->Nv );
	
	Queue* Q = CreateQ( Graph->Nv );
	
	Visited[V] = true;
	
	AddQ( Q,V );
	
	Vertex W,Tail,Last = V;
	int Level=0;
	AdjV* p;
	while( !IsEmpty( Q )){
		
		W = DeleteQ( Q );
		
		for(p=Graph->G[W];p;p=p->Next){
			
			if(!Visited[p->V]){
				
				Visited[p->V] = true;
				
				AddQ( Q,p->V );
				
				Tail = p->V;
			}
		}
		
		if(Last == W){
			Level++;
			Last = Tail;
		}
		
		if(Level==6){
			break;
		}
	}
	
	free(Q);
	
	int NumsConformToSixDegrees = NumTrueOfVisited( Visited,Graph->Nv );
	
	return NumsConformToSixDegrees;
}

//Queue and its related operations
Queue* CreateQ( int Nv )
{
	Queue* Q = (Queue*)malloc(sizeof(Queue));
	
	Q->QueArray = malloc(Nv*sizeof(Vertex));
	
	Q->front = Q->rear = -1;
	
	return Q;
}

void AddQ( Queue* Q,Vertex V )
{
	Q->rear++;
	
	Q->QueArray[Q->rear] = V;
}

Vertex DeleteQ( Queue* Q )
{
	Q->front++;

	return Q->QueArray[Q->front];
}

bool IsEmpty( Queue* Q )
{
	return Q->front == Q->rear ? true : false;	
}

/*Other auxiliary functions*/
//Initialize access array
void InitilizeVisited( bool Visited[],int Nv )
{
	Vertex V;
	for(V=0;V<Nv;V++){
		
		Visited[V] = false;
	}
}

//Calculate the number of people visited
int NumTrueOfVisited( bool Visited[],int Nv )
{
	int Sum = 0 ;
	
	Vertex V;
	for(V=1;V<Nv;V++){
		
		if(Visited[V]){
			
			Sum++;
		}
	}
	
	return Sum;
}

//malloc means free
void FreeGraph( LGraph* Graph )
{
	AdjV *p,*q;
	Vertex V;
	for(V=0;V<Graph->Nv;V++){
		
		for(p=Graph->G[V];p;p=q){
			
			q=p->Next;
			free(p);
		}
	}
	
	free(Graph->G);
	free(Graph);
}

 

Tags: C data structure

Posted by DragonHighLord on Wed, 04 May 2022 13:11:02 +0300