2 차 세계 대전 일기 - 9 일 째 - 데이터 구조: 그림 (2)

class Graph(private val vertices: ArrayList> = ArrayList(),
               private val adjacencyList: ArrayList> = ArrayList()) {
    fun createVertex(value: T): Vertex {
        val matchingVertices = vertices.filter { it.data == value }

        if (matchingVertices.isNotEmpty()) {
            return matchingVertices.last()
        }

        val vertex = Vertex(value, adjacencyList.size)
        vertices.add(vertex)
        adjacencyList.add(EdgeList(vertex))
        return vertex
    }

    fun addDirectedEdge(fromVertex: Vertex, toVertex: Vertex, weightValue: Double) {
        val edge = Edge(from = fromVertex,
                to = toVertex,
                weight = weightValue)

        fromVertex.addEdge(edge)
        val fromIndex = vertices.indexOf(fromVertex)
        adjacencyList[fromIndex].edges.add(edge)
    }

    fun addUnDirectedEdge(fromVertex: Vertex, toVertex: Vertex, weightValue: Double = 0.0) {
        addDirectedEdge(fromVertex, toVertex, weightValue)
        addDirectedEdge(toVertex, fromVertex, weightValue)

    }
    
    fun printAdjacencyList() {
        (0 until vertices.size)
                .filterNot { adjacencyList[it].edges.isEmpty() }
                .forEach { println("""${vertices[it].data} ->[${adjacencyList[it].edges.joinToString()}] """) }
    }
}

int visit[maxSize];
void DFS(AGraph *G, int v) {
    ArcNode *p;
    visit[v] = 1;
    cout << v << endl;
    p = G->adjlist[v].firstarc;  //  p    v     
    while (p != nullptr) {
        if (visit[p->adjvex] == 0) {
            DFS(G, p->adjvex);
            p = p->nextarc;
        }
    }
}

void BFS(AGraph *G, int v) {
    ArcNode *p;
    int que[maxSize], front = 0, rear = 0;  //       
    int j;
    cout << v << endl;
    visit[v] = 1;
    rear = (rear+1)%maxSize;  //   
    que[rear] = v;
    while (front != rear) {
        front = (front+1)%maxSize;  //     
        j = que[front];
        p = G->adjlist[j].firstarc;  // p      j     
        while (p != nullptr) {  //  p             
            if (visit[p->adjvex] == 0) {
                cout << p->adjvex << endl;
                rear = (rear+1)%maxSize;
                que[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
}