export default class Graph {
    private _isDirected: boolean; // 图是否是有向图
    private _vertices: Array<string | number> = []; // 顶点的名字
    private _adjList: Map<string | number, Array<string | number>>; // 顶点和它的相邻顶点
    constructor(isDirected: boolean = false) {
        this._isDirected = isDirected;
        this._adjList = new Map<string | number, Array<string | number>>();
    }
    /**
     * 添加顶点
     */
    public addVertex(vertex: string | number) {
        if (!this._vertices.includes(vertex)) { // 顶点不存在才添加，includes是ES2016方法
            this._vertices.push(vertex);
            this._adjList.set(vertex, []); // 邻接顶点的存放采用map结构
        }
    }
    /**
     * 顶点之间的关系，也就是两者之间是否有边相连
     * v,w是两个顶点
     * weight是权重
     */
    public addEdge(v: string | number, w: string | number) {
        if (!this._adjList.get(v)) { // v没有加进顶点数组里就会新添加进去
            this.addVertex(v);
        }
        if (!this._adjList.get(w)) { // w没有加进顶点数组里就会新添加进去
            this.addVertex(w);
        }
        this._adjList.get(v).push(w);
        // 无向图才会认为两者彼此相邻。如果是单向的就调用一次addEdge，双向就调用两次addEdge
        if (!this._isDirected) {
            this._adjList.get(w).push(v);
        }
    }

    /**
     * 顶点
     */
    public getVertices(): Array<string | number> {
        return this._vertices;
    }
    /**
     * 边
     * 顶点和它的相邻顶点
     */
    public getAdjList(): Map<string | number, Array<string | number>> {
        return this._adjList;
    }

    /**
     * 图的字符串形式
     */
    public toString() {
        let s: string = '';
        for (let i = 0, vl = this._vertices.length; i < vl; i ++) {
            const vertex = this._vertices[i]; // 顶点
            s += vertex + ' -> ';
            const neighbors: Array<string | number> = this._adjList.get(vertex); // 顶点的邻接顶点
            for (let j = 0, el =  neighbors.length; j < el; j ++) {
                s = `${s}, ${neighbors[j]}`;
            }
            s += '/n';
        }
        return s;
    }
}