图的存储结构：邻接矩阵与邻接表

图的存储结构

由于图结构比较复杂，无法用简单的顺序存储结构来表示。而多重链表的方式，即以一个数据域和多个指针域组成的结点表示图中的一个顶点，尽管可以实现图结构，但各个顶点的度数相差很大，按读数最大的顶点设计结点结构会造成很多浪费，而按照每个顶点自己的度数设计不同的顶点结构又带来操作不便，看以下存储结构。

邻接矩阵：

• 图的邻接矩阵（Adjacency Matrix）的存储方式是用两个数组来表示图，采用一维数组存储顶点信息，而边/弧采用二维数组来存储。设图G有n个顶点，则邻接矩阵是一个nxn的方阵，定义为：
  邻接矩阵
• 上图中矩阵的主对角线全为0是因为不存在顶点到自身的边，为1表示存在该顶点到另一个顶点的边。由于是无向图，若vi到vj的边不存在，则vj到vi的边也不存在，故其边数组是一个对称矩阵。
• 要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和。求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一边，为1就是邻接点。
• 对于有向图来说，其顶点数组和边数组如下：主对角线上数值依然为0，但因为是有向图，此矩阵并不对称。有向图的顶点vi入度为矩阵第i列之和，出度为第i行之和。与无向图一样，如果v[i][j]为1，则说明vi到vj存在弧，如下图所示。
  有向图的邻接矩阵

• 前面提到了网，即每条边上带有权的图叫做网，那么如何适应这个需求呢？设图G是网图，有n个顶点，则邻接矩阵是一个nxn的方阵，定义为：

  
  网图的邻接矩阵定义

• 这里Wij表示(vi,vj)或<vi,vj>上的权值，无穷大表示计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。

  
  网图的邻接矩阵

邻接矩阵优点：
直观、简单、好理解
方便检查任一对顶点间是否存在边
方便找任一顶点的所有“邻接点”
方便计算任一顶点的“度”
缺点：
不便于增加和删除顶点
浪费空间—存稀疏图（点很多而边很少）有大量无效元素，对稠密图比较合算。
浪费时间—统计稀疏图中一共有多少条边。

邻接矩阵创建代码
MGraph.h

#pragma once

typedef char VertexType;        //顶点类型
typedef int EdgeType;           //边类型
#define MAXVEX  100             //最大顶点数目
#define MAXEDGE 65536           //用65536代表无穷

typedef struct
{
    VertexType vexs[MAXVEX];    //顶点数组
    EdgeType arc[MAXVEX][MAXVEX];//边数组

    int numVertexes, numEdges;  //图中实际的顶点数和边数
}MGraph;

//创建无向网图
void CreateMGrah(MGraph& G);

//查询顶点索引
int LocateVex(MGraph G, VertexType v);

MGraph.cpp

#include "MGraph.h"
#include <iostream>

using namespace std;

//创建无向网图的邻接矩阵
void CreateMGrah(MGraph& G)
{
    cout << "请输入顶点个数和边个数:" << endl;
    cin >> G.numVertexes >> G.numEdges;

    cout << "请输入" << G.numVertexes << "个顶点：" << endl;
    for (int i = 0; i < G.numVertexes; i++)
    {
        cin >> G.vexs[i];                       //输入顶点
    }

    for (int i = 0; i < G.numVertexes; i++)
    {
        for (int j = 0; j < G.numVertexes; j++)
        {
            if (i == j)
            {
                G.arc[i][j] = 0;                
            }
            else
            {
                G.arc[i][j] = MAXEDGE;              //边初始化为无穷

            }
        }
    }

    cout << "请输入" << G.numEdges << "条边：" << endl;
    VertexType vertex1, vertex2;
    EdgeType edge;
    for (int i = 0; i < G.numEdges; i++)
    {
        cin >> vertex1 >> vertex2 >> edge;
        int m = LocateVex(G, vertex1);
        int n = LocateVex(G, vertex2);

        if (m >= 0 && n >= 0)
        {
            G.arc[m][n] = edge;
            G.arc[n][m] = edge;
        }
    }
}

//查询顶点索引
int LocateVex(MGraph G, VertexType v)
{
    for (int i = 0; i < G.numVertexes; i++)
    {
        if (v == G.vexs[i])
        {
            return i;
        }
    }
    return -1;
}

邻接表表示法

将数组与链表相结合的存储方法侧好难过为邻接表（Adjacency List）。

