图是一种复杂的数据结构，表现在不仅各个顶点的度可以相差很多，而且顶点的逻辑关系也错综复杂。从图的定义可知，一个图包含两方面的信息：顶点的信息以及描述顶点之间关系的信息。
邻接矩阵：
也称为数组表示法，其方法是用一个一维数组存储顶点信息，用二维数组存储边的信息，这个二维数组称为邻接矩阵。
Arc[i][j]=1, if (vi,vj)属于E
Arc[i][j]=0, if (vi,vj)不属于E
若为网图
Arc[i][j]=wij, if (vi,vj)属于E
Arc[i][j]=0, if i=j
Arc[i][j]=∞, 否则
其中，wij表示权值，∞表示一个计算机允许的、大于所有边的权值的数
显然，无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵则不一定对称
优点：在邻接矩阵中容易解决下列问题：
1. 对于无向图，顶点的度等于邻接矩阵第i行或第i列的非零元素的个数。对于有向图，顶点i的出度为第i行的非零元素的个数，入度为第i列非零元素的个数
2. 要判断i和j之间是否存在边，仅需要判断邻接矩阵中相应的元素Arc[i][j]
3. 要找顶点的所有邻接点，可以依次判断顶点与其他顶点是否有边或弧
算法：
const int maxsize=10;
templete <class datatype>
class mGraph
{
public:
mGraph(datatypea[],int n,int e);//constructor, n nodes, e edges
~mGraph(){}; //empty destructor
void DFSTraverse(intv); //depth-first travel
void BFSTraverse(intv); //breadth-first travel
private:
datatypevertex[maxsize]; //node array
intarc[maxsize][maxsize]; //edge array
int vertexnum,arcnum; //number of nodes andedges
} ;
构造函数：
Pseudocode：
1. 确定图的顶点个数和边的个数
2. 输入顶点信息储存在一维数组中
3. 初始化邻接矩阵
4. 依次输入每条边储存在邻接矩阵中
（1） 输入两个顶点i,j
（2） Arc[i][j]=1，Arc[j][i]=1;
C++：
templete <class datatype>
mGraph<datatype>::mGraph(datatypea[],int n,int e)
{
vertexnum=n;arcnum=e;
for(int i=0;i<vertexnum;i++)
{
vertex[i]=a[i];
}
for(inti=0;i<vertexnum;i++)
for(intj=0;j<vertexnum;j++)
{
arc[i][j]=0;
}
for(inti=0;i<arcnum;i++)
{
cin>>i>>j;
arc[i][j]=1;
arc[j][i]=1;
}
}
深度优先遍历：（伪代码已经在前面的文章中提及，下有链接）http://blog.csdn.net/qq_36642226/article/details/74855911
C++：
templete <class datatype>
voidmGraph<datatype>::DFSTraverse(int v)
{
cout<<vertex[v];
visited[v]=1;
for(int j=0;j<vertexnum;j++)
{
if(arc[v][j]==1&&visited[j]==0)
DFSTraverse(j);
}
}
广度优先遍历：（伪代码已经在前面的文章中提及，下有链接）http://blog.csdn.net/qq_36642226/article/details/74855911
C++：
templete <class datatype>
void mGraph<datatype>::BFSTraverse(int v)
{
front=rear=-1;
cout<<vertex[v];
visited[v]=1;
Q[++rear]=v;//queue
while(front!=rear)
{
v=Q[++front];
for(intj=0;j<vertexnum;j++)
if(arc[v][j]==1&&visited[j]==00)
{
cout<<vertex[j];
visited[j]=1;
Q[++rear]=j;
}
}
}