العمليات الأساسية على الرسوم البيانية

TypeScript

/* فئة الرسم البياني غير الموجّه القائمة على مصفوفة التجاور */
class GraphAdjMat {
    vertices: number[]; // قائمة الرؤوس، حيث يمثل العنصر "قيمة الرأس" ويمثل الفهرس "فهرس الرأس"
    adjMat: number[][]; // مصفوفة التجاور، حيث يقابل فهرسا الصف والعمود "فهرس الرأس"

    /* المُنشئ */
    constructor(vertices: number[], edges: number[][]) {
        this.vertices = [];
        this.adjMat = [];
        // إضافة الرؤوس
        for (const val of vertices) {
            this.addVertex(val);
        }
        // إضافة الأضلاع
        // لاحظ أن عناصر edges تمثل فهارس الرؤوس، أي أنها تقابل فهارس عناصر vertices
        for (const e of edges) {
            this.addEdge(e[0], e[1]);
        }
    }

    /* الحصول على عدد الرؤوس */
    size(): number {
        return this.vertices.length;
    }

    /* إضافة رأس */
    addVertex(val: number): void {
        const n: number = this.size();
        // إضافة قيمة الرأس الجديد إلى قائمة الرؤوس
        this.vertices.push(val);
        // إضافة صف إلى مصفوفة التجاور
        const newRow: number[] = [];
        for (let j: number = 0; j < n; j++) {
            newRow.push(0);
        }
        this.adjMat.push(newRow);
        // إضافة عمود إلى مصفوفة التجاور
        for (const row of this.adjMat) {
            row.push(0);
        }
    }

    /* حذف رأس */
    removeVertex(index: number): void {
        if (index >= this.size()) {
            throw new RangeError('Index Out Of Bounds Exception');
        }
        // حذف الرأس عند الفهرس index من قائمة الرؤوس
        this.vertices.splice(index, 1);

        // حذف الصف عند الفهرس index من مصفوفة التجاور
        this.adjMat.splice(index, 1);
        // حذف العمود عند الفهرس index من مصفوفة التجاور
        for (const row of this.adjMat) {
            row.splice(index, 1);
        }
    }

    /* إضافة ضلع */
    // المعاملان i وj يقابلان فهارس عناصر vertices
    addEdge(i: number, j: number): void {
        // معالجة تجاوز حدود الفهارس والتساوي
        if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
            throw new RangeError('Index Out Of Bounds Exception');
        }
        // في الرسم البياني غير الموجّه، مصفوفة التجاور متماثلة حول القطر الرئيسي، أي أنها تحقق (i, j) === (j, i)
        this.adjMat[i][j] = 1;
        this.adjMat[j][i] = 1;
    }

    /* حذف ضلع */
    // المعاملان i وj يقابلان فهارس عناصر vertices
    removeEdge(i: number, j: number): void {
        // معالجة تجاوز حدود الفهارس والتساوي
        if (i < 0 || j < 0 || i >= this.size() || j >= this.size() || i === j) {
            throw new RangeError('Index Out Of Bounds Exception');
        }
        this.adjMat[i][j] = 0;
        this.adjMat[j][i] = 0;
    }

    /* طباعة مصفوفة التجاور */
    print(): void {
        console.log('Vertex list = ', this.vertices);
        console.log('Adjacency matrix =', this.adjMat);
    }
}

TypeScript

/* فئة الرسم البياني غير الموجّه القائمة على قائمة التجاور */
class GraphAdjList {
    // قائمة التجاور، key: الرأس، value: جميع الرؤوس المجاورة لذلك الرأس
    adjList: Map<Vertex, Vertex[]>;

    /* المُنشئ */
    constructor(edges: Vertex[][]) {
        this.adjList = new Map();
        // إضافة جميع الرؤوس والأضلاع
        for (const edge of edges) {
            this.addVertex(edge[0]);
            this.addVertex(edge[1]);
            this.addEdge(edge[0], edge[1]);
        }
    }

    /* الحصول على عدد الرؤوس */
    size(): number {
        return this.adjList.size;
    }

    /* إضافة ضلع */
    addEdge(vet1: Vertex, vet2: Vertex): void {
        if (
            !this.adjList.has(vet1) ||
            !this.adjList.has(vet2) ||
            vet1 === vet2
        ) {
            throw new Error('Illegal Argument Exception');
        }
        // إضافة الضلع vet1 - vet2
        this.adjList.get(vet1).push(vet2);
        this.adjList.get(vet2).push(vet1);
    }

    /* حذف ضلع */
    removeEdge(vet1: Vertex, vet2: Vertex): void {
        if (
            !this.adjList.has(vet1) ||
            !this.adjList.has(vet2) ||
            vet1 === vet2 ||
            this.adjList.get(vet1).indexOf(vet2) === -1
        ) {
            throw new Error('Illegal Argument Exception');
        }
        // حذف الضلع vet1 - vet2
        this.adjList.get(vet1).splice(this.adjList.get(vet1).indexOf(vet2), 1);
        this.adjList.get(vet2).splice(this.adjList.get(vet2).indexOf(vet1), 1);
    }

    /* إضافة رأس */
    addVertex(vet: Vertex): void {
        if (this.adjList.has(vet)) return;
        // إضافة قائمة مترابطة جديدة في قائمة التجاور
        this.adjList.set(vet, []);
    }

    /* حذف رأس */
    removeVertex(vet: Vertex): void {
        if (!this.adjList.has(vet)) {
            throw new Error('Illegal Argument Exception');
        }
        // حذف القائمة المترابطة المقابلة للرأس vet في قائمة التجاور
        this.adjList.delete(vet);
        // اجتياز القوائم المترابطة للرؤوس الأخرى وحذف جميع الأضلاع التي تحتوي على vet
        for (const set of this.adjList.values()) {
            const index: number = set.indexOf(vet);
            if (index > -1) {
                set.splice(index, 1);
            }
        }
    }

    /* طباعة قائمة التجاور */
    print(): void {
        console.log('Adjacency list =');
        for (const [key, value] of this.adjList.entries()) {
            const tmp = [];
            for (const vertex of value) {
                tmp.push(vertex.val);
            }
            console.log(key.val + ': ' + tmp.join());
        }
    }
}