首页 > 代码库 > 数据结构中用图的邻接矩阵的表示以及深度搜索
数据结构中用图的邻接矩阵的表示以及深度搜索
#include<iostream> using namespace std; typedef char vertextype; typedef int edgetype; #define maxvex 100 #define infinity 1000 int visited[100]; class MGraph{ public: vertextype vexs[maxvex]; edgetype arc[maxvex][maxvex]; int numvertexs,numedges;//图的顶点数目和图的边的数目 MGraph(const int &v,const int &e):numvertexs(v),numedges(e){} void creategraph();//创建图结构 void displaygraph();//显示图的结构 void DFS(int i);//深度优先遍历的子函数 void DFSTraverse(); }; void MGraph::creategraph() { cout<<"下面请输入顶点的元素类型值,输入的个数为"<<numvertexs<<endl; for(int i=0;i<numvertexs;++i) { cin>>vexs[i]; } cin.clear(); cout<<"下面请为邻接矩阵赋值,矩阵的大小为:"<<numvertexs<<"*"<<numvertexs<<endl; for(int i=0;i<numvertexs;++i) { for(int j=0;j<numvertexs;++j) { cin>>arc[i][j]; } } } void MGraph::displaygraph() { cout<<"下面输出的是顶点中的元素"<<endl; for(int i=0;i<numvertexs;++i) { cout<<vexs[i]<<" "; } cout<<endl; for(int i=0;i<numvertexs;++i) { for(int j=0;j<numvertexs;++j) { cout<<arc[i][j]<<'\t'; } cout<<endl; } } //下面定义深度优先的函数 void MGraph::DFS(int i) { int j; visited[i]=true; cout<<"深度优先输出的结点信息"<<vexs[i]<<endl; for(j=0;j<numvertexs;++j) { if(arc[i][j]==1&&!visited[j]) DFS(j); } } void MGraph::DFSTraverse() { int i; for(i=0;i<numvertexs;++i) { visited[i]=0; } for(i=0;i<numvertexs;++i) { if(!visited[i]) DFS(i); } } int main() { MGraph G(4,5); G.creategraph(); G.displaygraph(); G.DFSTraverse(); system("pause"); return 0; }
数据结构中用图的邻接矩阵的表示以及深度搜索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。