图的储存

  对于图的储存是做图论题的基础，图的储存主要有两种方式，一个是邻接表，一个是邻接矩阵。两种储存方式有时候可以通用，但有一些图论题却不能混用。

  邻接矩阵实现方式很简单，直接就是创建一个二维数组G[N][N]，对于点x，y，G[x][y]的值就是x->y这一条边的权值。

#include<iostream>

#define INF 0x3f3f3f3f

using namespace std;

int G[N][N];

int N = 1e4+5;

int main()

{

int x,y,w;

int n,m;//图有n个点，有m条边

cin>>n;

//对邻接矩阵初始化

for(int i=0;i<=n;i++)

{

for(int j=0;j<=n;j++)

{

if(i==j)

G[i][j]=0;//点i就是点j，权值为零

else

G[i][j]=G[j][i]=INF;//点i和点j不连通，也就是i和j的权值无限大（无向图）

//G[i][j]=INF;有向图

 }

}

for(int i=0;i<m;i