本文章收录入数据结构与算法基础知识文章汇总，需要了解数据结构与算法链表，二叉树等相关知识的同学欢迎查看。

图指的是计算机中数据关系中的逻辑结构，数据在计算机中的只能由两种存储结构存储在计算机中，分别为顺序存储和链式存储。

一、图的基础知识

1.上图中的蓝色带标号的点称为顶点；

2.顶点之间的连接线称为边。

1.图的定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成。通常表示为G(V,E)，其中G表示图，V表示顶点的集合，E表示顶点之间边的集合。

2.图的分类

1.有向图和无向图

1.根据顶点之间边的关系划分；

2.任意两个顶点之间的边没有方向。图称之为无向图、边称为无向边；

3.任意两个顶点之间的边有方向，只能由一个顶点指向另一个顶点。图称之为有向图，边称之为有向边。

2.无向完全图和有向完成图

图中的任意一个顶点和其他顶点之间都有连接。

3.网图

图中的顶点之间连接的边是有权重的，每条边的权重可能不一样，这种顶点之间的边带权重的图称之为网图。

4.连通图和非连通图

1.图中的某些顶点和其他的顶点之间没有边进行连接，也不能通过顶点之间的边进行间接的连接，称这种图为非连通图，如图1；

2.图中的所有顶点都可以通过有限的边进行连接，即所有的顶点之间是连通的，称这种图为连通图，如图2。

5.子图

图中任意顶点和连接的边的集合构成的图，称之为图的子图。

二、图的存储

以快手面试真题为例：

题意分析：

1.题目要求：设计一种数据结构，将上面的图存到计算机的内存中；

2.上图是一个有向网图；

3.图中有顶点数据[v0 v1 v2 v3 v4],边数据[1(v3->v4) 2(v2->v0) 3(v1->v2) 5(v2->v3) 6(v0->v4) 9(v1->v0)];

思考：如何将顶点和边存到内存中，并且满足图中各顶点之间的关系呢？

（一）顺序存储–邻接矩阵

1.邻接矩阵

（1）图是一个无向图、并且边无权重时

1.用一个一维数组存储顶点信息；

2.用一个二维数组存储顶点之间的边信息，顶点之间有连接用1表示，无连接用0表示；

上图存储边信息的二维数组矩阵有如下特征：

1.第i行第j列的位置存储的是顶点Vi和顶点Vj的边信息，如果Vi和Vj有连接关系，则i行j行记为1，二维数组的对应位置存储1，否则记为0；

2.矩阵的对角线上存的数据为0，即任意顶点和自己之间是没有连接关系的。

3.矩阵中的数据以对角线对称，即无向图中Vi和Vj之间的边和Vj和Vi之间的边是相等的。

（2）图是一个有向图，并且边无权重时

这种情况与（1）的区别主要是图是一个有向图，二维数组矩阵中Vi和Vj之间的边和Vj和Vi之间的边是不相等，即Vi指向Vj，但Vj不一定指向Vi.

(3)图是一个有向图，并且有权重时

1.这种情况和（2）的区别就是有权重，所以二维数组存的数据是边的权重值；

2.由于权重值有可能是1，所以如果顶点之间的没有边信息，对应的二维数组存的值可以为一个异常的数据，如无穷大。

通过上面的分析，我们得到的存储图的顶点与顶点关系的二维数组矩阵即为邻接矩阵。

2.代码实现

1.定义一些状态值和数据类型

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define MAXVEX 100 //最大顶点数，应由用户定义

#define INFINITYC 0

typedef int Status;    //Status是函数的类型,其值是函数结果状态代码，如OK等

typedef char VertexType; //顶点类型

typedef int EdgeType; //边上的权值类型
复制代码

2.存储结构设计

typedef struct
{
    VertexType vexs[MAXVEX]; //顶点表

    EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵，可看作边表

    int numNodes, numEdges; //图中当前的顶点数和边数

}MGraph;
复制代码

3.存储实现

void CreateMGraph(MGraph *G){

    int i,j,k,w;
    
    printf("输入顶点数和边数:\n");

    //1. 输入顶点数/边数
    scanf("%d,%d",&G->numNodes,&G->numEdges);
    printf("顶点数:%d,边数:%d\n",G->numNodes,G->numEdges);

    //2.输入顶点信息/顶点表
    for(int i = 0; i< G->numNodes;i++)
    {
        getchar();
        scanf("%c",&G->vexs[i]);
    }

    printf("顶点数据：\n");
    for (i = 0; i<G->numNodes; i++) {
        printf("%c ",G->vexs[i]);
    }
    printf("\n");

    //3.初始化邻接矩阵
    for(i = 0; i < G->numNodes;i++)
         for(j = 0; j < G->numNodes;j++)
             G->arc[i][j] = INFINITYC;

    //4.输入边表信息
    for(k = 0; k < G->numEdges;k++){
        printf("输入边(vi,vj)上的下标i,下标j,权w\n");
        scanf("%d,%d,%d",&i,&j,&w);

        G->arc[i][j] = w;

        //如果无向图,矩阵对称;
        G->arc[j][i] = G->arc[i][j];
    }

    //5.打印邻接矩阵
    for (int i = 0; i < G->numNodes; i++) {
        printf("\n");
        for (int j = 0; j < G->numNodes; j++) {
            printf("%d ",G->arc[i][j]);
        }
    }
    printf("\n");
}
复制代码

