深度、广度优先搜索 桃扇骨 2022-10-08 14:24 166阅读 0赞 ### 文章目录 ### * 二、图的遍历 * * 2.1 深度优先搜索（DFS） * * DFS森林 * 应用 * 2.2 广度优先搜索（BFS） * * 基本操作 * 应用 # 二、图的遍历 # ## 2.1 深度优先搜索（DFS） ## ### DFS森林 ### Vertextype GetVex(ALGraph G, int v) { return G.vertices[v].data; } void DFSTree(ALGraph G, int v, CSTree& T) { int w, first; CSTree p, q=NULL; ArcNode* temp; visited[v] = TRUE; first = 1; temp = G.vertices[v].firstarc; while (temp != NULL) { w = temp->adjvex; if (visited[w] == 0) { p = (CSTree)malloc(sizeof(CSNode)); p->e = GetVex(G, w); //原"GetVex(G,v)";将v改为w即可 p->lchild = NULL; p->nextsibling = NULL; if (first) { T->lchild = p; first = 0; } else q->nextsibling = p; q = p; DFSTree(G, w, q); } temp = temp->nextarc; } } void DFSForest(ALGraph G, CSTree& T) { int v; CSTree p, q=NULL; T = NULL; for (v = 0; v < G.vexnum; v++) visited[v] = FALSE; for (v = 0; v < G.vexnum; v++) { if (!visited[v]) { p = (CSTree)malloc(sizeof(CSNode)); p->e = GetVex(G, v); p->lchild = NULL; p->nextsibling = NULL; if (!T) T = p; else q->nextsibling = p; q = p; DFSTree(G, v, p); } } } ### 应用 ### 建立一无向图的邻接表存储结构，并构造其对应的深度优先搜索生成树或森林，按先序遍历该二叉链表，输出得到的序列 #include<stdio.h> #include<stdlib.h> #define TRUE 1 /*状态码预定义*/ #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define MAX_VERTAX_NUM 20 //最大顶点个数 typedef char Vertextype; //邻接表类型 typedef struct ArcNode { int adjvex; //邻接点域 struct ArcNode* nextarc; //指向下一个邻接点的指针域 }ArcNode; //表头结点类型 typedef struct VNode { Vertextype data; //顶点域 ArcNode* firstarc; //边表头指针 }VNode, AdjList[MAX_VERTAX_NUM]; //图的类型 typedef struct { AdjList vertices; //邻接表 int vexnum, arcnum; //顶点数 边数 //int kind; }ALGraph; typedef struct CSNode { Vertextype e; CSNode* lchild, * nextsibling; }CSNode, * CSTree; int visited[MAX_VERTAX_NUM]; int LocateVex(ALGraph G, char e) { int i; for (i = 0; i < G.vexnum; i++) { if (G.vertices[i].data == e) return i; } return -1; } void CreateUDG(ALGraph& G) { int i, k, j; ArcNode* p, * s; char v1, v2; // printf("图的种类已默认为无向图\n"); // G.kind = 1; printf("请输入顶点数和边数：（空格区分）"); scanf("%d%d", &G.vexnum, &G.arcnum); getchar(); printf("开始建立顶点表\n"); for (i = 0; i < G.vexnum; i++) { printf("请输入第%d个顶点的信息:", i + 1); G.vertices[i].data = getchar(); getchar(); G.vertices[i].firstarc = NULL; } printf("建立边表\n"); for (k = 0; k < G.arcnum; k++) { printf("请输入两个顶点（例：ab代表a~b）:"); scanf("%c%c", &v1, &v2); getchar(); i = LocateVex(G, v1); j = LocateVex(G, v2); p = (ArcNode*)malloc(sizeof(ArcNode)); p->adjvex = j; p->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p; s = (ArcNode*)malloc(sizeof(ArcNode)); s->adjvex = i; s->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = s; } printf("边表建立完成\n"); } //打印邻接表 void DispGraph(ALGraph G) { int i; printf("打印邻接表:\n"); for (i = 0; i < G.vexnum; i++) { printf("%d->", i); while (1) { if (G.vertices[i].firstarc == NULL) { printf("^"); break; } printf("%d->", G.vertices[i].firstarc->adjvex); G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc; } printf("\n"); } } Vertextype GetVex(ALGraph G, int v) { return G.vertices[v].data; } void DFSTree(ALGraph G, int v, CSTree& T) { int w, first; CSTree p, q=NULL; ArcNode* temp; visited[v] = TRUE; first = 1; temp = G.vertices[v].firstarc; while (temp != NULL) { w = temp->adjvex; if (visited[w] == 0) { p = (CSTree)malloc(sizeof(CSNode)); p->e = GetVex(G, w); //原"GetVex(G,v)";将v改为w即可 p->lchild = NULL; p->nextsibling = NULL; if (first) { T->lchild = p; first = 0; } else q->nextsibling = p; q = p; DFSTree(G, w, q); } temp = temp->nextarc; } } void DFSForest(ALGraph G, CSTree& T) { int v; CSTree p, q=NULL; T = NULL; for (v = 0; v < G.vexnum; v++) visited[v] = FALSE; for (v = 0; v < G.vexnum; v++) { if (!visited[v]) { p = (CSTree)malloc(sizeof(CSNode)); p->e = GetVex(G, v); p->lchild = NULL; p->nextsibling = NULL; if (!T) T = p; else q->nextsibling = p; q = p; DFSTree(G, v, p); } } } void PreOrderTraverse(CSTree T) { if (T == NULL) return; printf("%c", T->e); PreOrderTraverse(T->lchild); PreOrderTraverse(T->nextsibling); } int main() { ALGraph G; //图 CSTree T; //树 CreateUDG(G); //建图 DispGraph(G); //画表 DFSForest(G, T); //种树 printf("先序遍历开始\n"); PreOrderTraverse(T); //先序遍历 system("pause"); return 0; } ## 2.2 广度优先搜索（BFS） ## ### 基本操作 ### int FirstAdjVex(MGraph G, int v) { int i; for (i = 0; i < G.vexnum; i++) { if (G.arcs[v][i] == 1) return i; } return -1; } int NextAdjVex(MGraph G, int u, int w) { for (int i = w + 1; i < G.vexnum; i++) { if (G.arcs[u][i] == 1) return i; } return -1; } void BFSTraverse(MGraph G) { SqQueue Q; int v, u, w, visited[MAX_VERTAX_NUM]; for (v = 0; v < G.vexnum; ++v) visited[v] = FALSE; InitQueue(Q); for (v = 0; v < G.vexnum; v++) { if (!visited[v]) //尚未访问 { visited[v] = TRUE; //访问并标记 cout << G.vexs[v]; //遍历 输出 EnQueue(Q, v); //v 入队 while (!QueueEmpty(Q)) { DeQueue(Q, u); //队头元素出队并置为u for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) //遍历边 { if (!visited[w]) { visited[w] = TRUE; cout << G.vexs[w]; EnQueue(Q, w); } } } } } cout << "广度优先搜索完成" << endl; } ### 应用 ### #include <iostream> using namespace std; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 //不可执行 #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 #define MAXQSIZE 100 //最大队列长度 typedef int QElemType; typedef int Status; #define MAX_VERTAX_NUM 20 //最大顶点个数 #define INFINITYA 99999999 typedef char VertexType; typedef int VRType; typedef int InfoType; typedef int AdjMatrix; typedef int QElemtype; /*--------单链队列-队列的顺序存储结构--------*/ /*线性表的单链表的存储结构*/ typedef struct QNode { QElemType* base; int front; int rear; }SqQueue; Status InitQueue(SqQueue& Q) { Q.base = (QElemType*)malloc(MAXQSIZE * sizeof(QElemType)); if (!Q.base) exit(OVERFLOW); Q.front = Q.rear = 0; return OK; } int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; } /*插入元素e为Q的新的队尾元素*/ Status EnQueue(SqQueue& Q, QElemType e) { if ((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; Q.base[Q.rear] = e; Q.rear = (Q.rear + 1) % MAXQSIZE; return OK; } /*若队列不为空则删除Q的队头元素，用e返回其值，并返回ok；否则返回ERROR*/ Status DeQueue(SqQueue& Q, QElemType& e) { if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE; return OK; } /*判断队列是否为空*/ Status QueueEmpty(SqQueue Q) { if (Q.front == Q.rear) return TRUE; else return FALSE; } //邻接矩阵 typedef struct { VertexType vexs[MAX_VERTAX_NUM]; AdjMatrix arcs[MAX_VERTAX_NUM][MAX_VERTAX_NUM]; int vexnum, arcnum; }MGraph; int LocateVex(MGraph G, VertexType e) { int i; for (i = 0; i < G.vexnum; i++) { if (G.vexs[i] == e) return i; } return -1; } Status CreateDG(MGraph& G) { int i, j, k; char v1, v2; cout << "请输入图的顶点个数（vexnum），边数（arcnum）"; cin >> G.vexnum >> G.arcnum; getchar(); cout << "请输入顶点（例：abcd）:"; for (i = 0; i < G.vexnum; i++) G.vexs[i] = getchar(); getchar(); for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.vexnum; j++) G.arcs[i][j] = INFINITYA; for (k = 0; k < G.arcnum; k++) { cout << k; cout << "请输入两个顶点:"; cin >> v1 >> v2; getchar(); i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = 1; } return OK; } int FirstAdjVex(MGraph G, int v) { int i; for (i = 0; i < G.vexnum; i++) { if (G.arcs[v][i] == 1) return i; } return -1; } int NextAdjVex(MGraph G, int u, int w) { for (int i = w + 1; i < G.vexnum; i++) { if (G.arcs[u][i] == 1) return i; } return -1; } void BFSTraverse(MGraph G) { SqQueue Q; int v, u, w, visited[MAX_VERTAX_NUM]; for (v = 0; v < G.vexnum; ++v) visited[v] = FALSE; InitQueue(Q); for (v = 0; v < G.vexnum; v++) { if (!visited[v]) //尚未访问 { visited[v] = TRUE; //访问并标记 cout << G.vexs[v]; //遍历 输出 EnQueue(Q, v); //v 入队 while (!QueueEmpty(Q)) { DeQueue(Q, u); //队头元素出队并置为u for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) //遍历边 { if (!visited[w]) { visited[w] = TRUE; cout << G.vexs[w]; EnQueue(Q, w); } } } } } cout << "广度优先搜索完成" << endl; } int main() { MGraph G; CreateDG(G); BFSTraverse(G); return 0; } ···
还没有评论，来说两句吧...