• 图中顶点用一个一维数组存储，也可以用单链表存储，不过数组更容易读取顶点信息。顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边的信息。

• 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以采用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

  
  无向图的邻接表
• 从图中我们知道，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储各个顶点的信息，firstedge是指针域，指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点在顶点表中的下标,next则存储指向边表中下一个结点的指针。
• 如果想知道某个顶点的度，查找这个顶点的边表中结点的个数即可，若要判断顶点vi到vj是否存在边，只需要测试顶点vi的边表中是否存在结点vj的下标j即可。若要求顶点的所有邻接点，对其边表进行遍历，得到的adjvex域对应的顶点就是邻接点。
• 若为有向图，邻接表结构是类似的。但由于有向图有方向，如果以顶点为弧尾来存储边表，则很容易得到每个顶点的出度，但有时为了便于确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi都建立一个链接为vi为弧头的表。如下图所示。
  有向图的邻接表与逆邻接表

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

  
  网图的邻接表

邻接矩阵与邻接表表示法的关系：

• 邻接表中每个链表对应邻接矩阵中的一行，链表中结点个数等于矩阵一行中非零元素的个数。
• 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。
• 邻接矩阵的空间复杂度为O(n^2),而邻接表的空间复杂度为O(n+e)。
• 用途：邻接矩阵多用于稠密图，而邻接表多用于稀疏图。

邻接表创建代码
ALGraph.h

#pragma once

#define MAXVEX 100
typedef char VertexType;        //顶点类型
typedef int EdgeType;           //边上的权值类型

struct EdgeNode                 //边表结点
{
    int adjvex;                 //邻接点域，存储该节点对应的下标

    EdgeType weight;            //存储权值，非网图不需要
    EdgeNode* next;             //下一个邻接点
};

typedef struct VertexNode
{
    VertexType data;            //顶点

    EdgeNode* firstEdge;        //边表头指针
}AdjList[MAXVEX];               //顶点数组

struct GraphAdjList
{
    AdjList adjList;            //顶点数组
    int numVertexes, numEdges;  //实际图中顶点数和边数
};

//建立无向图的邻接表结构
void CreateALGraph(GraphAdjList& G);

//根据顶点名称查找其下标
int locateVertex(GraphAdjList G, VertexType v);

ALGraph.cpp

#include "ALGraph.h"

#include <iostream>
using namespace std;

//建立无向图的邻接表结构
void CreateALGraph(GraphAdjList& G)
{
    cout << "请输入顶点个数和边个数：" << endl;
    cin >> G.numVertexes >> G.numEdges;

    cout << "请输入" << G.numVertexes << "个顶点：" << endl;
    for (int i = 0; i < G.numVertexes; i++)
    {
        cin >> G.adjList[i].data;
        G.adjList[i].firstEdge = NULL;
    }

    cout << "请输入" << G.numEdges << "条边：" << endl;

    VertexType vertex1, vertex2;
    int m, n;
    int edge;
    for (int i = 0; i < G.numEdges; i++)
    {
        cin >> vertex1 >> vertex2 >> edge;      //输入边及其依附的两个顶点

        m = locateVertex(G, vertex1);
        n = locateVertex(G, vertex2);

        if (m >= 0 && n >= 0)
        {
            //创建一个新的边结点
            EdgeNode* n1 = new EdgeNode;
            n1->weight = edge;
            n1->adjvex = n;
            n1->next = G.adjList[m].firstEdge;  //头插法插入顶点的firstedge
            G.adjList[m].firstEdge = n1;

            //由于是无向图，还需要插入到第n个顶点的边表中
            EdgeNode* n2 = new EdgeNode;
            n2->weight = edge;
            n2->adjvex = m;
            n2->next = G.adjList[n].firstEdge;
            G.adjList[n].firstEdge = n2;

        }
    }
}

//根据顶点名称查找其下标
int locateVertex(GraphAdjList G, VertexType v)
{
    for (int i = 0; i < G.numVertexes; i++)
    {
        if (v == G.adjList[i].data)
        {
            return i;
        }
    }
    return -1;
}

main.cpp

#include <iostream>
#include "MGraph.h"
#include "ALGraph.h"

using namespace std;

int main(int argc, char** argv)
{
    //1.邻接矩阵
    MGraph MG;
    CreateMGrah(MG);

    //2.邻接表
    GraphAdjList ALG;
    CreateALGraph(ALG);

    return 0;
}