一、基本概念
邻接矩阵(Adjacency Matrix)的存储结构,就是用一维数组存储图中顶点的信息,用一个二维数组表示图中各顶点之间的邻接关系信息。这个二维数组称为邻接矩阵。假设图G = (V, E)
有 n 个确定的顶点,即 V = {v0,v1,…,vn−1},则表示 G 中各顶点相邻关系为一个 n×n
的矩阵,矩阵的元素为:
若G是带权图,则邻接矩阵可定义为:
其中,wij 表示边(vi,vj)或弧 <vi,vj> 上的权值;∞ 表示一个计算机允许的、大于所有边上权值的数。
用邻接矩阵表示法表示无向图:
用邻接矩阵表示法表示带权图:
二、邻接矩阵存储的特点
-
无向图的邻接矩阵一定是一个对称矩阵。因此,在具体存放邻接矩阵时,只需存放上(或下)三角矩阵的元素即可。有向图的邻接矩阵不一定是对称矩阵。
-
对于无向图,邻接矩阵的第 i 行(或第 i 列)非零元素(或非 ∞ 元素)的个数正好是第 i 个顶点的度 D(vi)。
-
对于有向图,邻接矩阵的第 i 行(或第 i 列)非零元素(或非 ∞ 元素)的个数正好是第 i 个顶点的出度 OD(vi)(或入度 ID(vi))。
-
用邻接矩阵方法存储图,很容易确定图中任意两个顶点之间是否有边相连。但是,要确定图中有多少条边,则必须按行、列对每个元素进行检测,所花费的时间代价很大。这是用邻接矩阵存储图的局限性。
-
在邻接矩阵表示法中,如果是顶点很多而边很少的图,将会表示成一个稀疏矩阵。这不仅浪费空间,而且使一些算法变得很慢。
三、图的邻接矩阵存储表示
在用邻接矩阵存储图时,除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外,还需用一个一维数组存储顶点信息,另外还有图的顶点数和边数。故可将其形式描述如下:
typedef int VertexType;
typedef int Edgetype;
#define MaxVertexNum 30
class MGraph {
public:
MGraph(); //默认构造函数
MGraph::~MGraph(); //默认析构函数
void CreatGraph(); //建立图的存储矩阵成员函数
void Visit(int v);
void MGraph::BFStraverse(); //广度遍历图
void MGraph::BFS(int v); //从顶点 v 开始广度遍历图
int MGraph::MaxOutdegree();
//以邻接矩阵为存储结构,判断 vi 和 vj 之间是否有路径,
//若有,返回 1,否则返回 0
int MGraph::IsPath_DFS(int i, int j);
//以邻接矩阵为存储结构,判断 vi 和 vj 之间是否有路径,
//若有,返回 1,否则返回 0
int MGraph::IsPath_BFS(int i, int j);
void Init_Visit_Flag(); //初始化访问数组标志
private:
VertexType vertexs[MaxVertexNum]; //顶点表
Edgetype arcs[MaxVertexNum][MaxVertexNum]; //邻接矩阵,即边表
int vertexNum, edgeNum; //顶点数和边数
int visited[MaxVertexNum]; //访问标志数组
};
其中,建立一个图的邻接矩阵存储的算法如下:
//建立有向图 G 的邻接矩阵存储
void MGraph::CreatGraph() {
int i, j, k;
cin >> vertexNum >> edgeNum; //输入顶点数和边数
for(i=0; i < vertexNum; i++)
cin >> vertexs[i]; //输入顶点信息, 建立顶点表
for(i = 0; i < vertexNum; i++)
for(j = 0; j < vertexNum; j++)
arcs[i][j]=0; //初始化邻接矩阵
for(k=0; k < edgeNum; k++) {
cin >> i >> j; //输入 e 条边, 建立邻接矩阵
arcs[i][j] = 1; //若加入arcs[j][i]=1, 则为无向图的邻接矩阵存储建立
}
}
对于带权图邻接矩阵的建立方法是:首先将矩阵的每个元素都初始化。如果 i = j
,则使 arcs[i][j] = 0
,否则为 ∞(若图的权值为整数,则定义为最大整数;若为实数,则定义为最大实数)。然后读入边及权值(i,j,wij),将矩阵的相应元素置为 wij。