Adjacency matrix representation of weighted undirected graph (implemented in C language)

Adjacency matrix representation of weighted undirected graph (C Language implementation )

One 、 Adjacency matrix representation

​ Definition ： Adjacency matrix storage , It refers to using a one-dimensional array to store the information of vertices in the graph , Use a two-dimensional array to store the information of the edges in the graph （ That is, the adjacency relationship between vertices ）, The two-dimensional array that stores the adjacency relationship between vertices is called adjacency matrix .

​ about With weight chart for , If the summit V_i and V_j There are edges between them , Then the corresponding term in the adjacency matrix stores the A weight , If the summit V_i and V_j Not connected , Then use 0 or ∞ To represent that there is no edge between the two vertices .

​ for example , For a graph like this ：

​ We can get its adjacency matrix ：

​

​ notes ： In brackets 0、1、2、3 Represents the subscript of its two-dimensional array .

​ Easy to find , Weighted adjacency matrix has the following characteristics ：① About the symmetry of the main diagonal elements ;② Not 0 The value at the corresponding position of is the weight of the edge .

​ If it is without rights , Then the corresponding position of the edge is 1, The position of the edge is 0, It is also about the symmetry of the main diagonal elements .

Two 、 The functions realized by this program

• Create adjacency matrix of undirected graph

• Output the adjacency matrix corresponding to the undirected graph

• Output vertex set

• Determine whether two vertices are adjacent , That is, whether there are directly connected edges

3、 ... and 、 Structure definition of weighted undirected graph

typedef char VertexType; // The data type of the vertex 
typedef int EdgeType; // The data type of edge weight in weighted graph 

typedef struct {
    
	VertexType Vex[MaxVertexNum]; // Vertex table  MaxVertexNum Is the maximum number of vertices , The same below 
	EdgeType Edge[MaxVertexNum][MaxVertexNum];// Adjacency matrix , Side table 
	int vexnum, arcnum; // The current number of vertices and edges of a graph 
}MGraph;// Weighted undirected graph based on adjacency matrix method 

Four 、 Create an undirected graph and adjacency matrix

​ Because it's easy , There's not much to explain . It is worth noting that , We should make good use of the property that adjacency matrix of the undirected graph is symmetric about principal diagonal , So when you input the edge weight, you only need to input the upper triangle or the lower triangle .

void CreateMGraph(MGraph *G)
{
    
	int i,j,k,w;
	// First determine the number of vertices and edges 
	printf(" Please enter the number of vertices and edges , Space off :\n");
	scanf("%d %d",&G->vexnum,&G->arcnum);
	fflush(stdin);// Clear input buffer , Otherwise, the input may not be read normally  
	
	// Enter the values of the vertices in turn 
	printf(" Please enter the values of the vertices in turn :\n");
	for(int i = 0;i < G->vexnum; i++)
	{
    
		printf(" Enter the first %d Vertex information :\n",i+1);
		scanf("%c",&G->Vex[i]); // The received values are placed in the vertex table 
		fflush(stdin);// Clear input buffer , Otherwise, the input may not be read normally 
	}
	
	// Initialize adjacency matrix 
	for(i = 0;i < G->vexnum; i++)
		for(j = 0;j <G->vexnum; j++)
			G->Edge[i][j] = 0;// At the beginning, all are initialized to 0, It can also be used. ∞ 
				
	// Adjacency Matrix Building 
	for (k = 0; k < G->arcnum; k++)						
	{
    
		printf(" The input side <vi,vj> The subscript i, Subscript j And power w:\n");
		scanf("%d%d%d", &i, &j, &w);	// The input side <vi,vj> Weight on w
		G->Edge[i][j] = w;
		G->Edge[j][i] = G->Edge[i][j];	// An undirected graph matrix is symmetric 
	}
	
}

5、 ... and 、 Output adjacency matrix

​ The essence is to traverse a two-dimensional array .

// Output adjacency matrix  
void PrintMatrix(MGraph G)							
{
    
	int i,j;
	printf(" The adjacency matrix is represented as follows :\n");
	for (i = 0; i < G.vexnum; i++)
	{
    
		for (j = 0; j < G.vexnum; j++)
			printf("%-10d", G.Edge[i][j]);// Left aligned output  
		printf("\n");
	}
}

6、 ... and 、 Output vertex set

​ The essence is to traverse a one-dimensional array .

// Output vertex set 
void PrintVex(MGraph G) 
{
    
	printf("\n The vertex set is ：");
	for(int i=0;i<G.vexnum;i++)
		printf("%c ",G.Vex[i]);
	printf("\n");
}

7、 ... and 、 Determine whether two vertices are adjacent

​ The received parameter is the value of two vertices , So you need to find its subscript in the vertex table , Then judge whether the value of the adjacency matrix of its corresponding position is greater than 0, If it is greater than 0 It means adjacency , Otherwise not adjacent .

