を選択します。

これまで見られたツリー構造の特性は,ルートがあり,サブノードがあり,親ノードとサブノードを接続するedgeが存在し,親ノードから子ノードに方向が流れる.また、入口は1つであり、出口は2つ(または複数)の構造である.
グラフィック(Graph)は上記の構造ではなく、方向がなく、入口の個数もなく、サブノードもなく、他にも様々な構造があります.ツリーはグラフの形式と見なすことができます.(複数条件のある方向図)
グラフィック構造はG=(V,E)で表すことができる.
G : Graph
V:Vertex set(ツリーではNodeと呼ぶ)
E : Edge set

上記構成がある場合
V = { 1, 2, 3, 4, 5, 6 }
E = { (1,2) , (2,3) , (1,5) , (3,4), (6,4), (2,1) ... }
|V|=n(Vセットの大きさ)
|E|=m(Eセットのサイズ)
使えます.

グラフィック構造は上から下への階層構造ではないため、グラフィック構造の度合いは隣接するエッジの数であり、グラフィックの度合いは最も大きい値である.(4度:3)

隣接はノード3とノード2の隣接である.

E(2,3)入射ノード2,3.

パス(path):1から3までのパス?

1 -> 2 -> 3

1 -> 5 -> 4 -> 3

をもう一度歩くノードはパスに含まれません.

循環構造:始点と終点が同じ場合

1 -> 2 -> 3 -> 1

ビットに示すように、先頭と末尾は同じであり、グラフィックに存在するか、存在しないかのいずれかである.

サイクルのグラフはありませんか?——>ツリー構造(子ノードから親ノードまで)

サイクルでは、あるノードからあるノードへのパスは少なくとも2つ以上あり、ループがなければ1つのパスしか存在しない.

図形の方向

Undirected graph

方向図なし(双方向図)

Directed graph

方向のグラフがあり、1から5に直接移動できません.

weight graph

図のエッジに重みのある

グラフィック表示

表示図形は隣接性を表す.

隣接行列(隣接行列、nxn行列、O(n^2)

欠点:情報の表現に比べて無駄なメモリ(0個)が多すぎて効率が悪い.

隣接表(隣接表,O(n+m)

ここでのリストはチェーンテーブルを表します.

順番を問わずlinklistで表現する方法.
隣接リストメソッドを使用する場合,ノードの個数はedge個数の2倍である.△無方向は双方向だから.

グラフループ

DFS ( Depth - First Search )

Binary treeツアーで使用されるin、pre、postOrderはDFSに属します.
サブノードにアクセスすると、そのノードのサブノードを最後に検索し、次のブランチの場所に移動できます.
出典:ウィキペディア

BFS ( Breadth - First Search )

レベル単位で巡回しているのはBFSです.

出典:ウィキペディア
DFS、BFS-Python実施

class Graph:
    def __init__(self):
        self.graph = {}

    def addInfo(self,start,edges):
        self.graph[start] = edges

    def addEdge(self,start,edge):
        self.graph[start].append(edge)

    def addVertex(self,Vertex):
        self.graph[Vertex] = []

    ## BFS는 Queue구조로 구현가능하다.
    def BFS(self,start):
        Q = [start]

        visited = [start]
        while Q:
            cur_V = Q.pop(0)

            for next in self.graph[cur_V]:

                if next not in visited:
                    Q.append(next)
                    visited.append(next)

        return visited

    ## DFS는 스택과 재귀로 구현가능하다.

    def DFS(self,start):

        S = [start]

        visited = []

        while S:
            cur_V = S.pop()

            if cur_V not in visited:
                visited.append(cur_V)
                S.extend(self.graph[cur_V][::-1])
                
        return visited

    def DFS_recursive(self,start,visited=[]):
        visited.append(start)

        for next in self.graph[start]:
            if next not in visited:
                self.DFS_recursive(next,visited)

        return visited

if __name__=="__main__":
    G = Graph()
    G.addInfo('A',['C','D','E'])
    G.addInfo('B',['F','C'])
    G.addInfo('C',['A','B'])
    G.addInfo('D',['A','F'])
    G.addInfo('E',['A'])
    G.addInfo('F',['D','B'])

    print(G.BFS('A'))
    print(G.DFS('A'))
    print(G.DFS_recursive('A'))