数据结构-图的存储方式

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；在图形结构中，是由顶点的有穷非空集合和顶点之间边的集合组成，如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。通常表示为：G(V,E)。其中G表示一个图，V是图G中的顶点集合，E是图G中边的集合。那么如何存储图呢？下面我们一起从源码出发，解析数据结构中图的存储方式。其实数据结构中图的存储方式分为两种：利用邻接矩阵，利用邻接表。下面我们详细看一下关于这两种图的存储方式

一、利用邻接矩阵

由定义我们可以知道，图是由两部分组成，顶点和边，顶点和边的连接，确定了图的逻辑关系，所以图的存储，其中它的顶点需要存储，边与边的连接信息也要存储。顶点的信息，可以使用一维数组进行存储。边的信息，存在这多对多的逻辑关系，那么可以使用二维数据进行存储。邻接矩阵的存储，其实就是顺序存储的方式。

邻接矩阵存储实现思路：

1.确定顶点数

2.读取顶点信息

3.初始化邻接矩阵

4.读入边的信息

5.循环打印

邻接矩阵存储图的数据结构：

#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; /* 边上的权值类型应由用户定义 */

typedef struct

{

    VertexType vexs[MAXVEX]; /* 顶点表 */

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

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

}MGraph;

存储部分

void CreateMGraph(MGraph *G){

    int i,j,k,w;

    printf("输入顶点数和边数\n");

    scanf("%d,%d",&G->numNodes,&G->numEdges);

    printf("顶点数：%d,边数：%d\n",G->numNodes,G->numEdges);

    // 输入顶点信息，组成顶点表

    for (i = 0; i<=G->numNodes; i++) {

        scanf("%c",&G->vexs[i]);

    }

    // 初始化邻接矩阵

    for (i = 0; i<=G->numNodes; i++) {

        for (j = 0; j<=G->numNodes; j++) {

            G->arc[i][j] = INFINITYC; // 初始化0

        }

    }

    // 输入边表数据

    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] = w;

    }

    // 打印邻接矩阵

    printf("矩阵结果\n");

       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

         顶点数：4,边数：5

         abcd

         输入边（vi,vj）上的下标i，下标j，权w

         0,1,1

         输入边（vi,vj）上的下标i，下标j，权w

         0,2,1

         输入边（vi,vj）上的下标i，下标j，权w

         0,3,1

         输入边（vi,vj）上的下标i，下标j，权w

         1,2,1

         输入边（vi,vj）上的下标i，下标j，权w

         2,3,1

         矩阵结果

         0 1 1 1

         1 0 1 0

         1 1 0 1

         1 0 1 0

*/

二、利用邻接表

同样的，邻接矩阵（顺序存储）的方式，可能会产生一些空白的空间，会造成空间的浪费，那么，我们尝试使用链式的存储。

邻接表中首先有一个一维数组，在这个一维数组中的某一个顶点数据，指向了一个链表。一维数组中的数据，类似链表中的表头。链表中的数据都是与其有着顶点的连接逻辑关系的。

假如边有权重，那么邻接表的节点可以添加一个权重。

邻接表存储的数据结构设计：

#define M 100

#define true 1

#define false 0

typedef char Element;

typedef int BOOL;

//邻接表的节点

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;

存储部分

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);

        (*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;

        //j->i

        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;

        }

    }

}

图作为一种非线性数据结构，图的存储方式相对于线性数据结构的存储是比较复杂的，弄懂图的存储对我们掌握图的数据结构有着重要意义，没有看明白的小伙伴可以到本站的数据结构和算法教程中观看更加详细的讲解。