邻接矩阵存储无向图的类
const int MaxSize=10;
template <class T>
class Mgraph{
public:
MGraph(T a[ ], int n, int e );
~MGraph( )
void DFSTraverse(int v);
void BFSTraverse(int v);
……
private:
T vertex[MaxSize];
int arc[MaxSize][MaxSize];
int vertexNum, arcNum;
};
邻接矩阵中图的基本操作——构造函数
MGraph(T a[ ], int n, int e );
1.确定图的顶点个数和边的个数;
2.输入顶点信息存储在一维数组vertex中;
3.初始化邻接矩阵;
4.依次输入每条边存储在邻接矩阵arc中;
4.1 输入边依附的两个顶点的序号i, j;
4.2 将邻接矩阵的第i行第j列的元素值置为1;
4.3 将邻接矩阵的第j行第i列的元素值置为1;
template <class T>
MGraph::MGraph(T a[ ], int n, int e) {
vertexNum=n;
arcNum=e;
for (i=0; i<vertexNum; i++)
vertex[i]=a[i];
for (i=0; i<vertexNum; i++) //初始化邻接矩阵
for (j=0; j<vertexNum; j++)
arc[i][j]=0;
for (k=0; k<arcNum; k++) {
cin>>i>>j; //边依附的两个顶点的序号
arc[i][j]=1;
arc[j][i]=1; //置有边标志
}
}
深度优先遍历
⑴ 访问顶点v;
⑵ 从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;
⑶ 重复上述两步,直至图中所有和v有路径相通的顶点都被访问到。
int visited[MaxSize];
template <class T>
void MGraph::DFSTraverse(int v){
cout<<vertex[v];
visited [v]=1; // 已经输出了
for (j=0; j<vertexNum; j++)
if (arc[v][j]==1 && visited[j]==0)
DFSTraverse( j );
}
广度优先遍历
⑴ 访问顶点v;
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk;
⑶ 分别从v1,v2,…,vk出发依次访问它们未被访问的邻接点,并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。
----直至图中所有与顶点v有路径相通的顶点都被访问到。
int visited[MaxSize];
template <class T>
void MGraph::BFSTraverse(int v){
front=rear=-1;
cout<<vertex[v];
visited[v]=1;
Q[++rear]=v;
while (front!=rear)
{
v=Q[++front];
for (j=0; j<vertexNum; j++)
if (arc[v][j]==1 && visited[j]==0 ) {
cout<<vertex[j];visited[j]=1;
Q[++rear]=j;
}
}
}