• The concept of the figure

    A Graph is a finite non-empty set of vertices and a set of edges between vertices. It is usually expressed as: G(V,E). Where,G represents a graph, where V is the set of vertices in graph G and E is the set of edges in graph G.

    The elements that make up a stack, queue, tree, or list are called nodes. Note that the elements that make up a graph are called vertices. The relationship between vertices in a graph is many-to-many, as shown below:

  • Definitions of various graphs

    1. Undirected graph & undirected edgeThe graph shown below is an undirected graph. In common terms, it means that the edges of the graph have no direction and two vertices can point to each other
    2. Directed graph & directed edgesIt’s just a graph where the edges have directions
    3. Undirected complete graphIf there are n vertices in an undirected graph, there are at most N (n-1)/2 arcs, and we call an undirected graph with n(n-1)/2 arcs an undirected perfect graph
    4. Directed complete graphIf there are n vertices in a digraph, there are n(n-1)/2 arcs at most, and we call a digraph with n(n-1)/2 arcs undirected perfect graph
    5. Connected graphConnected graphs are based on the concept of connectivity. In an undirected graph G, I and j are said to be connected if there is a path from vertex I to vertex J (and of course there must be a path from j to I)
    6. A connected graphA graph with at least one point disconnected is an disconnected graph

  • The idea of storage – adjacency matrix of graph

    1. Creates an array to store all the vertices designed in the graph
    2. Creates a two-dimensional array to store the relationships between vertices

  • The adjacency matrix stores the relevant code

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

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* Maximum number of vertices */
#define INFINITYC 65535typedef int Status; /* typedef char VertexType; /* typedef char VertexType; /* The vertex type should be user-defined */ typedef int EdgeType; /* the weight type on the edge should be user defined */ typedef struct {VertexType * vers; EdgeType **edges; Int numNodes,numEdges; // Number of vertices and number of edges} Graph; Status initGraph(int numNodes,int numEdges,Graph *G){ G->numEdges = numEdges; G->numNodes = numNodes; G->vers = (VertexType *)malloc(sizeof(VertexType) * numNodes);if(G->vers == NULL) returnERROR; G->edges = (EdgeType **)malloc(sizeof(EdgeType *) * numEdges);if(G->edges == NULL) return ERROR;
    for(int i = 0; i < numEdges; i ++){
        G->edges[i] = (EdgeType *)malloc(sizeof(EdgeType) * numEdges);
        if(G->edges[i] == NULL) returnERROR; } // the small detail here is that when there is no relation, we set it to infinity, and when there is relation, the corresponding position can store weights. // By default, each vertex has no relationfor(int i = 0; i < G->numNodes; i ++)
        for(int n = 0; n < G->numNodes; n ++)
            G->edges[i][n] = INFINITYC;
    return OK;
}

void CreateGraph(Graph *G){

    int i,j,k,w,numNodes,numEdges;
    printf("Input number of vertices and edges :\n"); //1. Input vertices/edges scanf("%d,%d",&numNodes,&numEdges); getchar(); // Initialize initGraph(numNodes, numEdges, G);printf("Vertices :%d, edges :%d\n",G->numNodes,G->numEdges); // Enter the vertex informationfor(i = 0; i <= G->numNodes; i ++){
        scanf("%c",&G->vers[i]); } //4. Enter side table informationfor(k = 0; k < G->numEdges; k++){printf("Subscript I, subscript j, weight w\n on input edge (vi,vj)");
        scanf("%d,%d,%d",&i,&j,&w); G->edges[i][j] = w; // If there is no digraph, the matrix is symmetric; G->edges[j][i] = G->edges[i][j]; } /*5. Print the adjacency matrix */for (int i = 0; i < G->numNodes; i++) {
        printf("\n");
        for (int j = 0; j < G->numNodes; j++) {
            printf("%d ",G->edges[i][j]); }}printf("\n");
    
    
}
Copy the code

  • Graph memory – adjacency list implementation ideas

    1. Create an array of vertices to store vertex information (the nodes in the array are data to store the data in the vertex and a pointer to the first node in the relational linked list)
    2. Create a relational linked list that stores information about all vertices that are related to the current vertex.

    To use a metaphor, in the heart of a graph is an array of linked lists. Each linked list contains a head node, which stores vertex information, and the nodes after the head node store the vertices related to the head node

  • Adjacency list stores the relevant code

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

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define M 100typedef int Status; typedef char Element; Typedef struct Node {int index; // The vertex corresponds to the subscript Element data in the vertex table; Struct Node *next; // pointer to next j vertex}Node; Typedef struct vNode{struct Node * firstNode; // If there are no related vertices, they point to null Element data; }vNode,Adjlist[M]; Typedef struct Graph{Adjlist Adjlist; Int arc_num; Int node_num; // Number of nodes int is_directed; }Graph, *GraphLink; void creatGraph(GraphLink *g){ int i,j,k; Node *p; //1. Vertices, edges, whether directedprintf("Input number of vertices, number of edges, and direction? : \ n");
    scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed); / / 2. Vertex tableprintf("Enter vertex information: \n");
    for (i = 0; i < (*g)->node_num; i++) {
        getchar();
        scanf("%c", &(*g)->adjlist[i].data);
        (*g)->adjlist[i].firstNode = NULL;
    }
    
    printf("Input side information: \n");
    for (k = 0; k < (*g)->arc_num; k++){
        getchar();
        scanf("%d %d", &i, &j);
        p = (Node *)malloc(sizeof(Node));
        p->index = j;
        p->data = (*g)->adjlist[j].data;
        p->next = (*g)->adjlist[i].firstNode;
        (*g)->adjlist[i].firstNode = p;
        
        if((*g)->is_directed == 1){
            p = (Node *)malloc(sizeof(Node));
            p->index = i;
            p->data = (*g)->adjlist[i].data;
            p->next = (*g)->adjlist[j].firstNode;
            (*g)->adjlist[j].firstNode = p;
        }
    }
}

void putGraph(GraphLink g){
    int i;
    printf("Store information in adjacency list :\n"); // Walk through the vertex coordinates once morefor (i = 0; i < g->node_num; i++) {
        Node * p = g->adjlist[i].firstNode;
        while (p) {
            printf("%c->%c ", g->adjlist[i].data, g->adjlist[p->index].data);
            p = p->next;
        }
        printf("\n"); }}Copy the code