chaper 6-3 图的遍历

BFS广度优先

  • 使用辅助队列完成遍历。
  • 图的广度优先搜索与二叉树的层序遍历顺序一致。
  • 注意若为邻接矩阵存储的图,由于邻接矩阵的唯一性,根据BFS生成的生成树也唯一;而邻接表的存储表示不唯一(主要看存入边的顺序),因此其生成树不唯一。
  • BFS的邻接矩阵实现:
    图算法
  • BFS的邻接表实现:
 struct Enode {
	int data;
	Enode* next;
	int weight;//边权
};
 
Enode enodelist[20];
bool vis[200] = { false };
int num = 20;//节点数
void Bfs(int a) {
	queue<int>s;
	vis[a] = true;
	s.push(a);
	while (!s.empty()) {
		int t = s.front();
		s.pop();
		while (enodelist[t].next != nullptr) {
			t = enodelist[t].next->data;
			if(vis[t]==false){
				vis[t] = true;
				s.push(t);
			};
		};
	};
}
void set_bfs() {
	for (int i = 1; i <= num; i++) {
		if (!vis[i]) {
			Bfs(i);
		};
	};
}
  • 解单源最短路径
    给定起点u,求出u到图上其余点v的最短路径。
    通过BFS来解决问题,因为BFS总是按照距离从近到远来遍历的。
    注意上面给出的BFS算法没有指定起点,默认第一个顶点开始遍历。
int G[200][200];//邻接矩阵
int num = 20;
bool vis[200] = { false };
int d[200];//存储每个v到u的最短路径
void one_BFS(int a) {
	for (int i = 1; i <= num; i++) {
		d[i] = 0xffffff;
	};
	d[a] = 0;
	queue<int>s;
	vis[a] = true;
	s.push(a);
	while (!s.empty()) {
		int t = s.front();
		s.pop();
		for (int j = 1; j <= num; j++) {
			if (G[t][j] == 1 && vis[j] == false) {
				d[j] = d[t]+1;
				vis[j] = true;
				s.push(j);
			};
		};
	}
}
  • BFS性能分析
  1. 由于BFS需要辅助队列,因此其空间复杂度为O(|v|).
  2. 对于邻接表的BFS,每个顶点均需要访问一次,为O(|v|),每条边均需要至少访问一次,为O(|e|),总体为O(|v|+|e|)
  3. 对于邻接矩阵的BFS,因为矩阵的每个元素都会访问,为O(|v|^2)

DFS

  • 写DFS无需辅助结构,直接递归即可
  • DFS邻接矩阵实现:
    图算法
  • DFS邻接表实现:
struct enode {
	int data;
	enode* next;
};
enode elist[200];
int num = 20;
bool vis[200] = { false };
void dfs(int a) {
	vis[a] = true;
	int t = a;
	while (elist[t].next != nullptr) {
		t = elist[t].next->data;
		if (vis[t] == false) {
			dfs(t);
		};
	}
}
void set_dfs() {
	for (int i = 1; i <= num; i++) {
		if (!vis[i]) {
			dfs(i);
		};
	};
}
  • DFS性能
    同BFS
  • 注意:有向图的连通和强连通是不一样的。连通分为强连通和非强连通,而非强连通无法通过一次bfs或dfs来访问全部结点(因为路径是单向的,有路径不代表两端都能到达)
上一篇:转:js监控键盘大小写事件


下一篇:转:js-PC版监听键盘大小写事件