圖的存儲結構：

鄰接矩陣存儲

圖的鄰接矩陣存儲方式是用兩個數組來表示圖。一個一維數組存儲圖中頂點資訊，一個二維數組（鄰接矩陣）存儲圖中的邊或弧的資訊。

無向圖

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

從上面可以看出，無向圖的邊數組是一個對稱矩陣。所謂對稱矩陣就是n階矩陣的元滿足aij = aji。即從矩陣的左上角到右下角的主對角線為軸，右上角的元和左下角相對應的元全都是相等的。

從這個矩陣中，很容易知道圖中的資訊。

要判斷任意兩頂點是否有邊無邊就很容易了；
要知道某個頂點的度，其實就是這個頂點vi在鄰接矩陣中第i行或（第i列）的元素之和；
求頂點vi的所有鄰接點就是将矩陣中第i行元素掃描一遍，arc[i][j]為1就是鄰接點；

有向圖

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

有向圖講究入度和出度，頂點vi的入度為1，正好是第i列各數之和。頂點vi的出度為2，即第i行的各數之和。

若圖G是網圖，有n個頂點，則鄰接矩陣是一個n*n的方陣，定義為：

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

這裡的wij表示(vi,vj)上的權值。無窮大表示一個計算機允許的、大于所有邊上權值的值，也就是一個不可能的極限值。

代碼實作

// 頂點的類型
typedef char Vertex;
// 邊上的權值類型
typedef int EdgeWeight;
// 表示最大的頂點數量
#define MAXVN 100
// 表示無窮
#define INFINITY 65535

// 定義無向網圖的鄰接矩陣結點
typedef struct {
    // 頂點集合
    Vertex vexs[MAXVN];
    // 邊的集合
    EdgeWeight arc[MAXVN][MAXVN];
    // 頂點數量與邊的數量
    int edgeNum,vertexNum;
}MGraph;

/* 建立無向網圖的鄰接矩陣表示 */
void CreateMGraph(MGraph *G) {
    int i,j,k,w;
    printf("輸入頂點數和邊數:");
    scanf("%d,%d",&G->vertexNum,&G->edgeNum);

    for(i = 0; i < G->vertexNum; i++) {
        printf("\n輸入第%d個頂點:", i);
        scanf("%d",&G->vexs[i]);
    }

    for(i = 0; i < G->vertexNum; i++) {
        for(j = 0; j < G->vertexNum; j++) {
            G->arc[i][j] = INFINITY;
        }
    }
    /* 讀入edgeNum條邊，建立鄰接矩陣 */
    for(k = 0; k < G->edgeNum; k++) {
        printf("輸入邊(vi,vj)上的下标i，下标j和權w:\n");
        /* 輸入邊(vi,vj)上的權w */
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j] = w;
        /* 因為是無向圖，矩陣對稱 */
        G->arc[j][i] = G->arc[i][j];
    }
}

鄰接表存儲方式

是對鄰接矩陣的優化，對于邊數量相對頂點較少的圖，這種結構是存在對存儲空間的極大浪費的。

圖中頂點用一個一維數組存儲，當然，頂點也可以用單連結清單來存儲，不過數組可以較容易地讀取頂點資訊，更加友善。另外，對于頂點數組中，每個數組元素還需要存儲指向第一個鄰接點的指針，以便于查找該頂點的邊資訊。
圖中每個頂點Vi的所有鄰接點構成一個線性表，由于鄰接點的個數不定，是以用單連結清單存儲，無向圖稱為頂點Vi的邊表，有向圖稱為頂點Vi作為弧尾的出邊表。

對于無向圖：

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

對于有向圖：

由于有向圖有方向，鄰接表是以頂點為弧尾來存儲邊表的，這樣就很容易得到每個頂點的出度，但是要确定頂點的入度或以頂點為弧頭的弧，還需要建立一個有向圖的逆鄰接表，對每個頂點Vi都建立一個連結為Vi為弧頭的表。

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

