遍历图
DFS $O(n + m)$ : 需要遍历所有的结点(可能为非连通图)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10;
int n, m;
bool st[N];
// 图的结点(邻接表法)
struct Node
{
int id;
Node* next;
Node (int _id): id(_id), next(NULL) {}
}*head[N]; // 每个结点有一个单链表
// 头插法: 将b插入head[a]中
void add(int a, int b)
{
auto p = new Node(b);
p->next = head[a];
head[a] = p;
}
void dfs(int t)
{
st[t] = true;
// dfs在枚举前输出
cout << t << " ";
// dfs 所有与t邻接的没访问过的结点
for (auto p = head[t]; p; p = p->next)
if (!st[p->id])
dfs(p->id); // 没访问过则继续dfs
}
int main()
{
cin >> n >> m;
// 将边a->b存到图中去
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
}
// dfs图的所有结点 (id: 1~n)
for (int i = 1; i <= n; i ++ )
if (!st[i])
dfs(i);
return 0;
}
BFS $O(n + m)$ 借助队列: 可以求最短路径(默认为连通图)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10;
int n, m;
bool st[N]; // 判重数组, 每个点只能走一次
// 邻接表存储图
struct Node
{
int id;
Node* next;
Node (int _id): id(_id), next(NULL) {}
}*head[N];
// 头插法: 将b插入head[a]中
void add(int a, int b)
{
auto p = new Node(b);
p->next = head[a];
head[a] = p;
}
// 宽搜: 借助队列 (求最短路径)
void bfs(int u)
{
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
// 取出队头元素并输出
auto t = q.front();
q.pop();
cout << t << " ";
// 入队 与队头t邻接且没遍历过的点
for (auto p = head[t]; p; p = p->next)
{
int j = p->id;
if (!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
int main()
{
cin >> n >> m;
// 将结点a->b存到图中去
while (m -- )
{
int a, b;
cin >> a >> b;
add(a, b);
}
bfs(1);
return 0;
}