Bài thực hành 1

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

• Khai báo cấu trúc đồ thị (chủ yếu ma trận đỉnh cung)

• Các hàm cơ bản đồ thị như nhập cung

• Tính bậc của 1 đỉnh trong đồ thị

• Danh sách đỉnh kề của 1 đỉnh

⚠️ 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 !!!

Cấu trúc đồ thị

Danh sách đỉnh cung

typedef struct{
    int A[MAX][MAX];
    int n; //số đỉnh
    int m; //số cung
}Graph;

Danh sách cung

typedef struct {
    int u, v;
    int w;
} Edge;
typedef struct {
    int n, m;
    Edge edges[MAX];
} Graph;

Các hàm thao tác đồ thị

Hàm nhập cơ bản

void makeNullGraph(Graph *G){ //khởi tạo đồ thị rỗng
    G->m = 0;
    G->n = 0;
}

void initGraph(Graph *G, int n){ //khởi tạo đồ thị với n đỉnh
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            G->A[i][j] = 0;
}

void addEdge(Graph *G, int x, int y){ //thêm 1 cung vào đồ thị
    if(G->A[x][y] > 0 && G->A[x][y] > 0) //trường hợp đa cung
        G->A[x][y] = G->A[y][x] += 1;
    else
        G->A[x][y] = G->A[y][x] = 1;
}

// thêm 1 cung cho đồ thị có hướng
void addEdgeDirection(Graph *G, int x,int y){ 
    if(G->A[x][y] > 0){ //trường hợp đa cung
        G->A[x][y] += 1;
    }
    G->A[x][y] = 1;
}

void printGraph(Graph G){ // in ma trận đồ thị 
    for (int i = 1; i <= G.n; i++){
        for (int j = 1; j <= G.n; j++){
            printf("%d ",G.A[i][j]);
        }
        printf("\n");
    }
}

⚠️ LƯU Ý

Hàm thêm cung tuỳ thuộc vào hoàn cảnh bài toán mà bạn sửa lại cho đúng.

Hàm thao tác cơ bản

int inDegree(Graph G, int x){ //tính bậc trong của đồ thị
    int count = 0;
    for (int i = 1; i <= G.n; i++){
        if(G.A[x][i] == 1)
            count++;
    }
    return count;
}
int outDegree(Graph G, int x){ //tính bậc ngoài của đồ thị
    int count = 0;
    for(int i = 1; i <= G.n; i++){
        if(G.A[i][x] == 1)
            count++;
    }
    return count;
}
int maxDegree(Graph G){
    int max = inDegree(G,1); //sử dụng bậc trong hay ngoài đều được
    for(int i = 2; i <= G.n; i++){
        int x = inDegree(G,i);
        if(max < x)
            max = x;
    }
    return max;
}
bool multiEdge(Graph G){ //kiểm tra có chứa đa cung không
    for (int i = 1; i <= G.n; i++){
        for (int j = 0; j <= G.n; j++)
            if(G.A[i][j] > 1) // hoặc == 2 đều được
                return true;
    }
    return false;
}
List neighbors(Graph G, int x){ //trả về danh sách các đỉnh kề
    List L; makeNullList(&L);
    for (int i = 1; i <= G.n; i++){
        if(G.A[x][i] == 1)
            insertList(i,&L);
    }
    return L;
}
List arrayGraph(Graph G){ // trả về danh sách các đỉnh trong đồ thị
    List L; makeNullList(&L);
    for (int i = 1; i <= G.n; i++)
        insertList(i,&L);
    return L;
}