我的公众号是【CodeAllen】，程序员技术交流①群：736386324,转载请注明出处

上一篇说的临接矩阵是不错的图存储结构，但是对于边数相对顶点较少的图，这种结构是存在对存储空间极大浪费的

因此可以考虑另外一种存储结构：比如把数组和链表结合一起来存储

 

临接表无向图的处理方法：

1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便

2.图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储

 

临接表有向图的处理方法：

以把顶点当弧尾建立的临接表，这样很容易可以得到每个顶点的出度

 

临接表网的处理方法：

对于带权值的网图，可以在边表结点定义中在增加一个数据域来存储权值即可

 

代码实现：

#define MAXVEX 100

typedef struct EdgeNode         // 边表结点
{
    int adjvex;                 // 邻接点域，存储该顶点对应的下标
    int weight;                 // 用于存储权值，对于非网图可以不需要
    struct EdgeNode *next;      // 链域，指向下一个邻接点
} EdgeNode;

typedef struct VertexNode       // 顶点表结点
{
    char data;                  // 顶点域，存储顶点信息
    EdgeNode *firstEdge;        // 边表头指针
} VertexNode, AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVertexes, numEdges;  // 图中当前顶点数和边数
} GraphAdjList;

// 建立图的邻接表结构
void CreateALGraph(GraphAdjList *G)
{
    int i, j, k;
    EdgeNode *e;

    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &G->numVertexes, &G->numEdges);

    // 读取顶点信息，建立顶点表
    for( i=0; i < G->numVertexes; i++ )
    {
        scanf("%c", &G->adjList[i].data);
        G->adjList[i].firstEdge = NULL;     // 初始化置为空表
    }

    for( k=0; k < G->numEdges; k++ )
    {
        printf("请输入边(Vi,Vj)上的顶点序号：\n");
        scanf("%d %d", &i, &j);

        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = j;                      // 邻接序号为j
        e->next = G->adjList[i].firstEdge;
        G->adjList[i].firstEdge = e;

        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = i;                      // 邻接序号为i
        e->next = G->adjList[j].firstEdge;
        G->adjList[j].firstEdge = e;
    }
}