Javascriptを使用してグラフのデータ構造にアプローチする

隣接リストと隣接行列は、コンピューターサイエンスでグラフを表現する 2 つの一般的な方法です。

隣接リスト:

1. 隣接リストは、リンクされたリストの配列としてグラフを表します。
2. 配列のインデックスは頂点を表し、そのリンクされたリスト内の各要素は、頂点とともにエッジを形成する他の頂点を表します。

長所:

1. まばらなグラフ (エッジの少ないグラフ) を表現するのにスペース効率が良い。
2. 頂点の追加は簡単です。

短所:

1. 2 つの頂点間にエッジが存在するかどうかを確認するなど、一部の種類のクエリでは効率が低下します。 より複雑なデータ構造。

隣接行列:

1. 隣接行列はグラフを 2 次元配列として表します。ここで、i 行目、j 列目のセルは頂点 i と j の間のエッジを示します。

長所:

1. 理解と実装が簡単です。
2. 密なグラフ (より多くのエッジを持つグラフ) に効率的です。
3. 2 つの頂点間にエッジが存在するかどうかを簡単に確認できます。

短所:

1. より多くのスペースが必要です (O(V^2)、V は頂点の数です)。 頂点の追加には O(V^2) がかかり、隣接リストよりも遅くなる可能性があります。

重要なお知らせ

1. 面接官にどのアプローチを取るかを事前に伝え、長所と短所を伝えてください。

グラフトラバーサル

1. DFS (深さ優先検索) (スタック)
2. BFS (ブレスファーストサーチ) (キュー)

最短パス BFS を見つける方が良いでしょう

*有向グラフと無向グラフ: *

1. 有向グラフは有向グラフとも呼ばれ、各エッジが方向を持つグラフです。エッジは、ある頂点から別の頂点を指します。

2. 無向グラフは、エッジに方向性がないグラフです。エッジ (x, y) はエッジ (y, x) と同一です。

加重グラフと加重なしグラフ:

1. 重み付きグラフ は、各エッジに重みまたはコストが割り当てられたグラフです。これは、特定のエッジの重要性や長さが異なる問題に役立ちます。

2. 重み付けされていないグラフは、すべてのエッジの重みまたはコストが等しいグラフです。

セルフループ:

1. 自己ループは、頂点をそれ自体に接続するエッジです。

疎グラフと密グラフ:

1. 疎グラフは、エッジの数が最小エッジ数に近いグラフです。言い換えれば、頂点間にはエッジがほとんどありません。

2. 密グラフ は、エッジの数が可能な最大エッジ数に近いグラフです。言い換えれば、頂点間には多くのエッジが存在します。

循環グラフと非循環グラフ:

1. 循環グラフは、少なくとも 1 つのサイクル (頂点がそれ自体から到達可能なエッジと頂点のパス) を含むグラフです。

2. 非巡回グラフは、周期のないグラフです。ツリーと呼ばれる特別なタイプの非循環グラフは、循環のない接続された無向グラフです。
   

// Weighted graph adjacency list would look like

{
1: [ {node: 2, weight: 50}, {node: 3, weight: 60}]
...
6: [{node: 1, weight: 40}, {node:5, weight:30 }, {node:4, weight: 90}]
}

class Graph {
    constructor() {
        this.adjList = {};
    }

    addNode(value) {
        this.adjList[value] = []
    }

    addEdge(node1, node2) {
        this.adjList[node1].push(node2);
        this.adjList[node2].push(node1);
    }

    removeEdge(node1, node2) {
        this.removeElement(node1, node2);
        this.removeElement(node2, node1);
    }

    removeElement(node, value) {
        const index = this.adjList[node].indexOf(value);
        this.adjList[node] = [...this.adjList[node].slice(0, index), ...this.adjList[node].slice(index+1)];
    }

    removeNode(node) {
        const connectedNodes = this.adjList[node];

        for (let connectedNode of connectedNodes) {
            this.removeElement(connectedNode, node);
        }

        delete this.adjList[node];
    }
depthFirstTraversal(startNode) {
        const stack = [];
        const visited = {};

        stack.push(startNode);
        visited[startNode] = true;

        while(stack.length > 0) {
            const currentNode = stack.pop();
            const connectedNodes = this.adjList[currentNode];
            console.log(currentNode);
            connectedNodes.forEach(connectedNode => {
                if (!visited[connectedNode]) {
                    visited[connectedNode] = true;
                    stack.push(connectedNode);
                }
            })
        }
    }

    breathFirstTraversal(startNode) {
        const queue = [];
        const visited = {}

        queue.push(startNode);
        visited[startNode] = true;

        while(queue.length > 0) {
            const currentElement = queue.shift();
            const connectedNodes = this.adjList[currentElement];
            console.log(currentElement);
            connectedNodes.forEach(connectedNode => {
                if (!visited[connectedNode]) {
                    visited[connectedNode]=true;
                    queue.push(connectedNode);
                }
            });
        }
    }
}

const test = new Graph();

test.addNode(1);
test.addNode(2);
test.addNode(3);
test.addNode(4);
test.addNode(5);
test.addNode(6);
test.addEdge(1,2)
test.addEdge(1,3)
test.addEdge(1,6)
test.addEdge(2, 3);
test.addEdge(2, 5);
test.addEdge(2, 4);
test.addEdge(3, 4);
test.addEdge(3, 5);
test.addEdge(4, 5);
test.addEdge(4, 6);
test.addEdge(5, 6);
console.log('After adding all node and Edge --> ', test.adjList)

test.removeNode(4);

console.log('After Removing node 4 --> ', test.adjList)
console.log('----------Depth First Traversal -------------')
test.depthFirstTraversal(1);
console.log('----------Breath First Traversal -------------')
test.breathFirstTraversal(1);

/*
After adding all node and Edge -->  {
  '1': [ 2, 3, 6 ],
  '2': [ 1, 3, 5, 4 ],
  '3': [ 1, 2, 4, 5 ],
  '4': [ 2, 3, 5, 6 ],
  '5': [ 2, 3, 4, 6 ],
  '6': [ 1, 4, 5 ]
}
After Removing node 4 -->  {
  '1': [ 2, 3, 6 ],
  '2': [ 1, 3, 5 ],
  '3': [ 1, 2, 5 ],
  '5': [ 2, 3, 6 ],
  '6': [ 1, 5 ]
}
----------Depth First Traversal -------------
1
6
5
3
2
----------Breath First Traversal -------------
1
2
3
6
5
*/

以上がJavascriptを使用してグラフのデータ構造にアプローチするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。