Related operations of figure

Preface

Subject requirements ：
1. According to input , Data using adjacency matrix ;
2. Realize the depth first or breadth first traversal of the graph .
3. Circle of friends problem
4. Village to village connectivity

---

Tips ： The following is the main body of this article , The following cases can be used for reference

Complete code

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <malloc.h>
#define Maxvex 100 
typedef char VertexType;
typedef int EdgeType;
int visited[Maxvex];

// Define the diagram structure  
typedef struct MGraph {
    
	VertexType vexs[Maxvex];
	EdgeType arc[Maxvex][Maxvex];
	int numvex, numedg;
}MGraph;

// Define the queue  
typedef struct Queue {
    
	int data[Maxvex];
	int head,tail;
}Queue; 

// Initialize queue  
void BeQueue(Queue *Q){
    
	Q->head=Q->tail=0;
} 

// The team 
void  InQueue(Queue *Q,int i){
    
	Q->data[Q->tail]=i;
	Q->tail=(Q->tail+1)%Maxvex;
}

// Out of the team 
void OutQueue(Queue *Q,int *i){
    
	*i=Q->data[Q->head];
	Q->head=(Q->head+1)%Maxvex;
} 
// Determines if the queue is empty 
int Judge(Queue *Q){
    
	if(Q->head==Q->tail){
    
		return 1;
	}
	else{
    
		return 0;
	}
}
// Establish adjacency graph  
void CreateMGraph(MGraph* G) {
    
	int i, j, k, w;
	printf(" Enter the number of vertices and edges ：\n");
	scanf("%d%d", &G->numvex, &G->numedg);
	getchar();// Clear cache  
	
	printf(" Enter each vertex ：\n"); 
	for (i = 0;i < G->numvex;i++){
    
		printf(" The vertices %d:",i+1);
		scanf("%c",&G->vexs[i]);
		getchar();// Clear cache 
	}
	for (i = 0;i < G->numvex;i++) {
    
		for (j = 0;j < G->numvex;j++) {
    
			G->arc[i][j] = 0;// Assign an initial value to the weight 0 
		}
	}
	for (k = 0;k < G->numedg;k++) {
    
		printf(" The input side （vi,vj） The superscript of i, Subscript j And weights w\n");
		scanf("%d%d%d", &i, &j,&w);
		G->arc[i][j] = w;
		G->arc[j][i] = G->arc[i][j];
	}
}
// Build relationships  
void CreateFriend(MGraph* R) {
    
	int i, j, k;
	printf(" Enter the number of people and the number of relationship sides ：\n");
	scanf("%d%d", &R->numvex, &R->numedg);
	getchar();// Clear cache  
	
	printf(" Enter the person's code ：\n"); 
	for (i = 0;i < R->numvex;++i){
    
		printf(" people %d:",i+1);
		scanf("%c",&R->vexs[i]);
		getchar();// Clear cache 
	}
	for (i = 0;i < R->numvex;i++) {
    
		for (j = 0;j < R->numvex;j++) {
    
			R->arc[i][j] = 0;// Assign an initial value to the weight 0 
		}
	}
	for (k = 0;k < R->numedg;k++) {
    
		printf(" Input person （vi,vj） The superscript of i, Subscript j\n");
		scanf("%d%d", &i, &j);
		R->arc[i][j] = 1;
		R->arc[j][i] = R->arc[i][j];
	}
}
// Establish inter Village Relations  
void CreateCountryside(MGraph* C) {
    
	int i, j, k, w;
	printf(" Input the number of villages and connecting channels ：\n");
	scanf("%d%d", &C->numvex, &C->numedg);
	getchar();// Clear cache  
	
	for (i = 1;i <= C->numvex;i++) {
    
		for (j = 1;j <= C->numvex;j++) {
    
			C->arc[i][j] = 0;// Assign an initial value to the weight 0 
		}
	}
	
	for (k = 1;k <= C->numedg;k++) {
    
		printf(" Enter village road （vi,vj） The superscript of i, Subscript j And weights w\n");
		scanf("%d%d%d", &i, &j,&w);
		C->arc[i][j] = w;
		C->arc[j][i] = C->arc[i][j];
	}
}
// Print adjacency diagram  
void print(MGraph* G) {
    
	int i, j;
	printf(" Adjacency graph is ：\n");
	for (i = 0;i < G->numvex;i++) {
    
		for (j = 0;j < G->numvex;j++) {
    
			printf("%d\t", G->arc[i][j]);
		}
		printf("\n");
	}
}
// Print a relationship map  
void printF(MGraph* R) {
    
	int i, j;
	printf(" The interpersonal relationship diagram is ：\n");
	for (i = 0;i < R->numvex;i++) {
    
		for (j = 0;j < R->numvex;j++) {
    
			printf("%d\t", R->arc[i][j]);
		}
		printf("\n");
	}
}
// Print the village diagram  
void printC(MGraph* G) {
    
	int i, j;
	printf(" The village relationship diagram is ：\n");
	for (i = 1;i <= G->numvex;i++) {
    
		for (j = 1;j <= G->numvex;j++) {
    
			printf("%d\t", G->arc[i][j]);
		}
		printf("\n");
	}
}
// Deep search  
void DFS(MGraph G, int i) {
    
	int j;
	visited[i] = 1;
	printf("%c", G.vexs[i]);
	for (j = 0;j < G.numvex;j++) {
    
		if (G.arc[i][j] !=0 && !visited[j]) {
    
			DFS(G, j);
		}
	}
}

