Linear / Non-Linear

선형 자료구조(=Linear)
원소들을 하나씩 순차적으로 나열시킨 형태로 자료들간 앞,뒤 관계가 1:1인 자료구조이다.

비선형 자료구조(=Non-Linear)

하나의 자료뒤에 여러개의 자료가 존재할 수 있는 형태로 자료들간 앞,뒤 관계가 1:N 또는 N:N인 자료구조를 말한다.

---

Graph

정점(Vertex/Node)과 간선(Edge)로 이루어진 형태로 대표적인 비선형 자료구조이다.

• 방향
  • 무방향 그래프
  • 방향 그래프
• 가중치
  • 가중치 그래프
• Degree
  간선으로 연결된 이웃한 정점의 개수
  • InDegree
  • OutDegree
• 순환(Cycle)
  임의의 한점에서 출발해 자기 자신으로 돌아올 수 있는 경로
  
• 연결(Connected)
  임의의 두 정점 사이에 경로가 항상 존재하는 성질

인접행렬

// 방향, 가중치 없는 경우
func graphAdjMat(_ node: Int, _ edges: [[Int]]) {
    var adjMat: [[Int]] = .init(repeating: .init(repeating: 0, count: node + 1), count: node + 1)
    
    for edge in edges {
        
        adjMat[edge[0]][edge[1]] = 1
        adjMat[edge[1]][edge[0]] = 1
    }
    
    for y in 1...node {
        for x in 1...node {
            print(adjMat[y][x], terminator: " ")
        }
        print("")
    }
}

// 방향이 있는 경우
func graphAdjMat(_ node: Int, _ edges: [[Int]]) {
    var adjMat: [[Int]] = .init(repeating: .init(repeating: 0, count: node + 1), count: node + 1)
    
    for edge in edges {
        
        adjMat[edge[0]][edge[1]] = 1
    }
    
    for y in 1...node {
        for x in 1...node {
            print(adjMat[y][x], terminator: " ")
        }
        print("")
    }
}

// 가중치가 있는 경우
func weightedGraphAdjMat(_ node: Int, _ cost: [[Int]]) {
    var adjMat: [[Int]] = .init(repeating: .init(repeating: 0, count: node + 1), count: node + 1)
    
    for edge in cost {
        adjMat[edge[0]][edge[1]] = edge[2]
        adjMat[edge[1]][edge[0]] = edge[2]
    }
    
    for y in 1...node {
        for x in 1...node {
            print(adjMat[y][x], terminator: " ")
        }
        print("")
    }
}

인접리스트

func graphAdjList(_ node: Int, _ edges: [[Int]]) {
    var adjList: [[Int]] = .init(repeating: [], count: node + 1)
    
    for edge in edges {
        adjList[edge[0]].append(edge[1])
        adjList[edge[1]].append(edge[0])
    }
    
    for i in 1...node {
        print(adjList[i])
    }
}