存图方式一共有三种：邻接矩阵、邻接表、前向星
纯前向星还需要再加上排序的时间复杂度（当排序不是主要复杂度时适用），如果快排，时间复杂度是O(n log n)，可以用别的排序方式优化，即基数排序（不写纯前向星了，不会写基数排序 ）
事实上，不用排序也能模仿出来前向星的核心思路，即链式前向星，链式前向星也是最常用的存图方式
邻接矩阵
int edge[100][100],vis[100],m,n;
void add_edge(int u,int v,int w) //添加边
{
edge[u][v]=w;
}
void dfs(int x) //遍历
{
vis[x]=1;
cout<<x;
for(int i=1;i<=n;i++)
{
if(edge[x][i]&&!vis[i])
{
cout<<"->";
dfs(i);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,w);
}
dfs(1);
return 0;
}
/*
test
4 5
1 2 5
1 3 8
1 4 7
2 3 6
3 4 9
*/
邻接表（链式前向星）
int n,m,cnt,head[100],vis[100];
struct edge{
int nxt,to,w;
}e[100];
void add_edge(int u,int v,int w)
{
e[++cnt] = (edge){head[u],v,w};
head[u] = cnt;
}
void dfs(int x)
{
cout<<x;
vis[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
if(!vis[e[i].to])
{
cout<<"->";
dfs(e[i].to);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,w);
}
dfs(1);
return 0;
}
邻接表（vector存边）
vector<pair<int,int>> e[100];
int n,m,vis[100];
void add_edge(int u,int v,int w) //存边
{
e[u].push_back(make_pair(v,w));
}
void dfs(int x) //遍历
{
cout<<x;
vis[x]=1;
for(int i=0;i<e[x].size();i++)
{
if(!vis[e[x][i].first])
{
cout<<"->";
dfs(e[x][i].first);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
add_edge(u,v,w);
add_edge(v,u,w);
}
dfs(1);
return 0;
}