邻接矩阵

//用|V|*|V|二维数组来表示边的两端可达
int g[max_v][max_v];

邻接表建图

有两种：一种是直接用vector，还有一种是链式前向星

直接用vector：

struct edge {
	int to;
	int cost;//边的属性等等
	edge() {}
	edge(int t, int c) : to(t), cost(c) {}
}
vector<edge> G[MAX_V];
void add_edge(int u, int v, int c) {
	G[u].push_back(edge(v, c));
	//G[v].push_back(edge(u, c)); //无向边的时候
}

链式前向星：

struct edge{  //边的性质
    int u;   //起点
    int v;    //终点
    int dis;  //距离
    int cost;  //花费
    int nxt;  //下一条以u为起点的边，这个和链表类比
}cc[10010];
int head[maxn]; //head[v]表示起点是v的边组成的一条链（类似链表）
int cnt, ans; 
void add_edge(int u, int v, int d, int c) {
    cc[cnt].u = u;
    cc[cnt].v = v;
    cc[cnt].dis = d;
    cc[cnt].cost = c;
    cc[cnt].nxt = head[u]; //当前边的起点也就是整条链的首部是u
    head[u] = cnt++;  //以u为起点的最新的边变成了cnt这条边
}
//遍历的方法
for (int i = 1; i <= n; i++) { //依次输出的是以节点i为起点的边能到达的点，和邻接矩阵一个道理
	for (int j = head[i]; j != -1; j = cc[j].nxt) {
        printf("%d ", cc[j].v);
    }
    printf("\n") 
}

总结：


能用链式前向星就尽量用


vector邻接表操作灵活，易懂，但是占用内存大

刚开始接触的是vector邻接表，然后一直用的是vector，

前几天被一道题（POJ1724）卡了时间。。。。。。。


用链式前向星！！！！