図論:図の概念と図の貯蔵方式

転載先http://acm.uestc.edu.cn/bbs/read.php?tid=5670
pptアカウントのダウンロード:qscqesze
パスワード:123456
-------------------------------------------------------------------
1.図の基本概念
図:二元群(V,E).Vは頂点セットです.EはVにおけるノード間のエッジの集合である.
セルフループ:1つのエッジの2つの端点が同じです.
多重エッジ:2つの端点の間に2つ以上のエッジがあり、多重エッジと呼ばれます.
単純図:自己ループと多重エッジのない図
[エッジなし](None Edge):エッジは双方向です
有向エッジ有向エッジ:一方向エッジ、矢印
無方向図:無方向の図のみ
有向図:有向辺の図のみ
 
頂点の度合い:無方向図では、1つの頂点が接続されているエッジ数を頂点の度合いと呼びます.有向図では、1つの頂点から出発する辺数をその頂点導出度と呼ぶ.頂点に到達するエッジの数を入力と呼びます.
権限とネットワーク:
図のエッジに関連する数を与え,重みとなる.重みは、ある頂点から別の頂点までの距離、消費量などを表すことができます.帯権図は一般的に網となる.
完全図、稠密図、疎図:任意の2つの頂点間にエッジ(円弧)が接続されていることを完全図と呼びます.
エッジ(アーク)の少ない図を疎図と呼び,逆に稠密図と呼ぶ
2.図の記憶
隣接行列:
 

int g[max_v+1][max_v+1];

void init()//   

{

    for(int i=1;i<=max_v;i++)

        for(int j=1;j<=max_v;j++)

        {

            if(i==j)

                g[i][j]=0;

            else

                g[i][j]=inf;

        }

}

void add_edge(int a,int b,int c)

{

    g[a][b]=g[b][a]=c;//   

    //g[a][b]=c;     

}

 
 
 
空間複雑度:O(V^2)の利点:直感的で分かりやすく、任意の2点の関係を直接見ることができます.欠点:疎図では、利用されていないスペースがたくさんあります.重み付きマップでは、エッジの再処理はできません.頂点のすべてのエッジをクエリーするには、V回を列挙します.
 
隣接行列表現では,頂点自体の情報を格納するほか,各頂点間の関係を1つの行列で表す.(i,j)∈E(G)または〈i,j〉∈E(G)の場合、マトリクス内のi行目j列目の要素値は1であり、そうでなければ0である.
図の隣接行列は,1,(i,j)∈E(G)または〈i,j〉∈E(G)A[i][j]=0の場合,その他の場合と定義する.
例えば、以下は2つの無方向図と有方向図に対応する隣接行列である.
同様にネットワークの隣接行列を定義できるのは、wijが(i,j)∈E(G)または〈i,j〉∈E(G)A[i][j]=0であればi=j∞その他の場合である
図の格納-隣接テーブル

struct Edge

{

    int u,v;//  

}

vector<Edge> e[max_v+1];

void init()//   

{

    for(int i=1;i<=max_v;i++)

        e[i].clear();

}

void add_edge(int a,int b,int c)

{

    e[a].push_back((Edge){b,c});

    e[b].push_back((Edge){a,c});//     

}

スペースの複雑さ:図面O(V+E)図面O(V+2*E)なしの利点があります.スペースを節約し、関係のない頂点にアクセスすることなく、頂点に接続されているすべての頂点を迅速に見つけることができます.
図の各頂点に対して単一チェーンテーブル(n個の頂点に対してn個の単一チェーンテーブル)を作成し、i番目の単一チェーンテーブルのノードは頂点Viのすべての隣接頂点を含む.図の保存——前向き星

nt first[MAXN];      //first[x]    x             

int next[MAXM];    //next[i]   i          

int v[MAXM];        //v[i]   i     

int w[MAXM];       //w[i]   i     

int  cnt;         //            



   ：memset(first,0,sizeof(first));

             memset(next,0,sizeof(next));

       q     x->y : 

cnt++;

next[cnt]=first[x];     first[x]=cnt;  v[cnt]=y;  w[cnt]=q;

  ：for (int i=first[x];i;i=next[i])   {……}    

            //v[i]  x    ,w[i]       

前方星は隣接表に似ていて、余計なことは言わない.