4.调试

5.邻接矩阵的缺点

1.如上面的图，有5个顶点，但却只有一条边信息；

2.但在顺序存储中，需要申请5×5的二维数组矩阵空间来存储这一条边信息；

3.这就导致了大量的空间浪费。

（二）链式存储–邻接表

1.邻接表

1.创建一个一维顶点数组存储顶点信息；

2.顶点数组存的元素是一个顶点数据的结点，顶点的数据结构中有一个指针指向边信息，边信息是一个单向链表，这个单向链表存储了所有与顶点有连接的顶点的边信息；

3.边信息的单向链表保存的是顶点与其他顶点之间的边数据，它们没有顺序关系。

2.代码实现

以如上例子实现邻接表下的链式存储

1.定义一些状态值和数据类型

#define M 100

#define true 1

#define false 0

typedef char Element;

typedef int BOOL;
复制代码

2.定义结点和存储结构

//邻接表的边结点
typedef struct Node{

    int adj_vex_index;  //边信息对应的顶点在数组中的下标

    Element data;       //边的权重值

    struct Node * next; //边指针：指向下一个边结点

}EdgeNode;

//顶点结点
typedef struct vNode{

    Element data;          //顶点数据

    EdgeNode * firstedge;  //顶点下一个是谁？

}VertexNode, Adjlist[M];


//总图的一些信息
typedef struct Graph{

    Adjlist adjlist;       //顶点表

    int arc_num;           //边数

    int node_num;          //顶点数

    BOOL is_directed;      //是不是有向图

}Graph, *GraphLink;
复制代码

3.存储实现

void creatGraph(GraphLink *g){
    int i,j,k;

    EdgeNode *p;

    //1. 顶点,边,是否有向
    printf("输入顶点数目,边数和有向？：\n");
    scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed);


    //2.顶点表
    printf("输入顶点信息：\n");
    for (i = 0; i < (*g)->node_num; i++) {
        getchar();
        scanf("%c", &(*g)->adjlist[i].data);
        //创建顶点时，顶点数据指向边信息此时还没有，所以指向null
        (*g)->adjlist[i].firstedge = NULL;
    }
    
    //3.边信息
    printf("输入边信息：\n");
    for (k = 0; k < (*g)->arc_num; k++){
        getchar();
        scanf("%d %d", &i, &j);

        //①新建一个节点
        p = (EdgeNode *)malloc(sizeof(EdgeNode));

        //②弧头的下标
        p->adj_vex_index = j;

        //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
        p->next = (*g)->adjlist[i].firstedge;

        //④将顶点数组[i].firstedge 设置为p
        (*g)->adjlist[i].firstedge = p;

        if(!(*g)->is_directed)
        {
            // j -----> i
            //①新建一个节点
            p = (EdgeNode *)malloc(sizeof(EdgeNode));

            //②弧头的下标i
            p->adj_vex_index = i;

            //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
            p->next = (*g)->adjlist[j].firstedge;

            //④将顶点数组[i].firstedge 设置为p
            (*g)->adjlist[j].firstedge = p;
        }
    }
}
复制代码

1.输入顶点个数、边数、是否是有向图等信息；

2.顶点存入一维数组中，一维数组存的是一个带数据域和指针域的结构体，数据域存储顶点数据，指针域指向存储边信息的单向链表；

3.输入边信息，i是当前顶点下标，j是连接顶点在顶点数组中的下标；

4.输入后创建结点，记录权重值、顶点的下标j、指针域指向等；

5.判断是否是有向图，如果是无向图的话，需要确定j为原顶点，i为指向的顶点的关系，创建j与i两个顶点之间的关系,即反向关系。

4.遍历打印

void putGraph(GraphLink g){
    int i;
    printf("邻接表中存储信息:\n");

    //遍历一遍顶点坐标，每个再进去走一次
    for (i = 0; i < g->node_num; i++) {
        EdgeNode * p = g->adjlist[i].firstedge;

        while (p) {
            printf("%c->%c ", g->adjlist[i].data, g->adjlist[p->adj_vex_index].data);
            p = p->next;
        }
        printf("\n");
    }
}
复制代码

5.调试

/*
     邻接表实现图的存储
     输入顶点数目,边数和有向？：
     4 5 0

     输入顶点信息：
     0 1 2 3

     输入边信息：
     0 1 0 2 0 3 2 1 2 3

     邻接表中存储信息:
     0->3 0->2 0->1
     1->2 1->0
     2->3 2->1 2->0
     3->2 3->0
    */

    /*

     邻接表实现图的存储
     输入顶点数目,边数和有向？：
     4 5 1

     输入顶点信息：
     0 1 2 3

     输入边信息：
     1 0 1 2 2 1 2 0 0 3

     邻接表中存储信息:
     0->3
     1->2 1->0
     2->0 2->1
     */

    GraphLink g = (Graph *)malloc(sizeof(Graph));
    creatGraph(&g);
    putGraph(g);
复制代码

无向图存储