数据结构连通图.docVIP

邻接矩阵 邻接矩阵 1 MGraph.h #include iostream using namespace std; const int MaxSize=10; //邻接矩阵存储无向图的类 template class DataType class MGraph { public: MGraph(DataType a[ ], int n, int e ); ~MGraph( ){ }; void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int visited[MaxSize]; int vertexNum, arcNum; }; //构造函数 template class DataType MGraphDataType :: MGraph(DataType a[ ], int n, int e) { int i,j,k; vertexNum = n; arcNum = e; for (i = 0; i vertexNum; i++) vertex[i] = a[i]; for(i = 0; i vertexNum; i++) //初始化邻接矩阵 for(j = 0; jvertexNum; j++) arc[i][j] =0; cout依次输入每一条边endl; for ( k = 0; k arcNum; k++) //依次输入每一条边 { cin i j; //输入边依附的两个顶点的编号 arc[i][j] = 1; arc[j][i] = 1; //置有边标志 } cout\n输出邻接矩阵endl; for(i = 0; i vertexNum; i++) //初始化邻接矩阵 { for(j = 0; jvertexNum; j++) cout\tarc[i][j]; coutendl; } for (j = 0; j vertexNum; j++)visited[j] = 0; }; //深度优先遍历无向连通图 template class DataType void MGraphDataType :: DFSTraverse(int v) { int j; visited[v] = 1; cout vertex[v]; for (j = 0; j vertexNum; j++) if (arc[v][j] == 1 visited[j] == 0) DFSTraverse( j ); }; //广度优先遍历无向连通图 template class DataType void MGraphDataType :: BFSTraverse(int v) { int Q[MaxSize]; int front,rear,j; front = rear = -1; //初始化顺序队列 for (j = 0; j vertexNum; j++)visited[j] = 0; cout vertex[v]; visited[v] = 1; Q[++rear] = v; while (front != rear) //当队列非空时 { v = Q[++front]; //将队头元素出队并送到v中 for (j = 0; j vertexNum; j++) if (arc[v][j] == 1 visited[j] == 0 ) { cout vertex[j]; visited[j] = 1; Q[++rear] = j; } } for (j = 0; j vertexNum; j++)visited[j] = 0; }; #include MGraph.h void main() { char a[]={0,1,2,3,4,5}; MGraph char ta(a,6,6); cout广度优先遍历endl; ta.BFSTraverse(0); cout\n深度优先遍历endl; ta.