一、邻接矩阵存储结构

二、邻接表存储结构

示例：

1、定义结构

#define elementType QChar
#define MAXV 5

//边结点
struct ArcNode
{
    elementType advex;                      //终点编号
    struct ArcNode * nextarc{nullptr};      //指向下一条边的指针
    QJsonObject info;                       //该边的权值等信息
};

//头结点类型
struct VNode
{
    elementType data;                   //顶点信息
    ArcNode * firstarc{nullptr};		//指向第一条边
};

//图的邻接表类型
struct AdjGraph
{
    VNode adjlist[MAXV];       //邻接表
    int arcnode_number;         //边数
};

2、创建邻接表

//创建图的邻接表
void CreateAdj(AdjGraph * & G,
               int A[MAXV][MAXV],
               elementType nodeName[MAXV],
               int arcnode_number)
{
    G = new AdjGraph;
    for (int i = 0;i < MAXV;++i)
    {
        for (int j = MAXV - 1;j >= 0;--j)
        {
            if (A[i][j] != 0)	 //存在一条边
            {
                ArcNode * p = new ArcNode;
                p->advex = nodeName[j];			 //存放邻接点
                p->nextarc = G->adjlist[i].firstarc;  //采用头插法插入结点p
                G->adjlist[i].firstarc = p;
            }
        }
        G->adjlist[i].data = nodeName[i];
    }
    G->arcnode_number = arcnode_number;
}

3、输出邻接表

//输出邻接表G
void DispAdj(AdjGraph *G)	
{
    for (int i = 0;i < MAXV;++i)
    {
        ArcNode * p = G->adjlist[i].firstarc;
        QString str;
        while (p)
        {
            str.append(p->advex).append(" - ");
            p = p->nextarc;
        }
        qDebug()<<G->adjlist[i].data<<" - "<<str;
    }
}

4、销毁邻接表

//销毁邻接表
void DestroyAdj(AdjGraph *& G)   
{
    for (int i = 0;i < MAXV;++i)
    {
        if (ArcNode * pre = G->adjlist[i].firstarc)//指向第i个单链表的首结点
        {
            ArcNode * p = pre->nextarc;
            while (p)
            {
                delete pre;
                pre = p;
                p = p->nextarc;
            }
            delete pre;
        }
    }
    delete G;
    G = nullptr;
}

5、使用

    int arr[MAXV][MAXV] = {{0,1,0,1,1},
                           {1,0,1,1,0},
                           {0,1,0,1,1},
                           {1,1,1,0,1},
                           {1,0,1,1,0}};
    AdjGraph * G{nullptr};
    elementType nodeName[MAXV] = {'A','B','C','D','E'};
    CreateAdj(G,arr,nodeName,8);
    DispAdj(G);
    DestroyAdj(G);