图之广度优先遍历

这是另外一个遍历图中所有顶点的方法，名字叫广度优先遍历（Breadth first search）,下面就来说一下这个遍历的具体思路。

首选先我们来看一张图：

乍一看这个图，特别凌乱，好像除了用深度优先遍历之后，就没有什么思路。但是我们可以把这张图进行如下的一个整理

 

这样子一看是不是觉得特别有层次感，但是每一个顶点相连的邻接点也没有乱，比如A就是第一层，BF就是第二层，CIGE就是第三层，DH就是第四层，那么最后这张图的打印顺序就是ABFCIGEDH

那么下面我用下面一张图来分析一下它的具体思路：

还是用一张图来讲解一下上面进队出队思路：

 说一下啊，这里我们要用到的是队列，一个存放int的类型的队列，因为这里存放的是每一个顶点的索引，那么我们就需要把这个队列做成一个动态库，然后引入。

我们先看一下我们库文件中有没有动态库

    然后发现是没有这个东西的，然后我们还是自己制作一个动态库

                    然后移动到我们自己存放库文件的位置上

                                                                                                                                                             然后现在就可以来编写程序

直接引入代码undirected_graph.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
extern "C" 
{
	#include "seqqueue.h"
}
//最大顶点数
#define MAX_VERTEX 30
//定义是否过滤标识的数组
int visit[MAX_VERTEX];


//定义图结构
typedef struct _graph
{
	//顶点数组，存储顶点名字
	char **vertex;
	//边的数组
	int edge[MAX_VERTEX][MAX_VERTEX];
	//顶点个数
	int vertex_num;
	//边的条数
	int edge_num;
}graph;

//算出用户输入的顶点在数组中的位置
//这里就是比如输入一个v1,v2,那么对于无向图来说，(v1,v2)与(v2,v1)都代表的是同一条边
int calc_vertex_pos(graph &g,char* v)
{
	//遍历顶点数组
	for(int i = 0;i < g.vertex_num;i++) {
		//这里相当于就是字符串比较
		if(strcmp(v,g.vertex[i]) == 0) {
			return i;//找到直接返回这个位置
		}
	}
	return -1;
}