​ notes ： If the subscript operation of finding vertices is more frequent , You can consider encapsulating it into a function .

// Determine whether two vertices are adjacent  
bool Is_Edge_Exist(MGraph G, VertexType d1, VertexType d2)
{
    
	int i,j,k;
	for(k=0;k<G.vexnum;k++)
	{
    
		if(G.Vex[k]==d1)
			i = k;// Find the subscript corresponding to the vertex  
		if(G.Vex[k]==d2)
			j = k;// Find the subscript corresponding to the vertex 
	}
	return G.Edge[i][j]>0?1:0;
}

8、 ... and 、 All the code

#include<stdio.h>
#define MaxVertexNum 10 // The maximum number of vertices 
#include<stdbool.h> // according to C99 standard ,C Language use bool Type needs to add this header file 

typedef char VertexType; // The data type of the vertex 
typedef int EdgeType; // The data type of edge weight in weighted graph 

typedef struct {
    
	VertexType Vex[MaxVertexNum]; // Vertex table 
	EdgeType Edge[MaxVertexNum][MaxVertexNum];// Adjacency matrix , Side table 
	int vexnum, arcnum; // The current number of vertices and edges of a graph 
}MGraph;// Weighted undirected graph based on adjacency matrix method  

void CreateMGraph(MGraph *G)
{
    
	int i,j,k,w;
	// First determine the number of vertices and edges 
	printf(" Please enter the number of vertices and edges , Space off :\n");
	scanf("%d %d",&G->vexnum,&G->arcnum);
	fflush(stdin);// Clear input buffer , Otherwise, the input may not be read normally  
	
	// Enter the values of the vertices in turn 
	printf(" Please enter the values of the vertices in turn :\n");
	for(int i = 0;i < G->vexnum; i++)
	{
    
		printf(" Enter the first %d Vertex information :\n",i+1);
		scanf("%c",&G->Vex[i]); // The received values are placed in the vertex table 
		fflush(stdin);// Clear input buffer , Otherwise, the input may not be read normally 
	}
	
	// Initialize adjacency matrix 
	for(i = 0;i < G->vexnum; i++)
		for(j = 0;j <G->vexnum; j++)
			G->Edge[i][j] = 0;// At the beginning, all are initialized to 0, It can also be used. ∞ 
				
	// Adjacency Matrix Building 
	for (k = 0; k < G->arcnum; k++)						
	{
    
		printf(" The input side <vi,vj> The subscript i, Subscript j And power w:\n");
		scanf("%d%d%d", &i, &j, &w);	// The input side <vi,vj> Weight on w
		G->Edge[i][j] = w;
		G->Edge[j][i] = G->Edge[i][j];	// An undirected graph matrix is symmetric 
	}
	
}

// Output adjacency matrix  
void PrintMatrix(MGraph G)							
{
    
	int i,j;
	printf(" The adjacency matrix is represented as follows :\n");
	for (i = 0; i < G.vexnum; i++)
	{
    
		for (j = 0; j < G.vexnum; j++)
			printf("%-10d", G.Edge[i][j]);// Left aligned output  
		printf("\n");
	}
}

// Output vertex set 
void PrintVex(MGraph G) 
{
    
	printf("\n The vertex set is ：");
	for(int i=0;i<G.vexnum;i++)
		printf("%c ",G.Vex[i]);
	printf("\n");
}

// Determine whether two vertices are adjacent  
bool Is_Edge_Exist(MGraph G, VertexType d1, VertexType d2)
{
    
	int i,j,k;
	for(k=0;k<G.vexnum;k++)
	{
    
		if(G.Vex[k]==d1)
			i = k;// Find the subscript corresponding to the vertex  
		if(G.Vex[k]==d2)
			j = k;// Find the subscript corresponding to the vertex 
	}
	return G.Edge[i][j]>0?1:0;
}

int main()
{
    
	MGraph G;// Undirected graph  
	CreateMGraph(&G);// Create diagrams  
	PrintMatrix(G);// Output adjacency matrix  
	PrintVex(G);// Output vertex  
	
	// Determine whether two vertices are adjacent  
	VertexType d1,d2;
	d1 = 'A';
	d2 = 'B';
	if(Is_Edge_Exist(G,d1,d2))
		printf("\n%c and %c Adjacency !\n",d1,d2);
	else
		printf("\n%c and %c No adjacency !\n",d1,d2);
	d2 = 'C';
	if(Is_Edge_Exist(G,d1,d2))
		printf("\n%c and %c Adjacency !\n",d1,d2);
	else
		printf("\n%c and %c No adjacency !\n",d1,d2);
	return 0;
} 

Nine 、 test

Input example ：

When the input Just enter the upper triangle or the lower triangle ( Does not include... On the main diagonal ) that will do .