基于vector存图
struct Edge
{
int u, v, w;
Edge(){}
Edge(int u, int v, int w):u(u), v(v), w(w){}
};
vector<Edge>edges;//把每一条边存下来
vector<int>Map[maxn];//G[i]这个vector存的是以i为起点的所有边在edges里面的下标
void init(int n)
{
for(int i = ; i <= n; i++)Map[i].clear();
edges.clear();
}
void addedge(int u, int v, int w)
{
edges.push_back(Edge(u, v, w));//注意无向图需要存两条边
m = edges.size();
Map[u].push_back(m - );
}
void Find(int u)//遍历以u为起点的所有边
{
for(int i = ; i < Map[u].size(); i++)
{
Edge&e = edges[Map[u][i]];
//使用e就可以遍历以u为起点的所有的边
}
}
用邻接矩阵的代码比较简单，就不加上来了
使用链表前向星存图
https://www.cnblogs.com/ECJTUACM-873284962/p/6905416.html
struct edge
{
int next;//指向下一个节点
int u, v, w;
};
edge a[maxn];
int head[maxn], node;//node记录节点的数目，head[i]记录连接着i的第一条边
void add(int u, int v, int w)
{
a[node].u = u;
a[node].v = v;
a[node].w = w;
a[node].next = head[u];
head[u] = node++;
}
void init()
{
node = ;
memset(head, -, sizeof(head));
}
void Find(int u)
{
for(int i = head[u]; i != -; i = a[i].next)
{
edge& e = a[i];
//e就是连接着u的所有边
}
}