代碼實作：

// 頂點的類型
typedef char Vertex;
// 邊上的權值類型
typedef int EdgeWeight;
// 表示最大的頂點數量
#define MAXVN 100
// 表示無窮
#define INFINITY 65535

/*
一個頂點就存有結點的值以及第一條邊的資訊

一個邊結點存儲的就是邊的資訊（記錄邊的另一個頂點，邊描述的是兩個結點之間的資訊嘛），下一條邊的資訊和infomation（像是權值這些啦）
*/

// 邊表結構
typedef struct EdgeNode{
    // 鄰接點域（某結點的鄰接點的在頂點表中下标索引）
    int adjvex;
    // 指向下一條邊
    struct EdgeNode *next;
    // 權值，對于非網圖可以不要
    EdgeWeight weight;
}EdgeNode;
// 頂點表結構
typedef struct VertexNode{
    // 第一條邊
    EdgeNode *firstedge;
    // 頂點資訊。
    Vertex data;
}VertexNode,AdjList[MAXVN];
// 圖的結構
typedef struct{
    // 頂點數量與邊的數量
    int edgeNum,vertexNum;
    AdjList adjList;
}MLGraph;


void CreateMLGraph(MLGraph *G);

建立一個鄰接表存儲結構的無向圖：

void CreateMLGraph(MLGraph *G) {
    int i,j,k;
    EdgeNode *e;

    printf("輸入頂點數和邊數:");
    scanf("%d,%d",&G->vertexNum,&G->edgeNum);
    
    for(i = 0; i < G->vertexNum; i++) {
        //清空緩存，因為%c不會跳過空格等空字元
        fflush(stdin);

        printf("\n輸入第%d個頂點:", i);
        scanf("%c",&G->adjList[i].data);
        G->adjList[i].firstedge = NULL;
    }

    /* 建立邊表 */
    for(k = 0; k < G->edgeNum; k++) {
        printf("輸入邊(vi,vj)上的頂點序号:");
        scanf("%d,%d",&i,&j);
        
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        
        /* 邊結點e作為頂點的第一條邊。就和單連結清單的頭插法是一樣的。 */
        
        /* 鄰接序号為j */
        e->adjvex = j;
        /* 将e的指針指向目前頂點上指向的結點 */
        e->next = G->adjList[i].firstedge;
        /* 将頂點i的指針指向e */
        G->adjList[i].firstedge = e;

        /* 因為是無向圖，對另一個頂點i操作 */
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->next = G->adjList[j].firstedge;
        G->adjList[j].firstedge = e;
    }
}

十字連結清單

對于有向圖來說，鄰接表是有缺陷的，入度和出度。關心了出度問題，想了解入度就必須周遊整個圖，反之，逆鄰接表解決了入度卻不了解出度的情況。十字連結清單就是将它們整合一起将問題很好的解決。

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

代碼實作：

// 頂點的類型
typedef char Vertex;
// 邊上的權值類型
typedef int EdgeWeight;
// 表示最大的頂點數量
#define MAXVN 100
// 表示無窮
#define INFINITY 65535


// 邊表結構
typedef struct ArcNode{
    // 頭的頂點的位置
    int headvex;
    // 尾的頂點的位置
    int tailvex;

    // 出度的下一條邊，以目前結點為弧尾
    struct ArcNode *taillink;
    // 入度的下一條邊，以目前結點為弧頭
    struct ArcNode *headlink;
    // 權值，對于非網圖可以不要
    EdgeWeight weight;
}ArcNode;
// 頂點表結構
typedef struct VertexNode{
    // 表示出度
    ArcNode *firstin;
    // 表示入度
    ArcNode *firstout;
    // 頂點資訊。
    Vertex data;
}VertexNode,XList[MAXVN];
// 圖的結構
typedef struct{
    // 頂點數量與邊的數量
    int arcNum,vertexNum;
    XList xList;
}XGraph;

