在線性表中，數據元素之間是被串起來的，僅有線性關系，每個數據元素只有一個直接前驅和一個直接后繼；在樹形結構中，數據元素之間有著明顯的層次關系，并且每一層上的數據元素可能和下一層中多個元素相關，但只能和上一層中一個元素相關；在圖形結構中，是由頂點的有窮非空集合和頂點之間邊的集合組成，如果兩個頂點之間存在一條邊，那么就表示這兩個頂點具有相鄰關系。通常表示為：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;

        }

    }

}

圖作為一種非線性數據結構，圖的存儲方式相對于線性數據結構的存儲是比較復雜的，弄懂圖的存儲對我們掌握圖的數據結構有著重要意義，沒有看明白的小伙伴可以到本站的數據結構和算法教程中觀看更加詳細的講解。