图的存储

邻接矩阵

设图的结点个数为 \(n\)，定义 \(n\times n\) 的二维数组 \(g[N][N]\)，其中 \(g[i][j]\) 表示结点 \(i\) 到 \(j\) 的边权。

对于带权图，\(g[i][j]=\begin{cases}w &边(i, j)的权值 \\ +\infty &边(i,j)无直接连边\end{cases}\)。

对于无权图，\(g[i][j]=\begin{cases}1 &i,j之间有连边 \\ 0 &i,j之间无连边\end{cases}\)。

对于带权图，常用

memset(g, 0x3f, sizeof(g));

对于无权图，常用

memset(g, 0, sizeof(g));

或直接定义全局变量即可。

加一条边 \((u, v, w)\)，其中起点为 \(u\)，终点为 \(v\)，权值为 \(w\)（无权图权值为 \(1\) 即可）

对于有向图

g[u][v] = w;

对于无向图

g[u][v] = w;
g[v][u] = w;

对于带权图

const int INF = 0x3f3f3f3f;
for (int i = 1; i <= n; i++) {
	if (g[s][i] < INF) {
		cout << i <<' ';
	}
}

对于无权图

for (int i = 1; i <= n; i++) {
	if (g[s][i] == 1) {
		cout << i <<' ';
	}
}