VS+opencv表示图的深度优先和广度优先遍历算法实现
题目要求:分别以邻接矩阵和邻接表数据结构来表示和存储一个图(要求同时支持无向图和有向图),分别求解器其深度优先(堆栈)和广度优先(队列)遍历结果,共四个遍历函数(邻接矩阵+深度优先遍历,邻接表+深度优先遍历,邻接矩阵+广度优先遍历,邻接表+广度优先遍历)。在此基础上,借助OpenCV画出原来的图(顶点以数据域中的三个整数数值画相应颜色的圆,边以黑色的线条来表示),以红色的线条来取代黑色的线条表示得到的生成树上的边。
下图为个人数据(仅供参考):上图为"a.txt"文本的数据,下图为"b.txt"文本的数据
下面为个人的代码(已经注释清楚,如果不清楚可以评论私聊):
代码函数中的12时因为个人数据有12个点,可以在全局中#define N来表示你的数据个数,可以变通 ;
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include "opencv2/imgproc/imgproc.hpp"
#include<core/core.hpp>
#include<highgui/highgui.hpp>
#include "cv.h"
#include "highgui.h"
using namespace cv;
using namespace std;
struct color
{
int R;
int G;
int B;
}co[12]; //存储各个结点的颜色
struct node
{
int number;
struct node *next;
}s[12]; //创建邻接表的节点
struct node1
{
int x;
int y;
}nd[12]; //各个节点的坐标
int matrix[12][12] = { 0 }; //邻接矩阵
int visited[12] = { 0 }; //判断节点是否被输出
int k = 0; //统计已记录节点
void readtxt(); //读取全部文本
void drawpicture(Mat image);
void DFSchart(struct node *p,Mat image1); //邻接表深度搜索遍历
void BFSchart(Mat image1); //邻接表广度搜索遍历
void DFSmatrix(int i, Mat image1); //邻接矩阵深度搜索遍历
void BFSmatrix(Mat image1); //邻接矩阵广度搜索遍历
int main()
{
Mat image(400, 800, CV_8UC3, Scalar(255, 255, 255));
Mat image1, image2, image3, image4;
int i;
readtxt();
drawpicture(image);
namedWindow("lena", 1);
imshow("lena", image);
waitKey();
//邻接表深度搜索遍历
visited[12] = { 0 };
image1 = image.clone(); //复制原图,下面同理
for (i = 0; i < 12; i++) //此处循环是为面对该图为不连通图的情况,如果有多条独立的路径的话,即可通过循环判断所有点是否已经都被搜索了
{
k = 1;
if (visited[i] == 0)
DFSchart(&s[i],image1); //对该点进行深度搜索,下同理
if (k == 12)
break;
}
imshow("lena", image1);
waitKey();
imwrite("邻接表深入搜索遍历.jpg", image1);
//邻接表广度搜索遍历
for(i = 0; i < 12;i++) //将各点状态重新调味0,下同理
visited[i] = 0;
image2 = image.clone();
BFSchart(image2); //进行邻接表广度搜索
imshow("lena", image2);
waitKey();
imwrite("邻接表广度搜索遍历.jpg", image2);
//邻接矩阵深度搜索遍历
for (i = 0; i < 12; i++)
visited[i] = 0;
image3 = image.clone();
for (i = 0; i < 12; i++) //循环与邻接表深度搜索原因一致
{
k = 0;
if (visited[i] == 0)
DFSmatrix(i, image3); //深度搜索开始
if (k == 12)
break;
}
imshow("lena", image3);
waitKey();
imwrite("邻接矩阵深度搜索遍历.jpg", image3);
//邻接矩阵广度搜索遍历
//大部分道理与邻接表光度搜索道理一致
for (i = 0; i < 12; i++)
visited[i] = 0;
image4= image.clone();
BFSmatrix(image4); //广度搜索开始
imshow("lena", image4);
waitKey();
imwrite("邻接矩阵广度搜索遍历.jpg", image4);
return 0;
}
void readtxt() //读取2个文本的原始数据来获得各节点颜色和坐标,同时创建邻接矩阵和邻接表
{
FILE *fp;
int i, j, row, col;
struct node *p,*q;
fp = fopen("a.txt", "r"); //"a.txt"内存储各节点颜色及坐标
for (i = 0; i < 12; i++)
fscanf_s(fp, "%d:(%d,%d,%d,%d,%d)",&row, &co[i].R, &co[i].G, &co[i].B, &nd[i].x, &nd[i].y); //读取各节点颜色和坐标
fclose(fp);
fp = fopen("b.txt", "r"); //"b.txt"存储各条路
while (!feof(fp))
{
fscanf_s(fp, "(%d,%d)\n", &row, &col); //row为起点,col为路的终点
matrix[row][col] = 1; //将此路用矩阵表示
}
fclose(fp);
for (i = 0; i < 12; i++)
{
s[i].number = i;
p = &s[i];
//通过矩阵0.1属性来创建各个结点的邻接表
for (j = 0; j < 12; j++)
{
if (matrix[i][j] == 1) //如果二维矩阵此处为1,则代表i的邻接表内有j
{
q = (struct node *)malloc(sizeof(struct node));
q->number = j;
p->next = q;
p = q;
}
}
p->next = NULL;
}
}
void drawpicture(Mat image) //通过颜色及坐标及各点连接关系画出原图
{
int i;
char zm[3];
zm[1] = '\0';
zm[2] = '\0';
struct node *p, *q;
for (i = 0; i < 12; i++)
{
zm[0] = '0' + i; //zm数组用于putText函数用于在图片上输出文本
if (i > 9)
{
zm[0] = i / 10+'0';
zm[1] = i % 10 + '0';
}
circle(image, Point(nd[i].x, nd[i].y), 20, Scalar(co[i].B, co[i].G, co[i].R), -1); //画出各节点
putText(image, zm, Point(nd[i].x, nd[i].y), FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(255, 2, 2)); //在圆上标记此点的值
}
for (i = 0; i < 12; i++)
{
p = &s[i];
while (p->next!= NULL)
{
line(image, Point(nd[i].x, nd[i].y), Point(nd[p->next->number].x, nd[p->next->number].y), Scalar(0, 0, 0)); //在图上连接有关系的结点,即为路径
p = p->next;
}
}
}
void DFSchart(struct node *p,Mat image1) //邻接表深度搜索遍历
{
visited[0] = 1;
struct node *q=p->next;
while (q != NULL)
{
if (visited[q->number] == 0) //如果该点未被搜索到的话,就对其进行操作搜索
{
visited[q->number] = 1;
k += 1;
line(image1, Point(nd[p->number].x, nd[p->number].y), Point(nd[q->number].x, nd[q->number].y), Scalar(0, 0, 255)); //将该条搜索经过的路径改为红色
if (k == 12) //如果已经搜完所有结点,就直接return退出函数循环
return;
DFSchart(&s[q->number],image1); //通过递归对该点进行深度搜索
}
q = q->next;
}
} //
void BFSchart(Mat image1) //邻接表广度搜索遍历
{
int b[12];
int i=0, j=0,z;
struct node *p,*q;
b[0] = 0;
for (z = 0; z < 12; z++) //此处循环用以面对出现多条独立路径的情况
{
if (visited[z] == 0)
{
b[j] = z;
j++;
for (i; i < j; i++) //此处用循环不用堆栈的原因是因为每次搜索新的一个点时,j都会大于i,j可以当作堆栈的尾,i可以当作堆栈的头,对我而言可以等效使用,因为循环用惯了,此处可以多看几遍理解一下,不是很困难
{
visited[b[i]] = 1; //将搜索过的点状态调为1
p = &s[i];
q = p->next;
while (q != NULL)
{
if (visited[q->number] == 0) //如果此点未被搜索过,则对其进行操作
{
visited[q->number] = 1;
b[j] = q->number; //将搜索点加入b数组,可以当作正常使用的栈
j += 1;
line(image1, Point(nd[p->number].x, nd[p->number].y), Point(nd[q->number].x, nd[q->number].y), Scalar(0, 0, 255)); //将搜索过的路径描红
}
q = q->next;
}
}
}
if (j == 12) //如果j等于点的总数时则代表已经搜索完全可以退出函数了
return;
}
}
void DFSmatrix(int i, Mat image1) //邻接矩阵深度搜索遍历
{
visited[i] = 1;
k += 1;
int j;
if (k == 12) //如果已经搜完所有结点,就直接return退出函数循环
return;
for (j = 0; j < 12; j++)
{
if (matrix[i][j] == 1) //矩阵值为1时则代表i,j两点有路即可进行搜索判断
{
if (visited[j] == 0) //如果该点未被搜索到的话,就对其进行操作搜索
{
line(image1, Point(nd[i].x, nd[i].y), Point(nd[j].x, nd[j].y), Scalar(0, 0, 255)); //将该条搜索经过的路径改为红色
DFSmatrix(j, image1); //通过递归对该点进行深度搜索
if (k == 12) //如果已经搜完所有结点,就直接return退出函数循环
return;
}
}
}
}
void BFSmatrix(Mat image1) //邻接矩阵广度搜索遍历
{
int b[12];
int i = 0, j = 0, z,i1;
for (z = 0; z < 12; z++) //此处循环用以面对出现多条独立路径的情况
{
if (visited[z] == 0)
{
b[j] = z;
j++;
for (i; i < j; i++) //此处循环与上面广度搜索不用真正的堆栈同理
{
visited[b[i]] = 1; //此处用于帮起始点状态改变
for (i1 = 0; i1 < 12; i1++)
{
if (matrix[b[i]][i1] == 1)
{
if (visited[i1] == 0) //如果此点未被搜索过,则对其进行操作
{
visited[i1] = 1;
b[j] = i1; //将搜索点加入b数组,可以当作正常使用的栈
j++;
line(image1, Point(nd[b[i]].x, nd[b[i]].y), Point(nd[i1].x, nd[i1].y), Scalar(0, 0, 255)); //将搜索过的路径描红
}
}
}
if (j == 12) //如果j等于点的总数时则代表已经搜索完全可以退出函数了
return;
}
}
}
}