Adjacency List邻接表

对于边数相对顶点较少的图，我们使用一种存储结构的方式：邻接表（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;
}