邻接矩阵

简单,不讲

g[i][j]表示从i到j的边权


邻接表(数组)

u, v, w记录边的信息
first初始化-1,表示没有边
first[u[i]]保存u[i]的第一条边编号,next[i]存储编号为i的边的下一条边的编号

如图

模版

无向图

#include<cstdio>
#define N 100
using namespace std;
int main()
{
    int m;
    scanf("%d", &m);
    int first[N*2], next[N*2];
    for(int i=0; i<N; ++i)
    	first[i] = -1;
    int u[N*2], v[N*2], w[N*2];
    for(int i=1; i<=m*2; i+=2)
    {
    	scanf("%d%d%d", &u[i], &v[i], &w[i]);
    	u[i+1] = v[i];
    	v[i+1] = u[i];
    	w[i+1] = w[i];
    	next[i] = first[u[i]];
    	first[u[i]] = i;
    	next[i+1] = first[u[i+1]];
    	first[u[i+1]] = i+1;
	}
	int k;
	for(int i=1; i<=m*2; ++i)
	{
		k = first[i];
		while(k != -1)
		{
			printf("%d %d %d\n", u[k], v[k], w[k]);
			k = next[k];
		}
	}	
    return 0;
}

有向图

#include<cstdio>
using namespace std;
int main()
{
    int m, n;
    scanf("%d%d", &n, &m);
    int first[n+1], next[m+1];
    for(int i=0; i<N; ++i)
    	first[i] = -1;
    int u[m+1], v[m+1], w[m+1];
    for(int i=1; i<=m; ++i)
    {
    	scanf("%d%d%d", &u[i], &v[i], &w[i]);
    	next[i] = first[u[i]];
        first[u[i]] = i;
	}
	int k;
	for(int i=1; i<=n; ++i)
	{
		k = first[i];
		while(k != -1)
		{
			printf("%d %d %d\n", u[k], v[k], w[k]);
			k = next[k];
		}
	}	
    return 0;
}