【数据结构】图的存储结构（邻接矩阵）

一.邻接矩阵

1.图的特点

        任何两个顶点之间都可能存在边，无法通过存储位置表示这种任意的逻辑关系。

图无法采用顺序存储结构。

2.如何存储图？

将顶点与边分开存储。

3.邻接矩阵（数组表示法）

基本思想：

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中各顶点之间的邻接关系。

假设图G有n个顶点，则它的邻接矩阵是一个n*n的方阵

4.无向图的邻接矩阵

1.特点：

无向图的邻接矩阵是一个对称矩阵，主对角线为0

2.如何求顶点i的度？

邻接矩阵的第i行非零元素的个数

3.如何判断顶点i和j之间是否存在边？

判断arc[i][j]是否为1

4.如何求顶点i的所有邻接点？

将数组中第i行元素扫描一遍，若arc[i][j]为1，则顶点j为顶点i的邻接点

5.有向图的邻接矩阵

有向完全图：任意两个顶点之间都有方向相反的弧

1.如何求顶点i的出度？

扫描第i行

2.如何求顶点i的入度？

扫描第i列

6.网图的邻接矩阵

 

二.邻接矩阵存储无向图的类

const int MAX_VERTEX=10;//图的最大顶点数
template <class T>
class MGraph{
private:T vertex[MAX_VERTEX];int arc[MAX_VERTEX][MAX_VERTEX];int vertexNum,arcNum;//实际顶点个数，边的条数
public:MGraph(T v[],int n,int e);~MGraph();void DFSTraverse(int v);void BFSTraverse(int v);
};

template<class T>
MGraph<T>::MGraph(T v[],int n,int e){int vi,vj;vertexNum=n;arcNum=e;for(int i=0;i<n;i++){vertex[i]=v[i];}for(int i=0;i<n;i++){//初始化邻接矩阵for(int j=0;j<n;j++){arc[i][j]=0;}}for(int i=0;i<e;i++){//依次输入每一条边cin>>vi>>vj;//输入边依附的两个顶点的编号arc[vi][vj]=1;arc[vj][vi]=1;}
}