シュワン008 DSとA -グラフ

グラフ

グラフ理論は一般的に物事の間の関係を研究するための代数のクラスは、コンピュータサイエンスで最も一般的な使用はネットワークです.

グラフの表現

最初の表現はadjacency matrix これまでの例としてポイントと別のリンクa それは自己との関係はないa 関係を持つb and a との直接関係はありませんcエー
b
c
ディー
エー
0
1
0
1
b
1
0
1
0
c
0
1
0
1
ディー
1
0
1
0
もう一つの人気表現はlinked list
すべてのノードは、接続するノードへのポインタを持っています.
密なグラフは、ITノード間の接続がたくさんあるグラフです.
濃いならばE=O(v^2) どこE はエッジ数とv 頂点の数は、グラフが自己を接続していることを意味します.言い換えれば、行列はほぼすべて1です.
私たちがどんな社会的プラットホームのためにも類似したネットワークを必要とすると言いましょう.
リンクリストの順序はO(V+2E) は<O(v^2)

BFSとDFS

私が訪問するか、それを印刷する訪問平均.
私は彼女が作ったすべての接続を探索することを意味する.
訪問
探検する
意味
0
0
訪問されず、調査されない
1
0
訪問されるが、調査されない
1
1
訪問と調査
チェックしたノードの配列を使用することができますQueue or Stack , 使用するものQueue 呼ばれるBFS (Breadth First Search) そして、使用するものstack 呼ばれるDFS (Depth First Search) BFS このように木を横断します
DFS このように木を横断します

BFSアルゴリズム

// the graph G and array visited[] are global
// visited[] is initialized to 0
BFS(v)
{
    u = v;
    visited[u] = 1;
    repeat
    {
        for all vertices w adj to u do
        {
            if(visited == 0)
            {
                add w to q;
                visited[w] = 1;
            }
        }

        if q is empty then return;
        delete the next element u from q;
    }
}

グラフG visited を初期化する01
2
3
4
5
6
7
8
0
0
0
0
0
0
0
0
キューq最初の反復u=1 頂点w ADJからu are w={2,3} , それで、訪問されて、待ち行列はそうです
1
2
3
4
5
6
7
8
1
0
0
0
0
0
0
0
2
キューに追加した後2 としてマークされますvisited を初期化する01
2
3
4
5
6
7
8
1
1
0
0
0
0
0
0
今、我々は2 我々は行く必要がある3 なぜなら私たちはfor ここに隣接するすべてに行くループ1 どちらが{2,3}
1
2
3
4
5
6
7
8
1
1
1
0
0
0
0
0
2
3
今、我々はfor ループq が空でないので、次の要素を削除しますq は2 , 現在我々u なる2 と隣人2 are w={1,4,5} 以来1 私たちは再び訪問するつもりはありません、そして、我々が空に達するまで、我々は前と同じ論理をしますq これはすべてを訪問し、探索を意味します.

LinkedlistのBFS解析

キューの実装は、O(v)linkedlistはO(v+E)

隣接行列実装に関するBFS解析

我々があるならば8 頂点は、私たちには8x8 サイズ、配列、キューの実装は、それぞれのスペースの複雑さを持ちますO(v) ここでvは頂点数であり、時間の複雑さはT(v^2)

BFSを用いた幅優先第一軌条

グラフが接続されているかどうかを知るために、すべてのノードが同じグラフにあることを意味します

それらを2グラフに分けることができますU and G そこから交差点を持っていない少なくとも1つのノードU with Vこれらの2つのサブグラフを横断するには

BFT(G,n)
{
    // this loop to fill the array with not visited yet
    for i=1 to n do
        visited[i] = 0
    // this will visit every node that is not visited yet
    for i=1 to n do
        if(visited[i]==0) then BFS(i) //BFS not BFT !!!!!
}

各ケースをノード

第一4 ボックスはU グラフ付き4 ノード、彼は1から始まる1->4 訪問として、彼は壊れます.
この後、V そして同じことをする.
時間の複雑さO(E+V) と空間の複雑さO(V)

DFSアルゴリズム

DFS(v)
{
    visited[v] = 1;
    for each vertex w adj to v do
    {
        if(visited[w] == 0) then
            DFS(w);
    }
}

インDFS 私たちはポイントから始めて、それを探検します、その中の次のノードが調査されないならば、我々は前のノードを去って、新しいノードを調査します.
訪問された配列を初期化することは関数と呼ばれるプログラムで行われます、そして、我々が時間複雑さを計算するとき、我々はそれを数えます.

v = 1
v = 2
v = 4
v = 8
v = 5
v = 6
v = 3
v = 7
w = { 2 , 3 }
w＝｛1,4,5｝｝
w = { 2 , 8 }
w =｛4 , 5 , 6 , 7｝
w = { 2 , 8 }
w = { 3 , 8 }
w = { 1 , 7 }
w = { 3 , 8 }
2訪問しない
4訪問しない
8訪問しない
5活気がない
すべてのWは我々が戻ってV = 8
8活気のない
すべてのWを訪問v = 8、7
すべてのWは訪問しました、そして、すべてのVは訪問されます
私たちが毎回見ているように、私たちは訪問していないノードを持っています.すべての隣人が訪問されるならば、我々は古い隣人に戻ります.

DFSとDFTの解析

空間複雑度DFS is O(V) , すべてのノードが同時にスタック上にあるので、グラフがチェーンの場合は最悪の場合.したがって、空間の複雑さDFS and BFS is O(v) , 時間の複雑さO(E)+O(V) リンクリスト表示の場所O(V) 訪問した配列を初期化し、O(V^2) 行列表現の場合、BFS .DFT はBFT 代わりにBFS コールDFS .