[2023-09-25] 자료구조 & 알고리즘 - 그래프

그래프

- 정점과 정점사이를 연결하는 간선으로 이루어진 비선형 자료구조

- 정점 집합과 간선 집합으로 표현할 수 있다.

- ex) 지하철 노선도, 페이지랭크 알고리즘

 

 

그래프의 특징

- 정점은 여러개의 간선을 가질 수 있다.

- 크게 방향그래프와 무방향 그래프로 나눌 수 있다.

- 간선은 가중치를 가질 수 있다.

- 사이클이 발생할 수 있다.

 

무방향 그래프

- 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.

- 표현하기에 (A,B)와 (B,A)는 같은 간선으로 취급된다.

 

 

방향 그래프

- 간선에 방향성이 존재하는 그래프

- 양방향으로 갈 수 있더라도 <A,B> 와 <B,A>는 다른 간선으로 취급된다.

 

 

연결 그래프

-모든 정점이 서로 이동이 가능한 상태 그래프

- 특정 정점에서 다른 특정 정점까지 모든 경우의 수가 이동가능해야한 연결그래프가 된다.

비연결 그래프

- 특정 정점쌍 사이에 간선이 존재하지 않는 그래프

완전 그래프

- 모든 정점끼리 연결된 상태인 그래프

- 한 정점의 간선수 = 모든 정점 수 -1

- 총 간선수 = (모든 정점수 - 1) * 정점수

 

 

사이클

- 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

 

 

그래프를 코드로 나타내는 방법

1. 인접 행렬

2. 인접 리스트

자바스크립트에서 사용하는 방법

1. 인접행렬

-위 그래프를 기준으로 코드를 작성했다.

const graph = Array.from(Array(5), () => Array(5).fill(false));

graph[0][1] = true;
graph[0][2] = true;
graph[1][4] = true;
graph[3][2] = true;
graph[3][4] = true;

2. 인접리스트

const graph = Array.from(Array(5), () => Array(5).fill(false));]

graph[0].push(2);
graph[0].push(3);
graph[1].push(4);
graph[3].push(2);
graph[3].push(4);

 

 

그래프 코딩테스트

https://school.programmers.co.kr/tryouts/101815/challenges

 

 

내 제출

function solution(n, edge) {
    var answer = 0;
    let graph=Array.from({length: n+1},()=>Array());
    let visited =Array(n+1).fill(0);
    let queue=[];
    for(var [a,b] of edge){
        graph[a].push(b);
        graph[b].push(a);
    }
    visited[1]=1;
    queue.push([1,0]);
    while(queue.length){
        let [go,L] = queue.shift();
        for(let v of graph[go]){
            if(visited[v]==0){
                visited[v]=L+1;
                queue.push([v,L+1]);
            }
        }
    }
    visited=visited.filter((x)=>x==Math.max(...visited))
    
    return visited.length;

}

 

다른 풀이

class Queue {
	constructor(){
    	this.queue = [];
        this.front = 0;
        this.rear = 0;
    }
    
	enqueue(value){
    	this.queue[this.rear++] = value;
    }
    
    dequeue(){
    	const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front += 1;
        return value
    }
    
    isEmpty(){
    	return this.rear === this.front
    }
}
    
function solution(n, edge) {
    let graph=Array.from({length: n+1},()=>Array());
    let visited =Array(n+1).fill(0);
    const queue= new Queue();
    
    for(var [a,b] of edge){
        graph[a].push(b);
        graph[b].push(a);
    }
    visited[1]=1;
    
    queue.enqueue(1);
    while(!queue.isEmpty()){
        const src = queue.dequeue();
        for(let v of graph[src]){
            if(visited[v]==0){
                visited[v]=visited[src]+1;
                queue.enqueue(v);
            }
        }
    }
    visited=visited.filter((x)=>x==Math.max(...visited))
    
    return visited.length;

}