圖的遍歷方法一般有兩種：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）
采用深度優(yōu)先搜索（DFS）遍歷圖
沿著一條路徑直到無法繼續(xù)前進，才退回到路徑上離當前頂點最近的還存在未訪問分支頂點的岔道口象迎，并前往訪問那些未訪問分支頂點揽趾，直到遍歷完整個圖。
兩個概念：
連通分量：在無向圖中亭姥，如果兩個頂點之間可以相互到達（可以是通過一定路徑間接到達）稼钩，那么就稱這兩個頂點連通。如果G(V,E)的任意兩個頂點都連通达罗，則稱圖G為連通圖坝撑；否則，稱圖G為非連通圖粮揉，且稱其中的極大連通子圖為連通分量巡李。
強連通分量：在有向圖中，如果兩個頂點可以各自通過一條有向路徑到達另一個頂點扶认，就稱這兩個頂點強連通侨拦。如果圖G(V,E)的任意兩個頂點都強連通，則稱圖G為強連通圖蝠引；否則阳谍，稱圖G為非強連通圖，且稱其中的極大強連通子圖為強連通分量螃概。
把連通分量和強連通分量均稱為連通塊
如果要遍歷整個圖矫夯，就需要對所有連通塊分別進行遍歷。
基本思路：將經(jīng)歷過的頂點設置為已訪問吊洼，在下次遞歸碰到這個頂點時就不再去處理训貌，直到整個圖的頂點都被標記為已訪問。
如已知給定的圖時一個連通圖冒窍，則只需要一次DFS就能完成遍歷
偽代碼:
DFS(u) { //訪問頂點u
vis[u] = true; //設置u已被訪問
for(從u出發(fā)能到達的所有頂點v) //枚舉從u出發(fā)可以到達的所有頂點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所在的連通塊
}
實現(xiàn)鄰接矩陣和鄰接表前需要先定義MAXV為最大頂點數(shù)递沪、INF為一個很大的數(shù)字
const int MAXV = 1000; //最大頂點數(shù)
const int INF = 1000000000; //設INF為一個很大的數(shù)
鄰接矩陣版本
int n, G[MAXV][MAXV]; //n為頂點數(shù)，MAXV為最大頂點數(shù)
bool vis[MAXV] = {false}; //如果頂點i已被訪問综液，則vis[i] == true款慨。初值為false
void DFS(int u, int depth) { //u為當前訪問的頂點標號，depth為深度
vis[u] = true; //設置u已被訪問
//如果需要對u進行一些操作谬莹，可以在這里進行
//下面對所有從u出發(fā)能到達的分支頂點就像枚舉
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為頂點數(shù)埠戳，MAXV為最大頂點數(shù)
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表示初始為第一層
}
}
)
實例:
給出若干人之間的通話長度（視為無向邊）在岂，這些通話將他們分為若干組。每個組的總邊權設為該組內(nèi)的所有通話的長度之和屋灌，而每個人的點權設為該人參與的通話長度之和〗喽危現(xiàn)在給定一個閥值K，且只要一個組的總邊權超過K共郭，并滿足成員人數(shù)超過2祠丝，則將該組視為”犯罪團伙(Gang)“，而該組內(nèi)點權最大的人視為頭目除嘹。要求輸出”犯罪團伙“的個數(shù)写半，并按頭目姓名字典序從小到大的順序輸出每個”犯罪團伙“的頭目姓名和成員人數(shù)。
思路：
- 解決姓名和編號的對應關系尉咕〉可使用map<string, int>直接建立字符串與整型的映射關系，也可使用字符串hash的方法將字符串轉(zhuǎn)換為整型年缎。編號與姓名的對應關系則可以直接使用string數(shù)字進行定義悔捶，或者使用map<int, string>也是可以的
- 需要獲得每個人的點權，即與之相關的通話記錄的時長之和单芜，可以在讀入時進行處理蜕该。該步在求與某個點相連的邊的邊權之和
- 圖的遍歷。使用DFS遍歷每個連通塊洲鸠，目的是獲取每個連通塊的頭目（即連通塊內(nèi)點權最大的結點）堂淡、成員個數(shù)、總邊權
- 通過步驟3可以獲得連通塊的總邊權totalValue扒腕。如果totalValue大于給定的閥值K绢淀，且成員人數(shù)大于2，則說明該連通塊是一個團伙瘾腰，將該團伙的信息存儲下來
可以定義map<string, int>皆的，來建立團伙頭目的姓名與成員人數(shù)的映射關系。由于map中元素自動按鍵從小到大排序蹋盆。
注意點：
- 由于通話記錄的條數(shù)最多有1000條祭务，意味著不同的人可能有2000人内狗，因此數(shù)組大小必須在2000以上
- 可以使用使用結構體來存放頭目姓名與成員人數(shù)怪嫌，但會增加一定代碼量
struct Gang {
string head; //團伙頭目
int numMember; //成員數(shù)量
}arrayGang[maxn];
int numGang = 0; //團伙個數(shù)
bool cmp(Gang a, Gang b) {
return a.head < b.head; //按頭目姓名的字典序從小到大排序
}
- 由于每個結點在訪問后不應再次被訪問义锥，但是圖中可能有環(huán)，即遍歷過程中發(fā)生一條邊連接已訪問結點 的情況岩灭。此時為了邊權不被漏加拌倍，需要先累加邊權，再去考慮結點遞歸訪問的問題
- 本題也可用并查集解決
//輸入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; //總人數(shù)
const int INF = 1000000000; //無窮大
map<int, string> intToString; //編號->姓名
map<string, int> stringToInt; //姓名->編號
map<string, int> Gang; //head->人數(shù)
int G[maxn][maxn] = {0}, weight[maxn] = {0}; //鄰接矩陣G噪径，點權weight
int n, k, numPerson = 0; //邊數(shù)n柱恤、下限k、總人數(shù)numPerson
bool vis[maxn] = {false}; //標記是否被訪問
//DFS函數(shù)訪問單個連通塊找爱，nowVisit為當前訪問的編號
//head為頭目梗顺，numMember為成員編號，totalValue為連通塊的總邊權/
void DFS(int nowVisit, int& head, int& numMember, int& totalValue) {
numMember++; //成員人數(shù)+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函數(shù)遍歷真?zhèn)€圖寺谤，獲得每個連通塊的信息
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函數(shù)返回姓名str對應的編號
int change(string str) {
if(stringToInt.find(str) != stringToInt.end()) { //如果str已經(jīng)出現(xiàn)過，
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;
}
采用廣度優(yōu)先搜索（BFS）遍歷圖
通過反復取出隊首頂點吮播，將該頂點可到達的未曾加入過隊列（而不是未訪問）的頂點全部入隊变屁，直到隊列為空時遍歷結束。
偽代碼：
BFS(u) { //遍歷u所在的連通塊
queue q; //定義隊列q
將u入隊;
inq[u] = true; //設置u已入過隊
while(q非空) { //只要隊列非空
取出q的隊首元素u進行訪問
for(從u出發(fā)可達的所有頂點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;`
}
}
}
}
實例：
在微博中环戈，每個用戶都可能被若干個其他用戶關注闷板。而當該用戶發(fā)布一條信息時，他的關注者就可以看到這條信息并選擇是否轉(zhuǎn)發(fā)它院塞，且轉(zhuǎn)發(fā)的信息也可以被轉(zhuǎn)發(fā)者的關注者再次轉(zhuǎn)發(fā)遮晚，但同一用戶最多只能轉(zhuǎn)發(fā)該信息一次（信息的最初發(fā)布者不會轉(zhuǎn)發(fā)該信息）。現(xiàn)在給出N個用戶的關注情況（即他們各自關注了哪些用戶）以及一個轉(zhuǎn)發(fā)層數(shù)上限L迫悠，并給出最初發(fā)布消息的用戶編號鹏漆，求在轉(zhuǎn)發(fā)層上限內(nèi)消息最多會被多少用戶轉(zhuǎn)發(fā)
//輸入
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); //查詢個數(shù)
for(int i = 0; i < numQuery; i++) {
memset(inq, false, sizeof(inq)); //inq數(shù)組初始化
scanf("%d", &s); //起始結點編號
int numForward = BFS(s, L); //BFS，返回轉(zhuǎn)發(fā)數(shù)
printf("%d\n", numForward); //輸出轉(zhuǎn)發(fā)數(shù)
}
return 0;
}
