图 (Graph) 主要由两个要素组成：顶点 (或节点)(Vertex) 和边 (Edge)。

图主要分为无向图(Undirected Graph)，有向图(Directed Graph)，和加权图(Weighted Graph)。

graph

例如这是一个无向图↑

图的储存

图的储存可以通过结构体和vector数组实现，通过输入图的边来储存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<int> G[100005];
int main(int argc, char *argv[]) {
	cin >> n >> m;//n为节点数 m为边的个数
	for(int i = 1;i <= m;i++)
	{
		int u,v;//u,v为两个节点的编号
		cin >> u >> v;
		G[u].push_back(v);//如果是无向图，则需每条边正反两次存入vector数组
		G[v].push_back(u);//如果是有向图，则仅需要每条边单词次存入vector数组，此句不执行
	}
}

图的遍历

图的遍历可以使用深度优先搜索(DFS)和广度优先搜索(BFS)。

两种遍历方法思路相似，如下：

  1. 选择一个节点开始遍历
  2. 搜索与该节点相连的边
  3. 通过边找到下一个遍历的节点
  4. 查询该节点是否被访问过
  5. 若没有，则对其遍历
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
bool vis[100005];//vis[n]标记n节点是否已访问
void dfs(int x)
{
	vis[x] = 1;//标记x节点已被访问
	for(auto p : G[x])
	{
		if(vis[p]) continue;//若p节点已访问，则跳过
		dfs(p);
	}
}
void bfs(int x)
{
	vis[x] = 1;//标记x节点已被访问
	q.push(x);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		for(auto p : G[u])
		{
			if(vis[p]) continue;//若p节点已访问，则跳过
			vis[p] = 1;//标记p节点已被访问
			q.push(p);
		}
	}
}