邻接表——数组实现

邻接表用数组来实现。采用头插法。

#include <iostream>
using namespace std;
const int H = 10;
int main()
{
    int u[H*2],v[H*2],w[H*2];
    int first[H];//first[i]表示i号节点的第一条边
    int next[H*2];//next[i]表示第i条边的下一条边

    int n,m;//n个节点，m条边
    cin>>n>>m;

    //初始化，全都没有边
    for( int i=1; i<n; ++i )
        first[i] = -1;



----------

    //有向图的存储
    /*
    for( int i=1; i<=m; ++i ){
        cin>>u[i]>>v[i]>>w[i];
        next[i] = first[u[i]];
        first[u[i]] = i;
    }
    */

----------

    //无向图的存储

    for( int i=1; i<=m; ++i ){
        cin>>u[i]>>v[i]>>w[i];
    }
    //反着存一遍
    for( int i=m+1; i<=2*m; ++i ){

        u[i] = v[i-m];
        v[i] = u[i-m];
        w[i] = w[i-m];
    }
    for( int i=1; i<=2*m; ++i ){

        next[i] = first[u[i]];
        first[u[i]] = i;
    }

----------


    cout << "show:\n";
    for( int i=1; i<=n; ++i ){
        int k = first[i];
        while( -1!=k ){
            cout<<u[k]<<' '<<v[k]<<' '<<w[k]<<endl;
            k = next[k];
        }
    }

    return 0;
}