非連結グラフのプログラムで表現する

非連結グラフをプログラムで表現します。

基本は、連結グラフの時と変わりませんが、 グラフが分かれていることを
示すために変数を持っています。

図は以下の非連結グラフを使っています。
1から4が一つのグラフとなっており
5から8が一つのグラフとなっています。

cでのプログラムになります。

#include 
using namespace std;

#define MAX 8
bool visited[MAX];

void visit(int i);

int GRAPH[MAX][MAX] = {
    {0,1,0,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,0,0},
    {0,1,0,0,0,0,0,0},
    {0,0,0,0,0,1,0,0},
    {0,0,0,0,1,0,1,1},
    {0,0,0,0,0,1,0,1},
    {0,0,0,0,0,1,1,0}
};

int main() {
    // 非連結用
    int count = 1;  
    
    for(int i = 0;i < MAX;++i){
        if(!visited[i]){
            printf("graph%d:",count++);
            visit(i);
        }
    }
    return 0;
}

void visit(int i){
    visited[i] = true;
    for(int j = 0;j < MAX;++j){
        if(GRAPH[i][j] == 1 && !visited[j]){
            printf("%d->%d ",i + 1,j + 1);
            visit(j);
        }
    }
}

実行結果

graph1:1->2 2->3 2->4 graph2:5->6 6->7 7->8

非連結グラフ(disconnected graph)とは

非連結グラフ(disconnected graph)はグラフが分かれているもののことをいいます。

図にすると、こんな感じです。

グラフの説明で載せたグラフの図を分解しました。
数字1,2,3,4は一つのグラフですが、5,6,7,8は別のグラフになっています。
こういう概念です。

グラフの深さ優先探索をc言語で学ぶ

グラフを探索する方法の一つに深さ優先探索(DFS:Depth-First-Search)があります。

探索方法をグラフの解説で使用したグラフを例に解説すると、

 

まず、ノード1に隣接するノードを走査します。

ノード1にノード2が隣接するのでノード2を走査しに行きますが、
この時にノード1に隣接する他のノードの探索を行う前に、
ノード2に隣接するすべてのノードの探索を行います。

ノード2でもノード1と同様に探索を行いノード3を見つけます。

ノード3を見つけたら、ノード4は探索せずに、ノード3の探索を行います。

これを続けていき、隣接ノードが見つからない場合前のノードに戻り、
これを繰り返し、すべての探索が終わったら探索を終了します。

この時にループ処理に陥らないように、一度訪れたノードに対してフラグをもたせます。

では、cで書かれた深さ優先探索を行うコードを見て見ます。
このコードは、上記のグラフを例にしています。

#include 
using namespace std;

#define MAX 8
bool visited[MAX];

void visit(int i);

int GRAPH[MAX][MAX] = {
    {0,1,0,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,1,0},
    {0,1,0,0,0,0,0,0},
    {0,0,0,1,0,1,0,0},
    {0,0,0,0,1,0,1,1},
    {0,0,1,0,0,1,0,1},
    {0,0,0,0,0,1,1,0}
};

int main() {
    visit(0);
    return 0;
}

void visit(int i){
    visited[i] = true;
    for(int j = 0;j < MAX;++j){
        if(GRAPH[i][j] == 1 && !visited[j]){
            printf("%d->%d ",i + 1,j + 1);
            visit(j);
        }
    }
}

実行結果

1->2 2->3 3->7 7->6 6->5 5->4 6->8

ポイントは、一度訪れたノードに対してフラグを持つことです。

グラフとは有効グラフ無効グラフとは

グラフ(graph)は節点(node)を辺(edge)で結んだものです。

グラフの図を例に挙げます。

このグラフでは、節点を辺で結んでいますが、
辺で結ばれた間は行き来する道があることを示しています。

隣接行列

先のようなグラフをデータとして表現するたの手法として、
隣接行列(adjacency matrix)があります。

先のグラフを隣接行列で表してみます。

	1	2	3	4	5	6	7	8