void DFST(MGraph G){
    
	int i;
	for(i=0;i<G.numvex;++i){
    
		visited[i]=0;
	}
	for(i=0;i<G.numvex;++i){
    
		if(!visited[i]){
    
			DFS(G,i);
		}
	}
}
// Width search  
void BFS(MGraph *G){
    
	Queue Q;
	int i,j;
	for(i=0;i<G->numvex;i++){
    
		visited[i]=0;
	}
	BeQueue(&Q);
	for(i=0;i<G->numvex;i++){
    
		visited[i]=1;
		printf("%c",G->vexs[i]);
		InQueue(&Q,i);
		while(!Judge(&Q)){
    
			OutQueue(&Q,&i);
			for(j=0;j<G->numvex;j++){
    
				if(!visited[j]&&G->arc[i][j]!=0){
    
					visited[j]=1;
					printf("%c",G->vexs[j]);
					InQueue(&Q,j);
				}
			}
		}
	}
	printf("\n");
}
// Please have a few circles of friends  
void DFSF(MGraph R, int i) {
    
	int j;
	visited[i] = 1;
	for (j = 0;j < R.numvex;j++) {
    
		if (R.arc[i][j] !=0 && !visited[j]) {
    
			DFSF(R, j);
		}
	}
}
void DFSTF(MGraph R){
    
	int i,c=0;
	for(i=0;i<R.numvex;++i){
    
		visited[i]=0;
	}
	for(i=0;i<R.numvex;++i){
    
		if(!visited[i]){
    
			DFSF(R,i);
			c++;
		}
	}
	printf("%d Individuals share %d Circle of friends \n",R.numvex,c);
}
// Prim algorithm 
void Prim(MGraph C){
    
	int min,i,j,k,L=0;
	int adjvex[Maxvex];
	int lowcost[Maxvex];
	adjvex[1]=1;
	lowcost[0]=0;
	for(i=2;i<=C.numvex;i++){
    
		lowcost[i]=C.arc[1][i];
		adjvex[i]=1;
	}
	for(i=2;i<=C.numvex;i++){
    
		min=1000000;
		j=2;k=1;
		while(j<=C.numvex){
    
			if(lowcost[j]!=0&&lowcost[j]<min){
    
				min=lowcost[j];
				k=j;
			}
			j++;
		}
		if(min!=1000000) 
			L=L+min;
		lowcost[k]=0;
		for(j=2;j<=C.numvex;j++){
    
			if(lowcost[j]!=0&&C.arc[k][j]<lowcost[j]){
    
				lowcost[j]=C.arc[k][j];
				adjvex[j]=k;
			}
		}
	}
	printf("%d\n",L);
}
// Circle of friends problem 
void Friend(){
    
	MGraph R;
	CreateFriend(&R);
	printF(&R);
	DFSTF(R);
}
// Village to village connectivity 
void Countryside(){
    
	MGraph C;
	CreateCountryside(&C);
	printC(&C);
	Prim(C);
} 
int function(){
    
	int choose=-1;
	printf("1、 Create diagrams \n"); 
	printf("2、 Depth-first traversal \n"); 
	printf("3、 Breadth first traversal \n");
	printf("4、 Circle of friends problem \n");
	printf("5、 Village to village connectivity \n");
	printf("0、 sign out \n");
	while(choose!=0){
    
		printf(" Please select ：\n");
		scanf("%d", &choose);
		switch(choose){
    
			case 1:
				MGraph G;
				CreateMGraph(&G);
				print(&G);
				break;
			case 2:
				printf(" The depth traversal of the graph is ：\n");
				DFST(G);
				printf("\n");
				break;
			case 3:
				printf(" The breadth traversal of the graph is ：\n");
				BFS(&G);
				break;
			case 4:
				Friend();
				break;
			case 5:
				Countryside();
				break;
		} 
	}
} 
int main() {
    
	function();
	return 0;
}

experimental result

main interface

Adjacency matrix

Circle of friends problem

Village to village connectivity