对于边数相对顶点较少的图，我们使用一种存储结构的方式：邻接表（Adjacency List），即数组与链表相结合的存储方法。
无向图带权值的邻接表结构：
TREE
建树：
for(i=0; i<n; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
s[cnt].to=v;
s[cnt].w=w;
s[cnt].next=head[u];
head[u]=cnt++;
s[cnt].to=u;
s[cnt].w=w;
s[cnt].next=head[v];
head[v]=cnt++;
}
TREE
DFS遍历：
void DFS(int u)
{
vis[u]=true;
for(int i=head[u]; i!=-1; i=s[i].next)
{
int v=s[i].to;
int w=s[i].w;
printf("%d %d\n", v, w);
if(vis[v]==false) DFS(v);
}
}
DFS
代码:
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int to, next, w;
} s[10005];
int head[10005];
bool vis[10005];
void DFS(int u)
{
vis[u]=true;
for(int i=head[u]; i!=-1; i=s[i].next)
{
int v=s[i].to;
int w=s[i].w;
printf("%d %d\n", v, w);
if(vis[v]==false) DFS(v);
}
}
int main()
{
int i, n, cnt=1;
scanf("%d", &n);
memset(head, -1, sizeof(head));
memset(vis, false, sizeof(vis));
for(i=0; i<n; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
s[cnt].to=v;
s[cnt].w=w;
s[cnt].next=head[u];
head[u]=cnt++;
s[cnt].to=u;
s[cnt].w=w;
s[cnt].next=head[v];
head[v]=cnt++;
}
DFS(1);
return 0;
}
