對(duì)于邊數(shù)相對(duì)頂點(diǎn)較少的圖，我們使用一種存儲(chǔ)結(jié)構(gòu)的方式：鄰接表（Adjacency List），即數(shù)組與鏈表相結(jié)合的存儲(chǔ)方法。

無(wú)向圖帶權(quán)值的鄰接表結(jié)構(gòu)：

TREE

建樹(shù)：

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;
}