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

一.邻接矩阵

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