??? 大家好,图是一种复杂的结构,存储结构较复杂,下面是一个具体图的邻接矩阵存储方法示例,并实现了深度优先和广度优先遍历输出。
#include<iostream> using namespace std; const int MaxSize=10; template <class DataType> class MGraph { public: MGraph(DataType a[ ],int n,int e); //构造函数,建立具有n个顶点e条边的图 ~MGraph( ) { } //析构函数为空 void DFSTraverse(int v); //深度优先遍历图 void BFSTraverse(int v); //广度优先遍历图 private: DataType vertex[MaxSize]; //存放图中顶点的数组 int arc[MaxSize][MaxSize]; //存放图中边的数组 int vertexNum,arcNum; //图的顶点数和边数 }; template <class DataType> MGraph<DataType>::MGraph(DataType a[ ],int e) { int i,j; 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 (int k=0; k<arcNum; k++) { cout<<"请输入边的两个顶点的序号:"; cin>>i; cin>>j; arc[i][j]=1; arc[j][i]=1; } } template <class DataType> void MGraph<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); } template <class DataType> void MGraph<DataType>::BFSTraverse(int v) { int Q[MaxSize]; int front = -1,rear = -1; //初始化队列,假设队列采用顺序存储且不会发生溢出 cout << vertex[v]; visited[v] = 1; Q[++rear] = v; //被访问顶点入队 while (front != rear) //当队列非空时 { v = Q[++front]; //将队头元素出队并送到v中 for (int j = 0; j < vertexNum; j++) if (arc[v][j] == 1 && visited[j] == 0 ) { cout << vertex[j]; visited[j] = 1; Q[++rear] = j; } } } int visited[MaxSize]; int main( ) { int n,e; char ch[MaxSize]; for(int i=0;i<MaxSize;i++) visited[i]=0; cout<<"请输入顶点数和边数:"; cin>>n>>e; cout<<endl<<"请输入顶点:"; for(int i=0;i<n;i++) cin>>ch[i]; MGraph<char> MG(ch,n,e); cout<<"深度优先遍历序列是:"; MG.DFSTraverse(0); cout<<endl; for (int i=0; i<MaxSize; i++) visited[i]=0; cout<<"广度优先遍历序列是:"; MG.BFSTraverse(0); cout<<endl; system("pause"); return 0; }
运行时界面和输入如下:
请输入顶点数和边数:7? ?11
请输入顶点:A? B? C? D? E? F? G
请输入边顶点:0? 1
请输入边顶点:0 ?3
请输入边顶点:1? 3
请输入边顶点:1 ?2
请输入边顶点:1? 4
请输入边顶点:2? 4
请输入边顶点:3? 4
请输入边顶点:3? 5
请输入边顶点:4 ?5
请输入边顶点:5? 6
深度优先遍历顺序为:A B C E D F G
广度优先遍历顺序为:A B D C E F G
大家可以尝试存储其它图,也可以使用邻接表来存放。祝大家成功!
??