再话图算法之图的遍历

前言

定义,出度入读,有向图无向图,点权边权,邻接矩阵,邻接链表,有向图的强连通分量,无向图的连通分量,连通块..

1
2
3
4
5
struct Node{
int v,w;
Node(int _v,int _w): v(_v),w(_w) {} //constructor
}
Adj[index].push_back(Node(3,4));

DFS

dfs
在实际的题目中,可能遇到比较坑的情况,比如要删边避免回路。
邻接矩阵实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int MAXV=1000; //max vertices,设计算法不能超过千万级别复杂度
const int INF=1000000000;

int n,G[MAXV][MAXV];
bool vis[MAXV]={false}; //bool array要显式初始化

void DFS(int u,int depth)
{
vis[u]=true;
//do something for u in here
/**/
//下面对所有u能够直接到达的分支节点进行枚举
for(int v=0;v<n;v++)
{
if(vis[v]==false&&G[u][v]!=INF) //未被访问且可达
{
DFS(v,depth+1);
}
}
}

void DFSTraverse()
{
for(int u=0;u<n;u++)
{
if(vis[u]==false)
{
DFS(u,1);
}
}
}

邻接链表实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> Adj[MAXV];
int n;
bool vis[MAXV]={false};

void DFS(int u,int depth)
{
vis[u]=true;
//do something at u in here
/**/
for(int i=0;i<Adj[u].size();i++){
int v=Adj[u][i];
if(vis[v]==false){
DFS(v,depth);
}
}
}

void DFSTraverse()
{
for(int u=0;u<n;u++)
{
if(vis[u]==false)
{
DFS(u,1);
}
}
}

一道比较好的题目在P359,有空回头刷刷。

BFS

邻接矩阵版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int n,G[MAXV][MAXV];
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 BFSTraverse()
{
for(int u=0;u<n;u++)
{
if(inq[u]==false)
{
BFS(q);
}
}
}

邻接链表版:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
vector<int> Adj[MAXV];
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 BFSTraverse()
{
for(int u=0;i<n;i++)
{
if(inq[u]==false)
{
BFS(u);
}
}
}

有时候需要给定BFS的层次,这时候需要进行一些调整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct Node{
int v;
int layer;
}

vector<Node> Adj[N];
void BFS(int s)
{
queue<Node> q;
Node start(s,0); //起始点s,层次为0
q.push(start);
inq[start.v]=true;
while(!q.empty())
{
Node top=q.front();
q.pop();
int u=top.v;
for(int i=0;i<Adj[u].size();i++)
{
Node next=Adj[u][i];
next.layer=top.layer+1;
if(inq[next.v]==false)
{
q.push(next);
inq[next.v]=true;
}
}
}
}

同样的好题在P365,有空回来看看。