図アルゴリズムのまとめ

一般的な図アルゴリズムをまとめます.
kruskyal
mstを作成して、辺を押して小さい時から大巡回して、もし辺の鳴動ノードが異なる集合にあるならば、この辺はmstの中の1つの辺です.この場所は知識が必要です.

テーマ:[jobdu-10017]

コード

#include 
#include 
#include 
#define N 100
int tree[N + 8];

struct Edge {
    int u;
    int v;
    int w;
    Edge() {}
    Edge( int uu, int vv, int ww ) : u(uu), v(vv), w(ww) {}
    bool operatorconst Edge& rhs ) const {
        return w< rhs.w;
    }
};

typedef std::vector EdgeList;

int find_root(int x){
    if( tree[x] == -1 ) return x;
    else{
        int tmp = find_root( tree[x] );
        tree[x] = tmp;
        return tmp;
    }
}

int main( void ){
    int n = 0;
    while( std::cin >> n, n ){
        EdgeList edge_list;
        for( int i = 1; i <= n; ++i ) tree[i] = -1;
        for( int i = 0; i < n*(n-1)/2; ++i ){
            int u, v, w;
            std::cin >> u >> v >> w;

            Edge edge(u, v, w);
            edge_list.push_back(edge);
        }

        std::sort( edge_list.begin(), edge_list.end() );

        int ans = 0;
        int n = edge_list.size();
        for(int i = 0; i < n; ++i){
            int uu = edge_list[i].u;
            int vv = edge_list[i].v;
            int ww = edge_list[i].w;

            int a = find_root(uu);
            int b = find_root(vv);
            if( a == b ) continue;
            else{
                ans += ww;
                tree[a] = b;
            }
        }
        std::cout << ans << std::endl;
    }
    return 0;
}

dijkstra
経路長に基づいて順次増加するので、w＞0

テーマ:[jobdu-187]

コード

#include 
#include 
#include 
#define N 100

struct Edge {
    int node;
    int weight;
    Edge() {}
    Edge( int n, int w ) : node(n), weight(w) {}
};

typedef std::vector EdgeList;

EdgeList adj_list[N + 8];
int d[N+8];
int flag[N+8];

int dijk( int n, int s, int t );
void relax( int u, int v, int w );

int main( void ){
    int n,m;
    while(std::cin >> n >> m){
        if( !n && !m ) break;
        for( int i = 1; i <= n; ++i ) adj_list[i].clear();

        for( int i = 0; i < m; ++i ){
            int u,v,w;
            std::cin >> u >> v >> w;
            Edge edge(v,w);
            adj_list[u].push_back(edge);
            Edge edge1(u,w);
            adj_list[v].push_back(edge1);
        }

        int ans = dijk( n, 1, n );
        std::cout << ans << std::endl;
    }
    return 0;
}

int dijk( int n, int s, int t ){
    for( int i = 1; i <= n; ++i ){
        d[i] = INT_MAX;
    }
    d[s] = 0;

    for( int i = 1; i <= n; ++i ) flag[i] = 0;

    int cnt = n;
    while(cnt--){
        int u;
        int min = INT_MAX;
        for( int i = 1; i <= n; ++i ){
            if( flag[i] ) continue;
            if( d[i] < min ){
                u = i;
                min = d[i];
            }
        }

        flag[u] = 1;
        if( u == t ) break;

        int sz = adj_list[u].size();
        for( int k = 0; k < sz; ++k ){
            int v = adj_list[u][k].node;
            int w = adj_list[u][k].weight;
            relax(u, v, w);
        }
    }
    return d[t];
}

void relax( int u, int v, int w ){
    if( d[u] + w < d[v] )
        d[v] = d[u] + w;
}

bellman-ford
注意したいのは、bellman-fordの基本的な考え方は段階によって順次緩和するやり方です.dijkは、経路長によって順次増加する.全体の考えが違う.bellman-fordがV-1回緩和する理由は、一番長いルートが彼がチェーンに縮退しているからです.このときN個の頂点の図は、一番長い辺がN-1です.毎回、すべての辺を緩める.もし、すべての階層が緩和されたら.更に緩みが順次発見されても緩和が可能であることは、この図に負の側面があることを証明する.

テーマ:同上

コード

#include 
#include 
#include 
#define N 100

struct Edge {
    int node;
    int weight;
    Edge() {}
    Edge( int n, int w ) : node(n), weight(w) {}
};

typedef std::vector EdgeList;

EdgeList adj_list[N + 8];
int d[N+8];

int bellman_ford( int n, int s, int t );
void relax( int u, int v, int w );

int main( void ){
    int n,m;
    while(std::cin >> n >> m){
        if( !n && !m ) break;
        for( int i = 1; i <= n; ++i ) adj_list[i].clear();

        for( int i = 0; i < m; ++i ){
            int u,v,w;
            std::cin >> u >> v >> w;
            Edge edge(v,w);
            adj_list[u].push_back(edge);
            Edge edge1(u,w);
            adj_list[v].push_back(edge1);
        }

        int ans = bellman_ford( n, 1, n );
        std::cout << ans << std::endl;
    }
    return 0;
}

