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