1	0	1	1	0	0	0	0	0
2	1	0	0	1	0	0	0	0
3	0	1	0	0	0	0	1	0
4	0	1	0	0	1	0	0	0
5	0	0	0	1	0	1	0	0
6	0	0	0	0	1	0	1	1
7	0	0	1	0	0	1	0	1
8	0	0	0	0	0	1	1	0

節点から節点へ辺がある場合には1でない場合は0で
表現しています。

無効グラフ

辺に向きのないものを無効グラフと言います。
先で示したグラフは無効グラフになります。

有効グラフ

辺に向きをもたせたものを有効グラフと言います。
有効グラフの辺には矢印をもたせます。

有向グラフでは、矢印が向いている方向に対してのみ道があります。

例をあげると、
先のグラフ図で、1 → 2と向いている場合
隣接行列で表現すると、

1 → 2は1になるが
2 → 1は0になります。

木構造の解説

枝分かれしながら、データが増えていくデータ構造を木構造といいます。

木構造を図で示すと以下のようになります。

木は節点(node)とそれらを結んでいる枝(branch)によって構成されます。
節点はデータを表し、枝はその節点との関係にあたります。

分岐元の節点を親といい、枝をたどった先の節点を子といいます。

また、一番先頭の接点を根(root)と呼び、子を持たない接点のことを葉(reef)といいます。

深さと高さ

根からある節点に至るまでに通る枝の数をその頂点の深さ(depth)といい、
根から最も深い節点までの深さを木の高さ(height)>といいます。

図でいうと、木の高さは2になります。

2分木と2分探索木

木のうちで、各々の節点から出る枝の数が2本以下であるものを2分木といいます。

また、各々の節点のデータが比較可能で、
親と子の関係に規則がある(親と子に大小の関係あるなど)木のことを2分探索木(binary search tree)といいます。

この規則を元にし、アルゴリズムでは木が利用されます。

全二分木(Full Binary Tree)とは

全二分木は、すべてのノードが2つか子を持たない二分木をいいます。

親が一つしか子を持たないので、全二分木ではない。

     10
   1
3    5

全てのノードが2つ子を持っている・または子をもっていないので、
全二分木である。

     10
   1      20
3    5

complete binary treeとは

complete binary treeとは、一番深いノード以外すべてのノードが満たされている2分木のこと。

また、一番深いノードは、
左から右の順に埋まっているという条件も満たしている必要があります。
図解すると、、、

一番下のノードが右しかないので、complete binary treeではない。
           10
    5           20
3     6              40

           10
    5           20
3     6    16

一番下のノードが左から始まっているので、complete binary treeである。

スタック内の最小値を返すスタッククラスを作成する

問題：スタック内の最小値を返すスタッククラスを作成する

カスタムしたクラス内に最小値を保存スタックを持つことで、
簡潔にコードを書くことができます。

pushするときにカスタムスタッククラス内のスタックメンバーの最小値を
チェックし、最小ならばpushする。

popも同様の処理を行うことで、最小値を保持するスタックが完成します。

kotlinでのサンプルを載せます。

import java.util.Stack

class StackWithMin : Stack(){
    var stack : Stack = Stack()

    override fun push(value : Int): Int? {
        if(value < getMin()){
            stack.push(value)
        }
        return super.push(value)
    }

    fun getMin() : Int {
        if(stack.isEmpty()){
            return Integer.MAX_VALUE
        }
        else{
            return stack.peek()
        }
    }

    override fun pop() : Int{
        val value = super.pop()
        if(value == getMin()){
            stack.pop()
        }
        return value
    }
}

続いてmain関数での実行例です。

fun main(args : Array){
    var stack : StackWithMin = StackWithMin()
    stack.push(100)
    stack.push(50)
    stack.push(1)
    // 1
    println(stack.getMin())
    stack.pop()
    // 50
    println(stack.getMin())
    stack.pop()
    // 100
    println(stack.getMin())

}