# The creation of c/c + + graph

### The creation of c/c + + graph

#### Concept of Graphs

• A graph consists of points and lines
• If you know how many points there are and which points are wired, you can draw a picture
• Lines between points, with and without direction

#### Create map

To create a graph is to create lines between nodes, nodes, and nodes, which can be represented by a two-dimensional array, that is, a matrix.

The following code implements the creation of the above figure

graph_mtx.h

```#include <stdio.h>
#include <malloc.h>
#include <assert.h>

#define Default_vertex_size 10

#define T char//dai biao ding dian de lei xing

typedef struct GraphMtx{
int MaxVertices;//zui da ding dian shu liang]
int NumVertices;//shi ji ding dian shu liang
int NumEdges;//bian de shu lian

T* VerticesList;//ding dian list
int** Edge;//bian de lian jie xin xi, bu shi 0 jiu shi 1
}GraphMtx;

//chu shi hua tu
void init_graph(GraphMtx* gm);
//Print 2D array
void show_graph(GraphMtx* gm);
//Insert Vertex
void insert_vertex(GraphMtx* gm, T v);
void insert_edge(GraphMtx* gm, T v1, T v2);
//Delete Vertex
void remove_vertex(GraphMtx* gm, T v);
//Delete lines between vertices
void remove_edge(GraphMtx* gm, T v1, T v2);
//Destruction map
void destroy_graph(GraphMtx* gm);

#endif```

graph_mtx.c

```#include "graph_mtx.h"

void init_graph(GraphMtx* gm){
gm->MaxVertices = Default_vertex_size;
gm->NumEdges = gm->NumVertices = 0;

//kai pi ding dian de nei cun kong jian
gm->VerticesList = (T*)malloc(sizeof(T) * (gm->MaxVertices));
assert(NULL != gm->VerticesList);

//Create a 2D array
//Let a second level pointer of int point to an array with eight first level pointers of int
//Open a memory space that can store GM - > maxvertices an int level pointer
gm->Edge = (int**)malloc(sizeof(int*) * (gm->MaxVertices));
assert(NULL != gm->Edge);
//Open GM - > maxvertices group to store memory space of GM - > maxvertices int
for(int i = 0; i < gm->MaxVertices; ++i){
gm->Edge[i] = (int*)malloc(sizeof(int) * gm->MaxVertices);
}
//Initialize 2D array
//Make the relationship between the edges of each vertex unconnected
for(int i = 0; i < gm->MaxVertices; ++i){
for(int j = 0; j < gm->MaxVertices; ++j){
gm->Edge[i][j] = 0;
}
}
}
//Print 2D array
void show_graph(GraphMtx* gm){
printf("  ");
for(int i = 0; i < gm->NumVertices; ++i){
printf("%c  ", gm->VerticesList[i]);
}
printf("\n");
for(int i = 0; i < gm->NumVertices; ++i){
//At the beginning of the line, print the name of the top point
printf("%c:", gm->VerticesList[i]);
for(int j = 0; j < gm->NumVertices; ++j){
printf("%d  ", gm->Edge[i][j]);
}
printf("\n");
}
printf("\n");
}
//Insert Vertex
void insert_vertex(GraphMtx* gm, T v){
//Vertex space is full. You can't insert any more vertices
if(gm->NumVertices >= gm->MaxVertices){
return;
}
gm->VerticesList[gm->NumVertices++] = v;
}

void insert_edge(GraphMtx* gm, T v1, T v2){
if(v1 == v2)return;

int j = -1;
int k = -1;
//Find the subscript of 2 vertices
for(int i = 0; i < gm->NumVertices; ++i){
if(gm->VerticesList[i] == v1){
j = i;
continue;
}
if(gm->VerticesList[i] == v2){
k = i;
continue;
}
}
//It means that the subscript of the vertex is found
if(j != -1 && k != -1){
//Update 2 values because there is no direction
gm->Edge[j][k] = gm->Edge[k][j] = 1;
//Edge number plus 1
gm->NumEdges++;
}
}
```

graph_mtxmain.c

```#include "graph_mtx.h"

int main(){
GraphMtx gm;
//Initialization diagram
init_graph(&gm);
//Insert Vertex
insert_vertex(&gm, 'A');
insert_vertex(&gm, 'B');
insert_vertex(&gm, 'C');
insert_vertex(&gm, 'D');
insert_vertex(&gm, 'E');

insert_edge(&gm, 'A', 'B');
insert_edge(&gm, 'A', 'D');
insert_edge(&gm, 'B', 'C');
insert_edge(&gm, 'B', 'E');
insert_edge(&gm, 'C', 'E');
insert_edge(&gm, 'C', 'D');

//Connection between vertices
show_graph(&gm);
}```

Tags: C

Posted on Fri, 31 Jan 2020 13:05:05 -0800 by jbreits