1 #include "stdafx.h"
2 #include <iostream>
3 #include <queue>
4
5 using namespace std;
6
7 typedef char VertexType;
8 typedef int EdgeType;
9 const int MAXVEX = 100;
10 const int INFINITY = 65535;
11
12 class MGraph
13 {
14 public:
15 VertexType vex[MAXVEX];//顶点表
16 EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵,可看做边表
17 int numVertexes,numEdges;//图中当前的顶点数和边数
18 };
19
20
21 //创建无向网图
22 void CreateMGraph(MGraph &G)
23 {
24 int i,j,k,w;
25 cout<<"输入顶点数和边数"<<endl;
26 cin>>G.numVertexes>>G.numEdges;
27 for(i = 0;i!=G.numVertexes;i++)
28 cin>>G.vex[i];
29 for(i = 0;i!=G.numVertexes;i++)
30 for(j = 0;j<G.numVertexes;j++)
31 G.arc[i][j]=INFINITY;
32 for(k = 0;k!=G.numEdges;k++)
33 {
34 cout<<"输入边(vi,vj)上的下标i和j,以及权w"<<endl;
35 cin>>i>>j>>w;
36 G.arc[i][j]=w;
37 G.arc[j][i]=G.arc[i][j];
38 }
39 }
40
41 bool visited[MAXVEX];
42 //邻接矩阵的深度优先递归算法
43 void DFS(MGraph G,int i )
44 {
45 visited[i]=true;
46 cout<<G.vex[i];
47 for(int j = 0;j!=G.numVertexes;j++)
48 {
49 if(G.arc[i][j] ==1 && !visited[j])
50 DFS(G,j);
51 }
52 }
53 //邻接矩阵的深度遍历操作
54
55 void DFSTraverse(MGraph G)
56 {
57 int i ;
58 for(i = 0;i!=G.numVertexes;i++)
59 {
60 visited[i] = false;//初始化所有的顶点都是没有被访问过的.
61 }
62 for(i = 0;i!=G.numVertexes;++i)
63 {
64 if(!visited[i]) //这里是对没有访问的顶点进行深度遍历调用,如果图是连通图.for循环只执行一遍.
65 DFS(G,i);
66 }
67 }
68
69
70 //广度优先遍历
71 void BFSTraverse(MGraph G)
72 {
73 int i,j;
74 queue<int> Q;
75 for(i = 0;i<G.numVertexes;++i)
76 visited[i] = false;
77 for(i = 0;i!=G.numVertexes;++i)
78 {
79 if(!visited[i])
80 {
81 visited[i]= true;
82 cout<<G.vex[i]<<endl;
83 Q.push(i);
84 while(!Q.empty())
85 {
86 i = Q.front();
87 Q.pop();
88 for(j=0;j!=G.numVertexes;j++)
89 {
90 if(G.arc[i][j] == 1&& !visited[j])
91 {
92 visited[j]=true;
93 cout<<G.vex[j]<<endl;
94 Q.push(j);
95 }
96 }
97 }
98 }
99 }
100 }
101 int _tmain(int argc, _TCHAR* argv[])
102 {
103
104 return 0 ;
105 }