深度搜索（DFS） and  广度搜索（BFS）

代码如下:

1 #include "stdafx.h"  2 #include
     
        3 #include
      
         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 { 17     int adjvex;                        //改变所指向的顶点的位置 18     struct ArcNode *nextarc;           //指向下一条边的指针 19     string info;                       //和边相关的信息 20 }ArcNode; 21 typedef struct VNode                   //顶点信息 22 { 23     VerTexType data; 24     struct ArcNode *link;              //指向第一条依附该顶点的边的指针 25 }VNode;                                //AdList表示邻接表类型 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;        //输入顶点值107         G.xlist[i].link = NULL;        //初始化表头结点的指针域为NULL108     }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;              //生成一个新结点*p1116         p1->adjvex = j;                //邻接点序号为j117         p1->nextarc = G.xlist[i].link;118         G.xlist[i].link = p1;119         p2 = new ArcNode;120         p2->adjvex = i;121         p2->nextarc = G.xlist[j].link;122         G.xlist[j].link = p2;123     }124     cout << "图构建成功！" << endl<
       
        adjvex])137             DFS(G, p->adjvex);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);159                 p = G.xlist[i].link;   //找到当前顶点编表链表头指针160                 while (p)161                 {162                     if (!visited[p->adjvex])//若此顶点未访问163                     {164                         visited[p->adjvex] = true;165                         cout << G.xlist[p->adjvex].data<<" ";166                         EnQueue(Q, p->adjvex);//将此顶点入队列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 }
       
      
     

 

运行结果：