基于邻接矩阵的深搜和广搜

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int MaxSize = 10;                   //图中最多顶点个数
 5 int visited[MaxSize] = { 0 };              //全局数组变量visited初始化
 6 
 7 class MGraph
 8 {
 9 public:
10     MGraph(char a[], int n, int e);     //构造函数，建立具有n个顶点e条边的图
11     ~MGraph() { };                        //析构函数
12     void DFTraverse(int v);               //深度优先遍历图
13     void BFTraverse(int v);               //广度优先遍历图
14 private:
15     char vertex[MaxSize];           //存放图中顶点的数组
16     int edge[MaxSize][MaxSize];           //存放图中边的数组
17     int vertexNum, edgeNum;              //图的顶点数和边数
18 };
19 
20 
21 MGraph ::MGraph(char a[], int n, int e)
22 {
23     int i, j, k;
24     vertexNum = n; edgeNum = e;
25     for (i = 0; i < vertexNum; i++)          //存储顶点
26         vertex[i] = a[i];
27     for (i = 0; i < vertexNum; i++)          //初始化邻接矩阵
28         for (j = 0; j < vertexNum; j++)
29             edge[i][j] = 0;
30     for (k = 0; k < edgeNum; k++)           //依次输入每一条边
31     {
32         cout << "请输入边依附的两个顶点的编号：";
33         cin >> i >> j;                       //输入边依附的两个顶点的编号
34         edge[i][j] = 1; edge[j][i] = 1;           //置有边标志
35     }
36 }
37 
38 
39 void MGraph ::DFTraverse(int v)
40 {
41     cout << vertex[v]; visited[v] = 1;
42     for (int j = 0; j < vertexNum; j++)
43         if (edge[v][j] == 1 && visited[j] == 0) DFTraverse(j);
44 }
45 
46 
47 void MGraph ::BFTraverse(int v)
48 {
49     int w, j, Q[MaxSize];                   //采用顺序队列
50     int front = -1, rear = -1;                 //初始化队列
51     cout << vertex[v]; visited[v] = 1; Q[++rear] = v;   //被访问顶点入队
52     while (front != rear)                    //当队列非空时
53     {
54         w = Q[++front];                    //将队头元素出队并送到v中
55         for (j = 0; j < vertexNum; j++)
56             if (edge[w][j] == 1 && visited[j] == 0) {
57                 cout << vertex[j]; visited[j] = 1; Q[++rear] = j;
58             }
59     }
60 }
61 
62 int main()
63 {
64     int i;
65     char ch[] = { ‘A‘,‘B‘,‘C‘,‘D‘,‘E‘ };
66     /* 测试数据六条边是：(0 1)(0 2)(0 3)(0 4)(1 2)(2 4)  */
67     MGraph MG( ch, 5, 6 );              //建立具有5个顶点6条边的无向图
68     for (i = 0; i < MaxSize; i++)
69         visited[i] = 0;
70     cout << "深度优先遍历序列是：" << endl;
71     MG.DFTraverse(0);                     //从顶点0出发进行深度优先遍历
72     cout << endl;
73     for (i = 0; i < MaxSize; i++)
74         visited[i] = 0;
75     cout << "广度优先遍历序列是：" << endl;
76     MG.BFTraverse(0);                     //从顶点0出发进行广度优先遍历
77     return 0;
78 }