- #include<iostream>
- #include<vector>
- #include<queue>
- using namespace std;
- struct MGraph//无向图的定义
- {
- public:
- char vexes[100];
- int arc[100][100];
- int numVexes,numEgdes;
- int visited[100];//用于记录该节点是否被访问
- };
- void DFS(MGraph &G,int i);//从单个点进行深度优先遍历
- void createMGraph(MGraph* G);//构件图
- void DFSTrave(MGraph& G);//深度优先遍历
- void BFSTrave(MGraph& G);//广度优先遍历
- int main()
- {
- MGraph G;
- createMGraph(&G);
- for(int i=0;i<G.numVexes;i++)
- {
- for(int j=0;j<G.numVexes;j++)
- cout<<G.arc[i][j]<<" ";
- cout<<endl;
- }
- BFSTrave(G);
- }
- void createMGraph(MGraph* G)
- {
- cout<<"input number of vexs and edges:";
- cin>>G->numVexes>>G->numEgdes;
- cout<<"输入节点信息:";
- for(int i=0;i<G->numVexes;i++)
- {
- cin>>G->vexes[i];
- G->visited[i]=0;
- }
- for(int i=0;i<G->numVexes;i++)
- for(int j=0;j<G->numVexes;j++)
- G->arc[i][j]=-1;
- for(int k=0;k<G->numEgdes;k++)
- {
- int i,j,w;
- cout<<"输入边<i,j>及权值w:";
- cin>>i>>j>>w;
- G->arc[i][j]=w;
- G->arc[j][i]=w;
- cout<<endl;
- }
- }
- //深度优先遍历
- void DFS(MGraph &G,int i)//对i号节点进行深度遍历
- {
- cout<<G.vexes[i]<<" ";
- G.visited[i]=1;//设置该节点已访问
- for(int j=0;j<G.numVexes;j++)
- {
- if(!G.visited[j]&&G.arc[i][j]!=-1)//如果j号未被访问且与i号联通
- {
- DFS(G,j);
- }
- }
- }
- void DFSTrave(MGraph& G)
- {
- for(int j=0;j<G.numVexes;j++) //确保所有点都被访问,包括不连通的点
- {
- if(!G.visited[j])
- DFS(G,j);
- }
- }
- void BFSTrave(MGraph& G)
- {
- queue<int>Q;
- for(int i=0;i<G.numVexes;i++)
- G.visited[i]=0;
- for(int i=0;i<G.numVexes;i++)//遍历各点,以防疏漏孤立点
- {
- if(!G.visited[i])//如果尚未被访问
- {
- G.visited[i]=1;
- cout<<G.vexes[i]<<" ";//访问并设置
- Q.push(i);//压人队列
- while(!Q.empty())// 每次循环都会把与头元素相连的元素压入队列
- {
- int k=Q.front();
- Q.pop();
- for(int j=0;j<G.numVexes;j++)
- {
- if(!G.visited[j]&&G.arc[k][j]!=-1)
- {
- G.visited[j]=1;
- Q.push(j);
- cout<<G.vexes[j]<<" ";
- }
- }
- }
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/2710201513923.html
来源: http://www.codesnippet.cn/detail/2710201513923.html