int bellman_ford( int n, int s, int t ){
    for(int i = 1; i <= n; ++i) d[i] = INT_MAX;
    d[s] = 0;

    for( int cnt = 0; cnt < n-1; ++cnt ){ // V-1 
        // relax every edge
        for( int u = 1; u <= n; ++u ){
            int sz = adj_list[u].size();
            for( int k = 0; k < sz; ++k ){
                int v = adj_list[u][k].node;
                int w = adj_list[u][k].weight;
                relax(u, v, w);
            }
        }
    }

    for( int u = 1; u <= n; ++u ){
        int sz = adj_list[u].size();
        for( int k = 0; k < sz; ++k ){
            int v = adj_list[u][k].node;
            int w = adj_list[u][k].weight;
            if( d[u] + w < d[v] )
                return -1;
        }
    }
    return d[t];
}

void relax( int u, int v, int w ){
    if( d[u] + w < d[v] )
        d[v] = d[u] + w;
}

spfa
大体の思想はbellman-fordから来ていますが、毎回ただ緩んで有効な辺だけで、すべての辺を緩める必要はありません.これは彼の主な思想です.2つのデータ構造が追加されました.visited[v]は、vというノードがキューの中でcount[v]を表しています.vの入隊回数を表しています.N-1回を超えると.負の辺があります.例えば、2つの頂点の図だけがあります.2つの辺があります.1つは負です.このような状況があります.

#include 
#include 
#include 
#include 
#define N 100

struct Edge {
    int node;
    int weight;
    Edge() {}
    Edge( int n, int w ) : node(n), weight(w) {}
};

typedef std::vector EdgeList;

EdgeList adj_list[N + 8];
int d[N+8];
int visited[N+8]; // in the queue or not
int count[N+8];

int spfa( int n, int s, int t );

int main( void ){
    int n,m;
    while(std::cin >> n >> m){
        if( !n && !m ) break;
        for( int i = 1; i <= n; ++i ) adj_list[i].clear();

        for( int i = 0; i < m; ++i ){
            int u,v,w;
            std::cin >> u >> v >> w;
            Edge edge(v,w);
            adj_list[u].push_back(edge);
            Edge edge1(u,w);
            adj_list[v].push_back(edge1);
        }

        int ans = spfa( n, 1, n );
        std::cout << ans << std::endl;
    }
    return 0;
}

int spfa( int n, int s, int t ){
    for(int i = 1; i <= n; ++i) d[i] = INT_MAX;
    d[s] = 0;

    for( int i = 1; i <= n; ++i ){ visited[i] = 0; count[i] = 0; }

    std::queue<int> que;
    que.push(s);
    visited[s] = 1;
    count[s] += 1;

    while( !que.empty() ){
        int u = que.front();
        que.pop();
        visited[u] = 0;

        int sz = adj_list[u].size();
        for( int k = 0; k < sz; ++k ){
            int v = adj_list[u][k].node;
            int w = adj_list[u][k].weight;
            if( d[u] + w < d[v] ){
                d[v] = d[u] + w;
                if( visited[v] == 0 ){
                    que.push(v);
                    visited[v] = 1;
                    count[v] += 1;
                    if( count[v] > n-1 )
                        return -1;
                }
            }
        }
    }
    return d[t];
}

topsport
トポロジ順序は、viからvjまでのエッジが存在する場合、vjの前にviが配置される頂点シーケンスである.具体的には毎回0度の点を探して、これらの点の指す辺を削除します.n回繰り返したり、0度のない点は削除できます.
トポロジ順序が複数存在する可能性があるのは、度0の点選択が異なるからである.

テーマ:[jobdu-188]

コード

#include 
#include 
#include 
#define N 100

typedef std::vector<int> EdgeList;
EdgeList adj_list[N + 8];
int indegree[N + 8];

int main( void ){
    int n, m;
    while( std::cin >> n >> m ){
        if( !n && !m ) break;
        for( int i = 0; i < n; ++i ){ adj_list[i].clear(); indegree[i] = 0; }
        for( int i = 0; i < m; ++i ){
            int u,v;
            std::cin >> u >> v;
            adj_list[u].push_back(v);
            ++indegree[v];
        }

        std::queue<int> q;
        for( int i = 0; i < n; ++i ){
            if( !indegree[i] )
                q.push(i);
        }

        int cnt = 0;
        while(!q.empty()){
            int u = q.front();
            q.pop();
            ++cnt;

            int sz = adj_list[u].size();
            for( int k = 0; k < sz; ++k ){
                int v = adj_list[u][k];
                --indegree[v];
                if( !indegree[v] ) q.push(v);
            }
        }

        if( cnt == n ) std::cout << "YES" << std::endl;
        else std::cout << "NO" << std::endl;
    }

    return 0;
}