Bài thực hành 2

Trong bài này bạn cần nắm bắt các mục như sau :

• Duyệt đồ thị theo chiều sâu và rộng

• Kiểm tra tính liên thông và liên thông mạnh của đồ thị

• Kiểm tra đồ thị có chu trình không

⚠️ LƯU Ý

Tất cả các đỉnh trong đồ thị bắt đầu từ 1 thay vì 0, nên hãy để ý rõ không thì sai !!!

Duyệt đồ thị theo chiều sâu

Phương pháp ngăn xếp

Trả về danh sách duyệt đồ thị theo chiều sâu dùng ngăn xếp

void subDFS(Graph G, Stack stack, List *L){
    while (!emptyStack(stack)){
        int u = pullStack(&stack);
        if(memberList(u, *L)) continue;
        insertList(u, L);
        List temp = neighbors(G,u);
        for (int i = 0; i < temp.Size; i++){
            int v = temp.Data[i];
            if(!memberList(v, *L)){
                pushStack(&stack, v);
            }
        }
    }
}
List DFS(Graph G, int x){
    List L;
    makeNullList(&L);
    List array = arrayGraph(G);

    while (L.Size != G.n){
        Stack stack;
        makeNullStack(&stack);
        pushStack(&stack,x);

        subDFS(G,stack,&L);
        x = 0;
        for (int i = 0; i < array.Size; i++){
            if(!memberList(array.Data[i],L)){
                x = array.Data[i];
                break;
            }
        }
    }
    return L;
}

⚠️ CHÚ Ý

Hàm trả về đầy đủ các đỉnh kể cả khi đồ thị không liên thông, nên nếu bạn có nhu cầu khác hãy sử từ dòng 27 tới 32

Sử dụng đệ quy

void DFS_Re(Graph G, int v, bool visited[]){
    visited[v] = true;

    List temp = neighbors(G, v);
    for (int i = 0; i < temp.Size; i++){
        int u = temp.Data[i];
        if(!visited[u]){
            DFS_Re(G, u, visited);
        }
    }
}

⚠️ LƯU Ý

Sửa hàm này theo nhu cầu của bạn

Duyệt đồ thị theo chiều rộng

Sử dụng danh sách (tương đương hàng đợi)

void subBFS(Graph G, List queue, List *L){
    while (!emptyList(queue)){
        int u = elementAt(&queue);
        if(memberList(u, *L)) continue;
        insertList(u, L);
        List temp = neighbors(G,u);
        for(int i = 0; i < temp.Size; i++){
            int v = temp.Data[i];
            if(!memberList(v, *L) && !memberList(v, queue)){
                insertList(v, &queue);
            }
        }
    }
}
List BFS(Graph G, int x){    
    List L;
    makeNullList(&L);
    List array = arrayGraph(G);
    while (L.Size != G.n){
        List queue;
        makeNullList(&queue);
        insertList(x,&queue);

        subBFS(G,queue,&L);
        x = 0;
        for(int i = 0; i < array.Size; i++){
            if(!memberList(array.Data[i], L)){
                x = array.Data[i];
                break;
            }
        }
    }
    return L;
}

⚠️ CHÚ Ý

Hàm trả về đầy đủ các đỉnh kể cả khi đồ thị không liên thông, nên nếu bạn có nhu cầu khác hãy sử từ dòng 26 tới 31

Tính Liên thông của đồ thị

Là đồ thị khi một đỉnh bất kỳ có thể đi tới tất cả các đỉnh còn lại trong đồ thị

//kiểm tra đồ thị liên thông
int connectedGraph(Graph G){
    bool visited[G.n + 1]; // bắt đầu từ đỉnh 1 thay vì 0
    for (int i = 1; i <= G.n; i++){ // khởi tạo ban đầu là false
        visited[i] = false;
    }
    DFS_Re(G,x,visited);
    for(int i = 1; i <= G.n; i++){
        if(!visited[i])
            return false;
    }
    return true;
}

//kiểm tra đồ thị liên thông mạnh
bool connectedStrongGraph(Graph G){
    for (int i = 1; i <= G.n; i++){
        if(!connectedGraph(G,i))
            return false;
    }
    return true;
}

//đếm số đồ thị liên thông mạnh
int countSubConnectedGraph(Graph G){
    if(connectedStrongGraph(G)) 
        return 1;
    
    int count = 0;
    for(int i = 1; i <= G.n; i++){
        if (!connectedGraph(G,i))
            count++;
    }
    return count;
}