图的遍历可视化实现（广度优先和深度优先）

本文已参与「新人创作礼」活动，一同开启掘金创作之路

结合上次发的文章！总算把可视化的代码肝出来了！！！ 这次代码的话，是用了easyX的插件，然后结合编译器VS一同写出来的，难度不是很大，尤其是因为我自己是初学者，所以代码写的是比较简单的那种。 easyX的下载地址：easyx.cn/ 我代码完成的可视化图的遍历作用如下： 具有两个页面，其中一个是图，别的一个是所生成的信息

优先进行深度遍历
每遍历一次改动一个色彩

在深度优先遍历完之后，会对广度优先进行遍历
在广度优先的基础上进行变色

代码如下

#define MAXVEX 100
#define MINFINITE 0x7FFFFFFF
	#define _CRT_SECURE_NO_WARNINGS
	#pragma warning(disable:4996)
	typedef int EdgeType;
	typedef struct
	{
	 int edgeBegin;
	 int edgeEnd;
	 int wight;
	}EdgeWight;
	typedef struct
	{
	 char data;
	 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);
	#include <stdio.h>
	#include <graphics.h>
	#include <conio.h>
	#include <queue>
	#include <malloc.h>
	#include <algorithm>
    using namespace std;
	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, "%c,%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;
	  //printf("%d,%d,%d\n", i, j, wight);
	 }
	 fclose(fp);
	}
	void showGraph(MGraph pGraph)
	{	 
	printf("极点数:%d,边数：%d\n极点称号：", pGraph.vertexNum, pGraph.edgeNum);
 for (int i = 0; i < pGraph.vertexNum; ++i)
	 {
	  printf("%c,", pGraph.graphVertex[i]);
	 }
	 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, _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();
	}
/*
	DFS：它从图中某个极点V动身，访问此极点，然后从V的未被访问的邻接点动身深度优先便当图，
	直至图中所有和V有路径相通的极点都被访问到。
	若图中尚有极点未被访问，则另选图中一个未曾被访问的极点作为起始点，
	重复上述进程，直至图中所有极点都被访问到为止。
	*/
	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("%c-->", pGraph.graphVertex[i]);
 int wight;
	 for (int j = 0; j < pGraph.vertexNum; ++j)
	 {
	  //假如j没有被访问过，且i到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<int> 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("%c--->", 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;
	}