C语言图的深度优先遍历和广度优先遍历算法实现

#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 <wchar.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,100,_T("%lc"), (wchar_t)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;