void CreateXGraph(XGraph *G) {
    int i,j,k;
    ArcNode *t;
    printf("輸入頂點數和邊數:");
    scanf("%d,%d",&G->vertexNum,&G->arcNum);
    for(i = 0; i < G->vertexNum; i++) {
        //清空緩存，因為%c不會跳過空格等空字元
        fflush(stdin);

        printf("\n輸入第%d個頂點:", i);
        scanf("%c",&G->xList[i].data);
        G->xList[i].firstin = NULL;
        G->xList[i].firstout = NULL;
    }

    for(k = 0; k < G->arcNum; k++) {
        printf("\n輸入第%d條邊<vi,vj>上的頂點序号:", k + 1);
        scanf("%d,%d",&i,&j);
        t = (ArcNode*)malloc(sizeof(ArcNode));
        t->tailvex = i;
        t->headvex = j;
        t->taillink = G->xList[i].firstout;
        t->headlink = G->xList[i].firstin;
        G->xList[i].firstout = G->xList[j].firstin = t;
    }

}

運作結果：

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

鄰接多重表

說回鄰接表，對于無向圖的存儲，也存在小問題。對于同一條邊的存儲是可能有重複的（強迫症表示不能忍），可以往上面翻，看無向圖的鄰接表存儲方式部分的圖檔。

改造後就成下圖所示：

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

代碼實作

// 頂點的類型
typedef char Vertex;
// 邊上的權值類型
typedef int EdgeWeight;
// 表示最大的頂點數量
#define MAXVN 100
// 表示無窮
#define INFINITY 65535


// 邊表結構
typedef struct EdgeNode {
    // ivex,jvex是某條邊依附的兩個頂點在頂點表中的下标。
    int ivex,jvex;

    // ilink指向依附頂點ivex的下一條邊，jlink指向依附頂點jvex的下一條邊
    struct EdgeNode *ilink;
    struct EdgeNode *jlink;

    // 權值，對于非網圖可以不要
    EdgeWeight weight;
}EdgeNode;

// 頂點表結構
typedef struct VertexNode{
    // 第一條邊
    EdgeNode *firstedge;
    // 頂點資訊。
    Vertex data;
}VertexNode,Adjmulist[MAXVN];

// 圖的結構
typedef struct{
    // 頂點數量與邊的數量
    int edgeNum,vertexNum;
    Adjmulist adjmulist;
}AMLGraph;

void CreateAMLGraph(AMLGraph *G) {
    int i,j,k;
    EdgeNode *t;

    printf("請輸入頂點的數量以及邊的數量：");
    scanf("%d,%d",&G->vertexNum,&G->edgeNum);

    for(i = 0; i < G->vertexNum; i++) {
        fflush(stdin);

        printf("請輸入第%d個頂點：", i+1);
        scanf("%c", &G->adjmulist[i].data);
        G->adjmulist[i].firstedge = NULL;
    }

    for(k = 0; k < G->edgeNum; k++) {

        printf("輸入第%d條邊(vi,vj)上的頂點序号:", k + 1);
        scanf("%d,%d",&i,&j);

        if(i < 0 || j < 0) {
            exit(ERROR);
        }
        if(!(t = (EdgeNode*)malloc(sizeof(EdgeNode)))) {
            exit(ERROR);
        }

        t->ivex = i;
        t->jvex = j;

        t->ilink = G->adjmulist[i].firstedge;
        G->adjmulist[i].firstedge = t;

        t->jlink = G->adjmulist[j].firstedge;
        G->adjmulist[j].firstedge = t;
    }
}

運作效果：

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

算法與資料結構（c語言）——圖（Figure，二）：存儲結構圖的存儲結構：

圖的存儲結構：

鄰接矩陣存儲

鄰接表存儲方式

十字連結清單

鄰接多重表

繼續閱讀

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

200. 島嶼的個數（深度優先搜尋）

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]