//创建一个图
void create_graph(graph &g)
{
	printf("请输入图的顶点数目与边数目:顶点 边
");
	scanf("%d %d",&g.vertex_num,&g.edge_num);
	printf("请输入%d个顶点值
",g.vertex_num);

	//开始循环给顶点数组赋顶点值
	//在赋值之前需要在堆上开辟空间存放字符串
	g.vertex = (char**)malloc(sizeof(char*) * g.vertex_num);
	for(int i = 0;i < g.vertex_num;i++) {
		char str[100] = {0};
		scanf("%s",str);
		//这个数组又指向了分配的一个空间
		g.vertex[i] = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.vertex[i],str);
	}
	//把边的二维数组也给初始化一下
	//以顶点数n，形成一个n*n的二维数组
	for(int i = 0;i < g.vertex_num;i++) {
		for(int j = 0;j < g.vertex_num;j++) {
			//把对应的边全部初始化为0表示不存在
			g.edge[i][j] = 0;
		}
	}

	//上面二个数组内容给初始化好了
	//下面来设置边与边的关系，就是是否有边
	printf("请输入%d条边和与之对应的顶点1，顶点2
",g.edge_num);
	//设置两个有边的顶点之间的关系
	char v1[10];
	char v2[10];
	//有多少条边，就对应了有多少个顶点
	for(int i = 0;i < g.edge_num;i++) {
		scanf("%s %s",v1,v2);
		//然后我们计算顶点在数组中的位置
		//是0啊，1啊，还是2啊等等这样的关系
		int m = calc_vertex_pos(g,v1);//比如v1=0
		int n = calc_vertex_pos(g,v2);//v2 = 1 (0,1)就表示有边，就要把这个位置值设为1
		//同时(1,0)这个位置也要设置为1，毕竟是无向图
		g.edge[m][n] = 1;
		g.edge[n][m] = 1;
	}
}

//打印一张图
void print_graph(graph& g)
{
	//打印图也就是打印这个二维数组
	printf("	");
	//循环水平的顶点表头
	for(int i = 0;i < g.vertex_num;i++) {
		printf("%s	",g.vertex[i]);
	}
	//循环二维数组内容
	for(int i = 0;i < g.vertex_num;i++) {
		//打印水平的顶点表头
		printf("
");//每次换一个行
		printf("%s	",g.vertex[i]);
		//然后输出一行的内容
		for(int j = 0;j < g.vertex_num;j++) {
			printf("%d	",g.edge[i][j]);
		}
	}
	printf("	");
}


//广度优先遍历
void BFSTraverse(graph &g)
{
	//把过滤标识数组全部初始化为0
	for(int i = 0;i < g.vertex_num;i++) {
		visit[i] = 0;
	}
	//创建一个队列
	t_seq_queue* queue = create_queue();
	//遍历每一个结点
	for(int j = 0;j < g.vertex_num;j++) {
		//然后看看结点是否已经访问了
		if(!visit[j]) {
			//打印
			//并且把这个访问标识变为1
			printf("%s ",g.vertex[j]);
			visit[j] = 1;
			//同时把这个顶点的索引拿入队列，才好去查找它的邻接点
			push_queue(queue,j);
			//下面我们就要去查找下一层的邻接点
			//只要队列不为空，就要一直循环并打印数据
			while(!is_empty(queue)) {
				//首先拿到队头索引
				int index = get_front(queue);
				pop_queue(queue);
				//然后循环判断与之关联的顶点,让它打印并且入队
				for(int n = 0;n < g.vertex_num;n++) {
					if(g.edge[index][n] == 1 && !visit[n]) {
						printf("%s ",g.vertex[n]);
						push_queue(queue,n);
						visit[n] = 1;
					}
				}
			}
		}
	}
}

//构建图
void test01()
{
	graph g;
	create_graph(g);
	print_graph(g);
	printf("
---------------
");
	BFSTraverse(g);
}

int main() 
{
	test01();
	return 0;			
}

但是在这中间编译的时候又遇到一个问题，就是找不到队列的函数引用

 但是去查看了动态库，确实是已经编译好了，之前.c文件引入基本没出现过错误，这个时候我就在想是不是cpp文件引入c编写的动态库里的函数的时候会出现问题，于是这里就会引入一个问题 ，就是如何在cpp文件引入c编写的动态库？

这里先来说一下C++与C语言的函数处理方式，C++是一个面向对象编程的语言，那么它有一个特点就是可以实现函数的重载，也就是同名函数根据参数的个数，位置不同进行重载，C语言不行，换句话说，C++在编译函数的时候，为了解决函数多态的问题，就会将函数名与参数联合起来生成一个中间函数名称，而C语言不会，因为C++中引入C的函数就会找不到，因此我们需要用如下形式把C语言的头文件给括起来

                                                这个extern "C" {}就是表明这里名引入的函数都按照C语言的方式进行处理，于是编译成功

运行结果：

    下面说一下对于邻接表的一个深度优先遍历

分析思路都是一样，只是他们的内存形式不一样罢了

直接上代码

undirected_graph1.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef __cplusplus
extern "C" 
{
#endif
	#include "seqqueue.h"
#ifdef __cplusplus	
}
#endif
//最多能存放的顶点数目
#define MAX_VERTEX 100
//存放一个顶点过滤标识数组
int visit[MAX_VERTEX];

struct edge_node {
	int position;//这个表示vertex数组中的哪一个结点索引
	edge_node *next;//存放下一个邻接点的指针
	//这里权重可写可不写
};

struct vertex {
	char *name;//存放顶点名字,一级指针指向一个堆上面分配的空间
	//还有存放每一个与之相邻的第一个邻接点，其实这里它就相当于是头结点
	edge_node *first_node;
};

//最后需要整个图的结构
//来存放相应图的信息
struct graph {
	//存放顶点的所有信息
	vertex head[MAX_VERTEX];
	//顶点数与边数
	int vertex_num;
	int edge_num;
};



//这里还是来确定一下顶点位置
int find_pos(graph &g,char *v)//这里v如果有指向就可以打印,我的意思就是scanf直接赋值是不行的
{
	for (int i = 0; i < g.vertex_num; i++) {
		//循环存放顶点名字的那一片空间
		if (strcmp(g.head[i].name, v) == 0) {
			return i;
		}
	}
	return -1;
}

//先来创建一张图
void create_graph(graph &g)
{
	printf("请输入顶点数与边数:
");
	scanf("%d %d", &g.vertex_num, &g.edge_num);
	//循环输入顶点的值
	printf("请输入%d个顶点值:
", g.vertex_num);
	//循环给顶点赋值
	for (int i = 0; i < g.vertex_num; i++){
		char str[30] = { 0 };
		scanf("%s", str);
		//单纯scanf("%s",&g.head[i].name)肯定不行，这个name事一个二级指针
		g.head[i].name = (char*)malloc(sizeof(char) * (strlen(str) + 1));
		strcpy(g.head[i].name, str);//在哪一个索引位置存放顶点
		//除了赋值字符串之外，还需要初始化一个邻接点的地址
		g.head[i].first_node = NULL;//类似于每一个头顶点的next全是NULL
	}

	//下面开始来输入边，也就是两个顶点
	printf("请输入%d条边，顶点1，顶点2", g.edge_num);
	char v1[10];
	char v2[10];
	//循环给边赋值
	for (int i = 0; i < g.edge_num; i++) {
		scanf("%s %s", v1,v2);
		int m = find_pos(g, v1);
		int n = find_pos(g, v2);
		//在内存中找到了每个顶点的编号
		//然后比如说m是不是就是代表某个顶点的头部，这里可以
		//当成链表的头部处理
		//然后我们实现头插，表示某种联系
		//最后我们实现关系的一个交互，这是对于无向图来说v1与v2和v2与v1的关系一样
		
		//创建一个新的邻接点
		edge_node *p_new = (edge_node*)malloc(sizeof(edge_node));
		//然后开始在头部插入，这个头部也就是m点
		p_new->position = n;
		//这里p_new必须先指
		p_new->next = g.head[m].first_node;
		g.head[m].first_node = p_new;

		//然后实现v0与v1的一个交替，也就是一个意思
		edge_node *p_new1 = (edge_node*)malloc(sizeof(edge_node));
		//其实就是实现一个m与n的交替
		p_new1->position = m;
		p_new1->next = g.head[n].first_node;
		g.head[n].first_node = p_new1;
	}
}


//打印这张图
void print_graph(graph &g)
{
	for (int i = 0; i < g.vertex_num; i++) {
		printf("%s: ", g.head[i].name);
		//拿到头部结点进行一个单链表的遍历
		edge_node *p_node =  g.head[i].first_node;
		while (p_node != NULL) {
			//拿到的是n，找它的m
			int index = p_node->position;
			printf("%s ", g.head[index].name);
			p_node = p_node->next;
		}
		//换行
		printf("
");
	}
}


void BFSTraverse(graph &g)
{
	//初始化结点都没有被遍历
	for(int i = 0;i < g.vertex_num;i++) {
		visit[i] = 0;
	}
	//然后创建一个队列,依旧是去遍历每一个顶点
	t_seq_queue* queue = create_queue();
	for(int j = 0;j < g.vertex_num;j++) {
		//判断是否被访问
		if(!visit[j]) {
			//改变访问标识，打印，入队
			visit[j] = 1;
			printf("%s ",g.head[j].name);
			push_queue(queue,j);
			//然后开始走队列
			while(!is_empty(queue)) {
				//拿到队头元素
				int index = get_front(queue);
				//出队列
				pop_queue(queue);
				//拿到这个顶点的first_node
				edge_node *p_node = g.head[index].first_node;
				//开始循环与index这个顶点关联的所有顶点
				//这毕竟就是一个链表嘛
				while(p_node != NULL) {
					//找到这个顶点还是老规矩判断是否被遍历
					int n = p_node->position;
					if(!visit[n]) {
						printf("%s ",g.head[n].name);
						visit[n] = 1;
						//把这个顶点压入对列
						push_queue(queue,n);
					}
					p_node = p_node->next;
				}
			}
		}
	}
}
int main()
{
	graph g;
	create_graph(g);
	print_graph(g);
	printf("
------------------
");
	BFSTraverse(g);
	return 0;
}

  运行结果：

       下面来说一下时间复杂度，对比一下深度优先与广度优先，这两者在算法时间度是一样的，处理不同的实际情况，可以选择合适的算法。