本文已参与「新人创作礼」活动,一同开启掘金创作之路
结合上次发的文章!总算把可视化的代码肝出来了!!! 这次代码的话,是用了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;
}