图论基础

定义

由顶点v和边e构成的集合，记G=(v,e)

其他重要概念

• 路径：一个顶点到达另一个顶点途径的点构成的序列

• 边权：边的权重（在不同场景下意义不同）

  在求最短路问题中，权重可以代表距离；在网络流问题中，权重可以代表流量…

分类

有向图、无向图、有权图、无权图、连通图······

应用

导航、网络拓扑图、电路图、游戏地图、自动寻踪

图的存储

1. 邻接矩阵

采用数据结构：二维数组

存储思路：存储的是邻接（居）点

有边置1 无边置0 无向图要注意双向标注

例如给出这样一张图

• 邻接矩阵的输入

#include<iostream>
using namespace std;

const int N = 1e2 + 10;
int g[N][N];
//如果i,j顶点之间有边  g[i][j]=1
//如果i,j顶点之间没边  g[i][j]=0

int main() {
	int n,m;
    cin >> n >> m;
    //控制台输入
    for(int i=1;i<=m;i++){
        int u,v;
        cin >> u >> v;
        g[u][v] = g[v][u] = 1;
    }
	return 0;
}

• 找到指定点的所有邻接点

int v; cin >> v;
int n = 4;
for (int i = 1; i <= n; i++) {
	if (g[v][i] == 1) {//i是v的邻接点
		cout << i << " ";
	}
}

• 找到邻接矩阵所有的边

int n = 4;
for (int v = 1; v <= n; v++) {//固定v
	for (int u = 1; u <= n; u++) {//找到v的所有邻接点u
		if (g[u][v] == 1) {//v是u的邻接点
			printf("(%d,%d) ", u, v);
		}
	}
	cout << endl;
}

性能

• 时间复杂度：（遍历所有的边）$O(n^2)$
• 空间复杂度：$O(n^2)$

2. 邻接表（优化）

采用数据结构：一维数组（外层）+ 动态数组vector（内层）

vector<int> g[N];

g[i]是一个vector，存储了i号点所有邻接点

我们将一开始的图按照数据结构抽象成这种形式，以上述图为例:

• 邻接表的输入方式

vector增加元素使用push_back()

#include<iostream>
#include<vector>
using namespace std;

const int N = 1e2 + 10;
vector<int> g[N];   //g[i]是一个vector，存储了i号点所有邻接点

int main() {

	int n, m; cin >> n >> m;//n个顶点 m条边
	//邻接m条边,每条边遍历一遍
	for (int i = 1; i <= m; i++) {
		int u, v; 
        cin >> u >> v;//u-v之间有边
		g[u].push_back(v);  g[v].push_back(u);  //无向图
		//g[u].push_back(v);   //有向图
	}
	return 0;

}

• 邻接表边的遍历

#include<iostream>
#include<vector>
using namespace std;

const int N = 1e2 + 10;
vector<int> g[N];//g[i]是一个vector，存储了i号点所有邻接点

int main() {

	int n, m; cin >> n >> m;//n个顶点m条边
	//邻接m条边
	for (int i = 1; i <= m; i++) {
		int u, v; 
        cin >> u >> v;//u-v之间有边
		g[u].push_back(v);  g[v].push_back(u);  //无向图
		//g[u].push_back(v);   //有向图
	}
	
	//找出图中所有的边
	for (int i = 1; i <= n; i++) {//固定i
		//找到顶点i的所有邻接点
		for (int j = 0; j < g[i].size(); j++) {
			int v = g[i][j];
			printf("(%d,%d) ", i, v);
		}
        cout << endl;
	}
	return 0;

}

性能

• 时间复杂度：（遍历所有的边）$O(n+m)$

• 空间复杂度：$O(m)$