图的遍历方法一般有两种：深度优先搜索（DFS）和广度优先搜索（BFS）
采用深度优先搜索（DFS）遍历图
沿着一条路径直到无法继续前进，才退回到路径上离当前顶点最近的还存在未访问分支顶点的岔道口，并前往访问那些未访问分支顶点，直到遍历完整个图。
两个概念：
连通分量：在无向图中，如果两个顶点之间可以相互到达（可以是通过一定路径间接到达），那么就称这两个顶点连通。如果G(V,E)的任意两个顶点都连通，则称图G为连通图；否则，称图G为非连通图，且称其中的极大连通子图为连通分量。
强连通分量：在有向图中，如果两个顶点可以各自通过一条有向路径到达另一个顶点，就称这两个顶点强连通。如果图G(V,E)的任意两个顶点都强连通，则称图G为强连通图；否则，称图G为非强连通图，且称其中的极大强连通子图为强连通分量。
把连通分量和强连通分量均称为连通块
如果要遍历整个图，就需要对所有连通块分别进行遍历。
基本思路：将经历过的顶点设置为已访问，在下次递归碰到这个顶点时就不再去处理，直到整个图的顶点都被标记为已访问。
如已知给定的图时一个连通图，则只需要一次DFS就能完成遍历
伪代码:
DFS(u) { //访问顶点u
vis[u] = true; //设置u已被访问
for(从u出发能到达的所有顶点v) //枚举从u出发可以到达的所有顶点v
if vis[v] == false //如果v未被访问
DFS(v); //递归访问v
}
DFSTrave(G) { //遍历图G
for(G的所有顶点u) //对G的所有顶点u
if vis[u] == false //如果u未被访问
DFS(u); //访问u所在的连通块
}
实现邻接矩阵和邻接表前需要先定义MAXV为最大顶点数、INF为一个很大的数字
const int MAXV = 1000; //最大顶点数
const int INF = 1000000000; //设INF为一个很大的数
邻接矩阵版本
int n, G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数
bool vis[MAXV] = {false}; //如果顶点i已被访问，则vis[i] == true。初值为false
void DFS(int u, int depth) { //u为当前访问的顶点标号，depth为深度
vis[u] = true; //设置u已被访问
//如果需要对u进行一些操作，可以在这里进行
//下面对所有从u出发能到达的分支顶点就像枚举
for(int v = 0; v < n; v++) {
if(vis[v] == false && G[u][v] != INF) { //如果v未被访问，且u可到达v
DFS(v, depth + 1); //访问v， 深度加一
}
}
}
void DFSTrave() (
for(int u = 0; u < n; u++) { //对每个顶点u
if(vis[u] == false) { //如果u未被访问
DFS(u, 1); //访问u和u所在的连通块，1表示初始为第一层
}
}
)
邻接表版本
vector<int> Adj[MAXN]; //图G的邻接表
int n; //n为顶点数，MAXV为最大顶点数
bool vis[MAXV] = {false}; //如果顶点i已被访问，则vis[i] == true。初值为false
void DFS(int u, int depth) { //u为当前访问的顶点标号，depth为深度
vis[u] = true; //设置u已被访问
//如果需要对u进行一些操作，可以在这里进行
for(int i = 0; i < Adj[u].size(); i++) {
int v = Adj[u][i];
if(vis[v] == false){
DFS(v, depth + 1); //访问v， 深度加一
}
}
}
void DFSTrave() (
for(int u = 0; u < n; u++) { //对每个顶点u
if(vis[u] == false) { //如果u未被访问
DFS(u, 1); //访问u和u所在的连通块，1表示初始为第一层
}
}
)
实例:
给出若干人之间的通话长度（视为无向边），这些通话将他们分为若干组。每个组的总边权设为该组内的所有通话的长度之和，而每个人的点权设为该人参与的通话长度之和。现在给定一个阀值K，且只要一个组的总边权超过K，并满足成员人数超过2，则将该组视为”犯罪团伙(Gang)“，而该组内点权最大的人视为头目。要求输出”犯罪团伙“的个数，并按头目姓名字典序从小到大的顺序输出每个”犯罪团伙“的头目姓名和成员人数。
思路：
- 解决姓名和编号的对应关系。可使用map<string, int>直接建立字符串与整型的映射关系，也可使用字符串hash的方法将字符串转换为整型。编号与姓名的对应关系则可以直接使用string数字进行定义，或者使用map<int, string>也是可以的
- 需要获得每个人的点权，即与之相关的通话记录的时长之和，可以在读入时进行处理。该步在求与某个点相连的边的边权之和
- 图的遍历。使用DFS遍历每个连通块，目的是获取每个连通块的头目（即连通块内点权最大的结点）、成员个数、总边权
- 通过步骤3可以获得连通块的总边权totalValue。如果totalValue大于给定的阀值K，且成员人数大于2，则说明该连通块是一个团伙，将该团伙的信息存储下来
可以定义map<string, int>，来建立团伙头目的姓名与成员人数的映射关系。由于map中元素自动按键从小到大排序。
注意点：
- 由于通话记录的条数最多有1000条，意味着不同的人可能有2000人，因此数组大小必须在2000以上
- 可以使用使用结构体来存放头目姓名与成员人数，但会增加一定代码量
struct Gang {
string head; //团伙头目
int numMember; //成员数量
}arrayGang[maxn];
int numGang = 0; //团伙个数
bool cmp(Gang a, Gang b) {
return a.head < b.head; //按头目姓名的字典序从小到大排序
}
- 由于每个结点在访问后不应再次被访问，但是图中可能有环，即遍历过程中发生一条边连接已访问结点 的情况。此时为了边权不被漏加，需要先累加边权，再去考虑结点递归访问的问题
- 本题也可用并查集解决
//输入1
8 59
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
//输出1
2
AAA 3
GGG 3
//输入2
8 70
AAA BBB 10
BBB AAA 20
AAA CCC 40
DDD EEE 5
EEE DDD 70
FFF GGG 30
GGG HHH 20
HHH FFF 10
//输出2
0
#include<iostream>
#include<string>
#include<map>
using namespace std;
const int maxn = 2010; //总人数
const int INF = 1000000000; //无穷大
map<int, string> intToString; //编号->姓名
map<string, int> stringToInt; //姓名->编号
map<string, int> Gang; //head->人数
int G[maxn][maxn] = {0}, weight[maxn] = {0}; //邻接矩阵G，点权weight
int n, k, numPerson = 0; //边数n、下限k、总人数numPerson
bool vis[maxn] = {false}; //标记是否被访问
//DFS函数访问单个连通块，nowVisit为当前访问的编号
//head为头目，numMember为成员编号，totalValue为连通块的总边权/
void DFS(int nowVisit, int& head, int& numMember, int& totalValue) {
numMember++; //成员人数+1
vis[nowVisit] = true; //标记已被访问
if(weight[nowVisit] > weight[head]) {
head = nowVisit; //更新头目
}
for(int i = 0; i < numPerson; i++) {
if(G[nowVisit][i] > 0) { //如果nowVisit能到达i
totalValue += G[nowVisit][i]; //连通块的总边权增加该边权
G[nowVisit][i] = G[i][nowVisit] = 0; //删除这条边，防止回头
if(vis[i] == false) {
DFS(i, head, numMember, totalValue);
}
}
}
}
//DFSTrave函数遍历真个图，获得每个连通块的信息
void DFSTrave() {
for(int i = 0; i < numPerson; i++) {
if(vis[i] == false) {
int head = 1, numMember = 0, totalValue = 0;
DFS(i, head, numMember, totalValue);
if(numMember > 2 && totalValue > k) {
Gang[intToString[head]] = numMember;
}
}
}
}
//change函数返回姓名str对应的编号
int change(string str) {
if(stringToInt.find(str) != stringToInt.end()) { //如果str已经出现过，
return stringToInt[str]; //返回编号
} else {
stringToInt[str] = numPerson; //str的编号为numPerson
intToString[numPerson] = str; //numPerson对应str
return numPerson++;
}
}
int main() {
int w;
string str1, str2;
cin >> n >> k;
for(int i = 0; i < n ; i++) {
cin >> str1 >> str2 >> w;
int id1 = change(str1);
int id2 = change(str2);
weight[id1] += w;
weight[id2] += w;
G[id1][id2] += w;
G[id2][id1] += w;
}
DFSTrave();
cout << Gang.size() << endl;
map<string, int>::iterator it;
for(it = Gang.begin(); it != Gang.end(); it++) {
cout << it->first << " " << it->second << endl;
}
return 0;
}
采用广度优先搜索（BFS）遍历图
通过反复取出队首顶点，将该顶点可到达的未曾加入过队列（而不是未访问）的顶点全部入队，直到队列为空时遍历结束。
伪代码：
BFS(u) { //遍历u所在的连通块
queue q; //定义队列q
将u入队;
inq[u] = true; //设置u已入过队
while(q非空) { //只要队列非空
取出q的队首元素u进行访问
for(从u出发可达的所有顶点v) { //枚举从u能直接到达的顶点v
if(inq[v] == false) { //如果v未曾加入过队列
将v入队；
inq[v] = true; //设置v已加入过队列
}
}
}
}
BFSTrave(G) { //遍历图G
for(G的所有顶点u) //枚举G的所有顶点
if(inq[u] == false) { //如果u未曾入过队列
BFS(u); //遍历u所在的连通块
}
}
邻接矩阵版本
bool inq[MAXV] = {false}; //记录顶点是否入过队列
void BFS(int u) {
queue<int> q;
q.push(u);
inq[u] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int v = 0; v < n; v++) {
if(inq[v] == false && G[u][v] != INF){
q.push(v);
inq[v] = true;
}
}
}
}
void BFSTrave() {
for(int u = 0; u < n; u++) {
if(inq[u] == false) {
BFS(u);
}
}
}
邻接表版本
vector<int> Adj[MAXN];
int n;
bool inq[MAXV] = {false};
void BFS(int u) {
queue<int> q;
q.push(u);
inq[u] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = 0; i < Adj[u].size();i++) {
int v = Adj[u][i];
if(inq[v] == false) {
q.push(v);
inq[v] = true;
}
}
}
}
void BFSTrave() {
for(int u = 0; u < n; u++) {
if(inq[u] == false) {
BFS(u);
}
}
}
如果需要存放顶点层号，需要定义结构体Node，存放顶点的编号和层号
struct Node {
int v;
int layer;
};
vector<Node> Adj[N];
void BFS(int s) {
queue<Node> q;
Node start;
start.v = s;
start.layer = 0;
q.push(start);
inq[start.v] = true;
inq(!q.empty()) {
Node topNode = q.front();
q.pop();
int u = topNode.v;
for(int i = 0; i < Adj[u].size(); i++) {
Node next = Adj[u][i];
next.layer = topNode.layer + 1;
if(inq[next.v] == false) {
q.push(next);
inq[next.v] = true;`
}
}
}
}
实例：
在微博中，每个用户都可能被若干个其他用户关注。而当该用户发布一条信息时，他的关注者就可以看到这条信息并选择是否转发它，且转发的信息也可以被转发者的关注者再次转发，但同一用户最多只能转发该信息一次（信息的最初发布者不会转发该信息）。现在给出N个用户的关注情况（即他们各自关注了哪些用户）以及一个转发层数上限L，并给出最初发布消息的用户编号，求在转发层上限内消息最多会被多少用户转发
//输入
7 3
3 2 3 4
0
2 5 6
2 3 1
2 3 4
1 4
1 5
2 2 6
//输出
4
5
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int MAXV = 1010;
struct Node {
int id;
int layer;
};
vector<Node> Adj[MAXV]; //邻接表
bool inq[MAXV] = {false};
int BFS(int s, int L) {
int numForward = 0;
queue<Node> q;
Node start;
start.id = s;
start.layer = 0;
q.push(start);
inq[start.id] = true;
while(!q.empty()) {
Node topNode = q.front();
q.pop();
int u = topNode.id;
for(int i = 0; i < Adj[u].size(); i++) {
Node next = Adj[u][i];
next.layer = topNode.layer + 1;
if(inq[next.id] == false && next.layer <= L) {
q.push(next);
inq[next.id] = true;
numForward++;
}
}
}
return numForward;
}
int main() {
Node user;
int n, L, numFollow, idFollow;
scanf("%d%d", &n, &L);
for(int i = 1; i <= n; i++) {
user.id = i;
scanf("%d", &numFollow);
for(int j = 0; j < numFollow; j++) {
scanf("%d", &idFollow);
Adj[idFollow].push_back(user);
}
}
int numQuery, s;
scanf("%d", &numQuery); //查询个数
for(int i = 0; i < numQuery; i++) {
memset(inq, false, sizeof(inq)); //inq数组初始化
scanf("%d", &s); //起始结点编号
int numForward = BFS(s, L); //BFS，返回转发数
printf("%d\n", numForward); //输出转发数
}
return 0;
}
