# 数据结构之DFS与BFS

2018/04/29 13:35

  1 #include "stdafx.h"
2 #include<iostream>
3 #include<string>
4 using namespace std;
5 #define MAX 30
6 #define MVNum 100
7 #define ERROR 1
8 typedef char VerTexType;
9 typedef int Status;
10 typedef int QElemType;
11 #define MAXSIZE 100
12 #define OK 1
13 #define ERROR 0
14 #define OVERFLOW -2
15 typedef struct ArcNode                 //边结点
16 {
18     struct ArcNode *nextarc;           //指向下一条边的指针
19     string info;                       //和边相关的信息
20 }ArcNode;
21 typedef struct VNode                   //顶点信息
22 {
23     VerTexType data;
26 typedef struct                         //邻接表
27 {
28     VNode xlist[MAX];
29     int vexnum, arcnum;                //图的当前顶点数和边数
30 }ALGraph;
31
32 typedef struct Node                    //构造队列
33 {
34     int data;
35     struct Node *next;
36 }Node,*QNode;
37 typedef struct
38 {
39     QNode front;                       //队头指针
40     QNode rear;                        //对尾指针
41 }Queue;
42 Status InitQueue(Queue &Q)             //初始化队列
43 {
44     Q.front = Q.rear=new Node;         //生成新节点作为头节点，对头和队尾指针指向此节点
45     if (!Q.front)
46         exit(OVERFLOW);
47     Q.front->next = NULL;               //头结点的指针域置空
48     return OK;
49 }
50
51 Status EnQueue(Queue &Q, int e)        //入队操作
52 {
53     QNode p = new Node;
54     if (!p)                            //存储分配失败
55         exit(OVERFLOW);
56     p->data = e;
57     p->next = NULL;
58     Q.rear->next = p;
59     Q.rear = p;                        //把当前的p设置尾对尾节点，rear指向p
60     return OK;
61 }
62
63 Status DeQueue(Queue &Q, int &e)       //出队操作
64 {
65     QNode p;
66     p = Q.front->next;                 //将欲删除的对头结点暂存给p
67     Q.front->next = p->next;           //将原队头节点后继p->next赋值给头结点后继
68     if (Q.rear == p)                   //如果队头是队尾，则删除后将rear指向头节点
69         Q.rear = Q.front;
70     e = p->data;                       //将欲删除的对接点赋值给e
71     delete p;
72     return OK;
73 }
74
75 Status QueueEmpty(Queue Q)             //队列判空
76 {
77     if (Q.rear == Q.front)
78         return 1;
79     else
80         return 0;
81 }
82
83 int LocateVex(ALGraph &G, char &v)     //定位函数
84 {
85     int i;
86     for (i = 0; i < G.vexnum; i++)
87     {
88         if (G.xlist[i].data == v)
89             return i;
90     }
91     if (i >= G.vexnum)
92         return ERROR;
93     else
94         return 0;
95 }
96 void CreateUDG(ALGraph &G)             //创建无向图
97 {
98     ArcNode *p1, *p2;
99     int i, j, k;
100     char v1, v2;
101     cout << "请输入图的顶点数、边数：" << endl;
102     cin >> G.vexnum >> G.arcnum;       //输入总顶点数，总边数
103     cout << "请输入顶点的值:(顶点之间用空格分离)" << endl;
104     for (i = 0; i < G.vexnum; i++)
105     {
106         cin >> G.xlist[i].data;        //输入顶点值
108     }
109     cout << "请输入弧尾和弧头：" << endl;
110     for (k = 0; k < G.arcnum; k++)
111     {
112         cin >> v1 >> v2;               //输入各边，构造邻接表
113         i = LocateVex(G, v1);
114         j = LocateVex(G, v2);
115         p1 = new ArcNode;              //生成一个新结点*p1
119         p2 = new ArcNode;
123     }
124     cout << "图构建成功！" << endl<<endl;
125 }
126
127 static bool visited[MAX];              //访问过visited，为1否则为0
128
129 void DFS(ALGraph G, int m)             //深度优先搜索
130 {
131     visited[m] = true;                 //标记已经遍历过
132     cout << G.xlist[m].data<<" ";
134     while (p)
135     {
138         p = p->nextarc;
139     }
140 }
141
142 void BFS(ALGraph G,int n)              //广度优先搜索
143 {
144     ArcNode *p;
145     Queue Q;
146     for (int i = 0; i < G.vexnum; i++)
147         visited[i] = false;
148     InitQueue(Q);
149     for (int i = 0; i < G.vexnum; i++)
150     {
151         if (!visited[i])
152         {
153             visited[i] = true;
154             cout << G.xlist[i].data<<" ";
155             EnQueue(Q, i);
156             while (!QueueEmpty(Q))
157             {
158                 DeQueue(Q, i);
160                 while (p)
161                 {
163                     {
167                     }
168                     p = p->nextarc;    //指针指向下一个邻接点
169                 }
170             }
171         }
172     }
173 }
174
175 void coutGraphD(ALGraph G)             //深搜输出函数
176 {
177     for (int i = 0; i < G.vexnum; i++)
178         visited[i] = false;
179     cout << "深度优先搜索输出的顶点的结果为:" << endl;
180     for (int i = 0; i < G.vexnum; i++)
181         if (!visited[i])
182             DFS(G, i);
183     cout << endl;
184 }
185 void coutGraphW(ALGraph G)             //广搜输出函数
186 {
187     for (int i = 0; i < G.vexnum; i++)
188         visited[i] = false;
189     cout << "广度优先搜索输出的顶点的结果为:" << endl;
190     for (int i = 0; i < G.vexnum; i++)
191         if (!visited[i])
192             BFS(G, i);
193     cout << endl;
194
195 }
196 int main()
197 {
198     ALGraph MG;
199     CreateUDG(MG);
200     coutGraphD(MG);
201     coutGraphW(MG);
202     return 0;
203 }

0
0 收藏

0 评论
0 收藏
0