#数据结构与算法学习笔记#PTA18：图（邻接表）+DFS（深度优先搜索）+BFS（广度优先搜索）（C/C++）

2018.5.22

 

上周解决完了树的大BOSS，这周正式进入图了。图根据边的性质可以分为有权图和无权图，有向图和无向图。无论哪一种图，都可以用邻接矩阵与邻接表两种数据结构表示，对于稠密图来说，邻接矩阵更方便一些，对于稀疏图来说，邻接表效率更高。图有两种遍历方法，深度优先搜索（DFS，Depth First Search）与广度优先搜索（BFS，Breadth First Search）。

这题意思很简单，只要按DFS或者BFS遍历一遍图的每一个连通集就好。需要注意的地方有：1.访问的顺序需要是编号递增顺序，即但编号A的结点有N个相连结点时，需要先遍历下一次编号最小的结点。2.需要考虑多个连通图存在的情况。

整体结构分为三部分：用邻接表建立图（邻接矩阵也可），进行DFS遍历，进行BFS遍历。邻接表建立图中需要注意每个头结点后的临接点需要按递增顺序插入。DFS的基本思想是，从第一个结点开始，遍历该结点的邻接表，将访问到的结点进行标记，若有未访问的结点，则递归访问其邻接表。BFS的基本思想是，从第一个结点开始，每次先压入表头结点，弹出表头结点时依次压入没有访问过的邻接点指向的表头结点，重复进行弹出和压入操作，直到队列为空。

BFS的思想其实就是层次遍历二叉树的思想，详见——#数据结构与算法学习笔记#PTA10：层次遍历叶节点（JAVA）

 

题目要求：

给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:

输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:

 

按照"{ v​1 v2 ... vk }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

 

 

实现代码：

// ConnectedSet.cpp: 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

//邻接点
class AdjacentNode {
public:
	int data;
	int weight;
	AdjacentNode* next;
};

//邻接表头结点
class HeadNode {
public:
	int data;
	AdjacentNode * headedge;
	bool isvisit = false;
};

void CreateGraph(vector<HeadNode*>& graph, int nodenum, int edgenum);	//邻接表方式建立图
void DFS(vector<HeadNode*>& graph, int index);							//深度优先搜索（DFS）
void BFS(vector<HeadNode*>& graph, int index);							//广度优先搜索（BFS）


int main()
{
	int nodenum, edgenum;
	cin >> nodenum >> edgenum;

	vector<HeadNode*> graph;
	CreateGraph(graph, nodenum, edgenum);

	//深度优先搜索DFS
	//注意考虑多个连通集存在	
	for (int i = 0; i < nodenum; i++) {
		if (!(*graph[i]).isvisit) {
			cout << "{";
			DFS(graph, i);
			cout << " }" << endl;
		}
	}


	//清楚访问标志
	for (int i = 0; i < nodenum; i++) {
		(*graph[i]).isvisit = false;
	}

	//广度优先搜索BFS
	//注意考虑多个连通集存在
	for (int i = 0; i < nodenum; i++) {
		if (!(*graph[i]).isvisit) {
			cout << "{";
			BFS(graph, i);
			cout << " }" << endl;
		}
	}



	system("pause");
	return 0;
}

void CreateGraph(vector<HeadNode*>& graph, int nodenum, int edgenum) {
	//建立邻接表表头
	for (int i = 0; i < nodenum; i++) {
		HeadNode* node = new HeadNode();
		node->data = i;
		node->headedge = NULL;
		graph.push_back(node);
	}
	//插入每个邻接点（双向） 
	//将插入临接点调整为增序
	for (int i = 0; i < edgenum; i++) {
		int a, b;
		cin >> a >> b;

		AdjacentNode * loc = (*graph[a]).headedge;		//指示插入位置,将其调整到符合递增顺序的位置
		AdjacentNode * newnode = new AdjacentNode();	//待插入结点
		newnode->data = b;
		if (loc && loc->data < b) {
			while (loc->next && loc->next->data < b) {
				loc = loc->next;
			}
			newnode->next = loc->next;
			loc->next = newnode;
		}
		else {
			newnode->next = (*graph[a]).headedge;
			(*graph[a]).headedge = newnode;
		}

		//无向图
		loc = (*graph[b]).headedge;
		newnode = new AdjacentNode();
		newnode->data = a;
		if (loc && loc->data < a) {
			while (loc->next && loc->next->data < a) {
				loc = loc->next;
			}
			newnode->next = loc->next;
			loc->next = newnode;
		}
		else {
			newnode->next = (*graph[b]).headedge;
			(*graph[b]).headedge = newnode;
		}

	}
}

void DFS(vector<HeadNode*>& graph, int index) {
	//标记每一个已访问的结点
	(*graph[index]).isvisit = true;
	cout << " " << index;

	//利用递归进行广度优先搜索：遍历该结点的邻接表，若有未访问的结点，则递归访问其邻接表
	AdjacentNode *p = (*graph[index]).headedge;
	while (p) {
		if (!(*graph[p->data]).isvisit) {
			DFS(graph, p->data);
		}
		p = p->next;
	}
}

void BFS(vector<HeadNode*>& graph, int index) {
	(*graph[index]).isvisit = true;
	cout << " " << index;

	//利用队列进行广度优先搜索：每次先压入表头结点，弹出表头结点时依次压入没有访问过的邻接点
	queue<HeadNode*> bfsque;
	bfsque.push(graph[index]);

	while (!bfsque.empty()) {
		//重置p为表头结点的地址
		AdjacentNode* p = (*graph[bfsque.front()->data]).headedge;
		bfsque.pop();
		while (p) {
			if (!(*graph[p->data]).isvisit) {
				bfsque.push(graph[p->data]);
				cout << " " << p->data;
				(*graph[p->data]).isvisit = true;
			}
			p = p->next;
		}
	}
}

---

#Coding一小时，Copying一秒钟。留个言点个赞呗，谢谢你#