图的存储结构：

邻接矩阵存储

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

无向图

算法与数据结构（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[难]