C++ 图算法：深度优先搜索和广度优先搜索实现

#define MAXVEX 100 #define MINFINITE 0x7FFFFFFF #define _CRT_SECURE_NO_WARNINGS #pragma warning(disable:4996) #include <stdio.h> #include <wchar.h> #include <graphics.h> #include <conio.h> #include #include <malloc.h> #include

using namespace std;

typedef int EdgeType;

typedef struct { int edgeBegin; int edgeEnd; int wight; }EdgeWight;

typedef struct { char data[10]; int x; int y; }Vertex;

typedef struct { Vertex graphVertex[MAXVEX]; EdgeType graphEdge[MAXVEX][MAXVEX]; int vertexNum; int edgeNum; }MGraph;

//初始化 void initGraph(MGraph* pGraph); //生成图 void createGraph(MGraph* pGraph); //展示图的邻接矩阵 void showGraph(MGraph pGraph); //画图 void drawGraph(MGraph pGraph); //DFS(深度优先搜索) void DFSTraverse(MGraph pGraph); //DFS void DFS(MGraph pGraph, int* pVisited, int i); //BFS（广度优先搜索） void BFSTraverse(MGraph pGraph);

void initGraph1(MGraph* pGraph) { //初始化边的矩阵 for (int i = 0; i < pGraph->vertexNum; ++i) { for (int j = 0; j < pGraph->vertexNum; ++j) { if (i != j) { pGraph->graphEdge[i][j] = MINFINITE; } else { pGraph->graphEdge[i][j] = 0; } } } }

void createGraph(MGraph* pGraph) { FILE *fp(fopen("Graph.txt", "r")); fscanf(fp, "%d,%d\n", &pGraph->vertexNum, &pGraph->edgeNum); initGraph1(pGraph); for (int i = 0; i < pGraph->vertexNum; ++i) { fscanf(fp, "%s,%d,%d\n", pGraph->graphVertex[i].data, &pGraph->graphVertex[i].x, &pGraph->graphVertex[i].y); } int i, j, wight; for (int k = 0; k < pGraph->edgeNum; ++k) { fscanf(fp, "%d,%d,%d\n", &i, &j, &wight); pGraph->graphEdge[i][j] = wight; pGraph->graphEdge[j][i] = wight; } fclose(fp); }

void showGraph(MGraph pGraph) { printf("顶点数:%d,边数：%d\n顶点名称：", pGraph.vertexNum, pGraph.edgeNum); for (int i = 0; i < pGraph.vertexNum; ++i) { printf("%s,", pGraph.graphVertex[i].data); } puts("\n领接矩阵："); for (int i = 0; i < pGraph.vertexNum; ++i) { for (int j = 0; j < pGraph.vertexNum; ++j) { if (pGraph.graphEdge[i][j] == MINFINITE) { printf("* "); } else { printf("%-3d", pGraph.graphEdge[i][j]); } } puts(""); } }

void drawGraph(MGraph pGraph) { initgraph(640, 480, SHOWCONSOLE); int x1, y1, x2, y2; setlinecolor(BLACK); setbkcolor(WHITE); cleardevice(); setbkmode(TRANSPARENT); wchar_t str[100]; for (int i = 1; i < pGraph.vertexNum; ++i) { for (int j = 0; j < i; ++j) { if (pGraph.graphEdge[i][j] > 0 && pGraph.graphEdge[i][j] < MINFINITE) { x1 = pGraph.graphVertex[i].x; y1 = pGraph.graphVertex[i].y; x2 = pGraph.graphVertex[j].x; y2 = pGraph.graphVertex[j].y; line(x1, y1, x2, y2); settextcolor(BLACK); swprintf(str, 100, _T("%d"), pGraph.graphEdge[i][j]); outtextxy((x1 + x2 - 10) / 2, (y1 + y2 - 20) / 2, (LPCTSTR)str); } } } setfillcolor(YELLOW); int radio = 22; for (int i = 0; i < pGraph.vertexNum; ++i) { fillcircle(pGraph.graphVertex[i].x, pGraph.graphVertex[i].y, radio); outtextxy(pGraph.graphVertex[i].x - 5, pGraph.graphVertex[i].y - 5, pGraph.graphVertex[i].data); } DFSTraverse(pGraph); BFSTraverse(pGraph);

_getch(); closegraph(); }

void DFS(MGraph pGraph, int* pVisited, int i) { pVisited[i] = 1; _getch(); setlinecolor(RGB(0, 255, 64)); setlinestyle(PS_SOLID, 3); circle(pGraph.graphVertex[i].x, pGraph.graphVertex[i].y, 25); printf("%s-->", pGraph.graphVertex[i].data); int wight; for (int j = 0; j < pGraph.vertexNum; ++j) { wight = pGraph.graphEdge[i][j]; if (pVisited[j] == 0 && (wight > 0 && wight < MINFINITE)) { DFS(pGraph, pVisited, j); } } }

void DFSTraverse(MGraph pGraph) { puts("DFS深度优先遍历结果："); int visited[MAXVEX] = { 0 }; for (int i = 0; i < pGraph.vertexNum; ++i) { if (visited[i] == 0) { DFS(pGraph, visited, i); } } }

void BFSTraverse(MGraph pGraph) { queue queueTra; int visited[MAXVEX] = { 0 }; int wight, k; for (int i = 0; i < pGraph.vertexNum; ++i) { if (visited[i] == 0) { visited[i] = 1; queueTra.push(i); printf("BFS广度优先遍历结果："); while (!queueTra.empty()) { _getch(); k = queueTra.front(); queueTra.pop(); setlinecolor(RGB(51, 24, 33)); setlinestyle(PS_SOLID, 3); circle(pGraph.graphVertex[k].x, pGraph.graphVertex[k].y, 25); printf("%s--->", pGraph.graphVertex[k].data); for (int j = 0; j < pGraph.vertexNum; ++j) { wight = pGraph.graphEdge[k][j]; if (visited[j] == 0 && (wight > 0 && wight < MINFINITE)) { queueTra.push(j); visited[j] = 1; } } } }

} }

//主函数 int main() { MGraph graph; createGraph(&graph); showGraph(graph); drawGraph(graph); return 0; }