Javascript를 사용하여 그래프 데이터 구조에 접근

인접 목록과 인접 행렬은 컴퓨터 과학에서 그래프를 표현하는 두 가지 일반적인 방법입니다.

인접 목록:

1. 인접 목록은 연결된 목록의 배열로 그래프를 나타냅니다.
2. 배열의 인덱스는 꼭짓점을 나타내고, 연결된 목록의 각 요소는 꼭짓점과 가장자리를 형성하는 다른 꼭짓점을 나타냅니다.

장점:

1. 희소 그래프(가장자리 수가 적은 그래프)를 표현하는 데 공간 효율적입니다.
2. 정점을 추가하는 것이 더 쉽습니다.

단점:

1. 두 정점 사이에 가장자리가 존재하는지 확인하는 등 일부 유형의 쿼리에는 효율성이 떨어집니다. 더욱 복잡한 데이터 구조.

인접 매트릭스:

1. 인접 행렬은 그래프를 2차원 배열로 표현하며, 여기서 i번째 행과 j번째 열의 셀은 정점 i와 j 사이의 가장자리를 나타냅니다.

장점:

1. 이해와 구현이 간단합니다.
2. 밀집된 그래프(가장자리가 더 많은 그래프)에 효율적입니다.
3. 두 정점 사이에 에지가 존재하는지 빠르게 확인하세요.

단점:

1. 더 많은 공간이 필요합니다(O(V^2), 여기서 V는 정점 수). 정점 추가는 O(V^2)이므로 인접 목록보다 느릴 수 있습니다.

중요사항

1. 면접관에게 어떤 접근 방식을 따를 것인지 미리 알리고 장단점을 말해주세요.

그래프 순회

1. DFS(깊이 우선 검색)(스택)
2. BFS(Breath First Search)(큐)

최단 경로 BFS를 찾는 것이 좋습니다

*유향 그래프와 무향 그래프: *

1. 유향 그래프는 유향 그래프라고도 하며 각 모서리에 방향이 있는 그래프입니다. 가장자리는 한 꼭지점에서 다른 꼭지점을 가리킵니다.

2. 무방향 그래프는 모서리에 방향이 없는 그래프입니다. 모서리(x, y)는 모서리(y, x)와 동일합니다.

가중치 그래프와 비가중치 그래프:

1. 가중치 그래프는 각 모서리에 가중치 또는 비용이 할당된 그래프입니다. 이는 특정 가장자리의 중요성이나 길이가 다른 문제에 유용합니다.

2. 무가중 그래프는 모든 간선의 가중치나 비용이 동일한 그래프입니다.

자체 루프:

1. 자체 루프는 정점을 자신에게 연결하는 모서리입니다.

희소 그래프와 밀집 그래프:

1. 희소 그래프는 간선의 개수가 최소 변의 개수에 가까운 그래프입니다. 즉, 정점 사이의 가장자리가 거의 없습니다.

2. 밀집 그래프는 간선 수가 최대 간선 수에 가까운 그래프입니다. 즉, 꼭지점 사이에 변이 많다는 뜻입니다.

순환 그래프와 비순환 그래프:

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!