JS演示图论汇总

缺乏、安全感 2023-06-29 07:23 4阅读 0赞

BFS.js

DFS.js

kruskal.js

prim.js

JS.js

//半径
    var r = 10;
    //鼠标状态
    var mStatus = 3;
    //画边时的第一个点
    var selectV = null;
    //顶点数组
    var vers = new Array();
    //边数组
    var edges = new Array();
    //邻接矩阵
    var adj = new Array();
    //遍历栈、队列
    var vstack = new Array();
    //接收canvas的onclick事件
    function CanvasClick(e) {
        e = e || event;
        var canvas = document.getElementById('MyCanvas');
        var x = e.clientX - canvas.offsetLeft;
        var y = e.clientY - canvas.offsetTop;
        switch (mStatus)
        {
            case 0:
                AddV(x, y);
                break;
            case 1:
                Select(x, y);
                break;
            case 2:
                AddE(x,y);
                break;
            default:
                break;
        }
        
    }
    //添加顶点
    function AddV(x, y) {
        //检查坐标是否符合添加顶点的要求
        if (CheckPoint(x, y)) {
            var v = new vertex(x, y);
            vers.push(v);
            DrawGraph();
            Output(" * 添加顶点:" + v.name + "。位置:" + v.x + "," + v.y + "<br/>");
        }
    }
    //选择顶点
    function Select(x, y) {
        for (var i = 0; i < vers.length; i++)
            if (Math.sqrt((vers[i].x - x) * (vers[i].x - x) + (vers[i].y - y) * (vers[i].y - y)) <= 10) {
                selectV = vers[i];
                selectV.isSelect = true;
                DrawGraph();
                mStatus = 2;
    
                Output("<font color='red'>" + " * 选中顶点:" + selectV.name + "</font><br/>");
                var canvas = document.getElementById('MyCanvas');
                canvas.style.cursor = 'url(画边.png),auto';
            }
    }
    //添加边
    function AddE(x, y) {
        for (var i = 0; i < vers.length; i++)
            if (Math.sqrt((vers[i].x - x) * (vers[i].x - x) + (vers[i].y - y) * (vers[i].y - y)) <= 10) {
                var eg = new edge(selectV, vers[i]);
                edges.push(eg);
                selectV.isSelect = false;
                DrawGraph();
                mStatus = 1;
                var canvas = document.getElementById('MyCanvas');
                canvas.style.cursor = 'url(选点.png),auto';
                Output("<font color='blue'>" + " * 添加边:" + eg.v1.name + eg.v2.name + "</font><br/>");
            }
    }
    //信息输出
    function Output(msg) {
        var outputDiv = document.getElementById('OutputDiv');
        outputDiv.innerHTML += msg;
    }
    //画顶点前检查坐标是否符合要求
    function CheckPoint(x, y) {
        if (x < 30 || x > 650 || y < 30 || y > 350)
            return false;
        for (var i = 0; i < vers.length; i++) {
            if (Math.sqrt((vers[i].x - x) * (vers[i].x - x) + (vers[i].y - y) * (vers[i].y - y)) < 60)
                return false;
        }
        return true;
    }
    
    //画点事件
    function AddVBtnClick() {
        mStatus = 0;
        var canvas = document.getElementById('MyCanvas');
        canvas.style.cursor = 'url(画点.png),auto';
    }
    //画边事件
    function AddEBtnClick() {
        if (selectV) {
            selectV.isSelect = false;
            var n = selectV.name;
            selectV = null;
            DrawGraph();
            Output("<font color='red'>" + " * 取消顶点:" + n + "</font><br/>");
        }
        else {
            mStatus = 1;
            var canvas = document.getElementById('MyCanvas');
            canvas.style.cursor = 'url(选点.png),auto';
        }
    }
    //绘图
    function DrawGraph() {
        var canvas = document.getElementById('MyCanvas');
        canvas.width = canvas.width;
        if (canvas.getContext) {
            var ctx = canvas.getContext('2d');
            for (var i = 0; i < vers.length; i++)
                vers[i].draw(ctx);
            for (var i = 0; i < edges.length; i++) {
                edges[i].draw(ctx);
            }
        }
    }
    //顶点构造函数
    var vertex = function (x, y) {
        this.x = x;
        this.y = y;
        this.name = String.fromCharCode(0x41 + vers.length);
        this.isSelect = false;
        this.isVisit = false;
        this.draw = function (ctx) {
            ctx.save();
            ctx.beginPath();
            ctx.strokeStyle = "#000000";
            ctx.arc(this.x, this.y, r, 2 * Math.PI, 0, true);
            ctx.closePath();
            ctx.stroke();
            if (this.isVisit) {
                ctx.fillStyle = "#00FF00";
                ctx.fill();
            }
            if (this.isSelect) {
                ctx.fillStyle = "#FFFF00";
                ctx.fill();
            }
            ctx.fillStyle = "#FF0000";
            ctx.fillText(this.name, parseInt(this.x) - 3, parseInt(this.y) + 3);
            ctx.restore();
        }
    }
    //边构造函数
    var edge = function (v1, v2) {
        this.v1 = v1;
        this.v2 = v2;
        this.isVisit = false;
        this.draw = function (ctx) {
            var x1 = parseInt(v1.x), y1 = parseInt(v1.y), x2 = parseInt(v2.x), y2 = parseInt(v2.y);
            var a = x1 - x2, b = y1 - y2, c = Math.sqrt(a * a + b * b);
            var beginX = x1 - a * r / c, beginY = y1 - b * r / c;
            var endX = x2 + a * r / c, endY = y2 + b * r / c;
            ctx.save();
            ctx.beginPath();
            if (this.isVisit)
                ctx.strokeStyle = "#FF0000";
            else
                ctx.strokeStyle = "#000000";
            ctx.moveTo(beginX, beginY);
            ctx.lineTo(endX, endY);
            ctx.stroke();
            ctx.closePath();
            ctx.restore();
        }
    }
    
    function loadXmlFile(xmlFile) {
        var xmlDom = null;
        if (window.ActiveXObject) {
            xmlDom = new ActiveXObject("Microsoft.XMLDOM");
            xmlDom.async = false;
            xmlDom.load(xmlFile) || xmlDom.loadXML(xmlFile); //如果用的是XML字符串//如果用的是xml文件  
        }
        else if (document.implementation && document.implementation.createDocument) {
            var xmlhttp = new window.XMLHttpRequest();
            xmlhttp.open("GET", xmlFile, false);
            xmlhttp.send(null);
            xmlDom = xmlhttp.responseXML;
        } 
        else {
            xmlDom = null;
        }
        return xmlDom;
    }
    
    
    function DrawBtnClick() {
        var canvas = document.getElementById('MyCanvas');
        canvas.width = canvas.width;
        vers = [];
        edges = [];
        var ctrlDiv = document.getElementById('CtrlDiv');
        CtrlDiv.innerHTML = "<input id=\"AddVBtn\" type=\"button\" value=\"画点\" onclick=\"AddVBtnClick();\" />";
        CtrlDiv.innerHTML += "<input id=\"AddEBtn\" type=\"button\" value=\"画边\" onclick=\"AddEBtnClick();\" />";
    }
    //清空
    function ClearBtnClick() {
        var canvas = document.getElementById('MyCanvas');
        canvas.width = canvas.width;
        vers = [];
        edges = [];
        var ctrlDiv = document.getElementById('CtrlDiv');
        CtrlDiv.innerHTML = "";
    }
    //保存
    function SaveBtnClick() {
        var verStr="";
        for (var i = 0; i < vers.length; i++) {
            verStr += vers[i].x + "," + vers[i].y + "," + vers[i].name;
            if (i != vers.length-1)
                verStr += ".";
        }
        var egStr="";
        for (var i = 0; i < edges.length; i++) {
            egStr += edges[i].v1.name + "," + edges[i].v2.name;
            if (i != edges.length-1)
                egStr += ".";
        }
        document.getElementById("HiddenField").value = verStr + "|" + egStr;
    }
    //载入
    function LoadBtnClick() {
        var xmlDoc = loadXmlFile("XMLFile.xml");
        var k = xmlDoc.getElementsByTagName("Graph").length;
        var s = "<select id=\"GraphSelect\">";
        for (var i = 0; i < k; i++) {
            s+="<option>"+xmlDoc.getElementsByTagName("Graph")[i].getAttribute('name')+"</option>";
        }
        s += "</select>";
        s += "<input id=\"SubmitBtn\" type=\"button\" value=\"提交\" onclick=\"SubmitBtnClick();\" />";
        var ctrlDiv = document.getElementById('CtrlDiv');
        CtrlDiv.innerHTML = s;
    }
    function SubmitBtnClick() {
        var gname=document.getElementById('GraphSelect').value;
        var xmlDoc = loadXmlFile("XMLFile.xml");
        var count = xmlDoc.getElementsByTagName("Graph").length;
        var vNode, eNode;
        for (var i = 0; i < count; i++) 
            if (xmlDoc.getElementsByTagName("Graph")[i].getAttribute('name') == gname) {
                vNode = xmlDoc.getElementsByTagName("Graph")[i].getElementsByTagName("vertexs")[0];
                eNode = xmlDoc.getElementsByTagName("Graph")[i].getElementsByTagName("edges")[0];
                break;
             }
        vers = [];
        for (var j = 0; j < vNode.getElementsByTagName("v").length; j++) {
            var x = vNode.getElementsByTagName("v")[j].getAttribute('x');
            var y = vNode.getElementsByTagName("v")[j].getAttribute('y');
            var name = vNode.getElementsByTagName("v")[j].getAttribute('name');
            var v = new vertex(x, y);
            v.name = name;
            vers.push(v);
        }
        edges = [];
        for (var j = 0; j < eNode.getElementsByTagName("eg").length; j++) {
            var v1,v2;
            for (var k = 0; k < vers.length; k++) {
                if (eNode.getElementsByTagName("eg")[j].getAttribute('v1') == vers[k].name)
                    v1 = vers[k];
                if (eNode.getElementsByTagName("eg")[j].getAttribute('v2') == vers[k].name)
                    v2=vers[k];
            }
            var eg = new edge(v1, v2);
            edges.push(eg);
        }
        DrawGraph();
    }
    //输出vstack内元素
    function OutVstack() {
        for (var i = 0; i < vstack.length; i++) {
            Output(vstack[i].name+" ");
        }
        Output("<br/>");
    }
    //DFS遍历演示
    function ShowDFSBtnClick() {
        if (vers.length <= 0)
            return;
        var s = "<select id=\"VertexSelect\">";
        for (var i = 0; i < vers.length; i++) {
            s += "<option>" + vers[i].name + "</option>";
        }
        s += "</select>";
        s += "<input id=\"BeginDFSBtn\" type=\"button\" value=\"开始\" onclick=\"BeginDFSBtnClick();\" />";
        s += "<input id=\"NextDFSBtn\" type=\"button\" value=\"下一步\" onclick=\"NextDFSBtnClick();\" />";
        var ctrlDiv = document.getElementById('CtrlDiv');
        CtrlDiv.innerHTML = s;
    }
    function Locate(v) {
        for (var i = 0; i < vers.length; i++)
            if (vers[i] == v)
                return i;
        return -1;
    }
    function LocateEg(v1, v2) {
        for (var i = 0; i < edges.length; i++)
            if ((edges[i].v1 == v1 && edges[i].v2 == v2)||(edges[i].v1 == v2 && edges[i].v2 == v1))
                return i;
        return -1;
    }
    function BeginDFSBtnClick() {
        var outputDiv = document.getElementById('OutputDiv');
        outputDiv.innerHTML = "";
        //初始化邻接矩阵，栈
        adj = [];
        for (var i = 0; i < vers.length; i++) {
            adj[i] = new Array();
            for (var j = 0; j < vers.length; j++)
                adj[i][j] = 0;
        }
        for (var i = 0; i < edges.length; i++) {
            adj[Locate(edges[i].v1)][Locate(edges[i].v2)] = 1;
            adj[Locate(edges[i].v2)][Locate(edges[i].v1)] = 1;
        }
        vstack = [];
        //获取开始顶点
        var vname = document.getElementById('VertexSelect').value;
        //开始顶点入栈，修改顶点状态，重绘图
        for (var i = 0; i < vers.length; i++)
            if (vers[i].name == vname) {
                vstack.push(vers[i]);
                vers[i].isVisit = true;
                vers[i].isSelect = true;
                Output(" * 访问顶点" + vers[i].name + "<br/>");
                Output(" * 顶点" + vers[i].name + "入栈,当前顶点为:" + vers[i].name + "<br/>");
            }
        DrawGraph();
    }
    function NextDFSBtnClick() {
        if (vstack.length <= 0) {
            alert("遍历结束");
            Output("<br/> * 遍历结束<br/>");
            return;
        }
        var cur = Locate(vstack[vstack.length - 1]);
        for (var j = 0; j < vers.length; j++)
            if (adj[cur][j] == 1 && !vers[j].isVisit) {
                vers[j].isVisit = true;
                vers[j].isSelect = true;
                vers[cur].isSelect = false;
                vstack.push(vers[j]);
                edges[LocateEg(vers[cur], vers[j])].isVisit = true;
                DrawGraph();
                Output(" * 通过顶点" + vers[cur].name + "访问顶点" + vers[j].name +  ",");
                Output("顶点" + vers[cur].name + "入栈,当前顶点为:" + vers[j].name + "<br/>");
                return;
            }
            vers[cur].isSelect = false;
            Output(" * 将顶点" + vers[cur].name + "出栈");
        vstack.pop();
        if (vstack.length > 0) {
            vstack[vstack.length - 1].isSelect = true;
            Output(",当前顶点为:" + vstack[vstack.length - 1].name + "<br/>");
        }
        DrawGraph();
    }
    
    //BFS遍历演示
    function ShowBFSBtnClick() {
        if (vers.length <= 0)
            return;
        var s = "<select id=\"VertexSelect\">";
        for (var i = 0; i < vers.length; i++) {
            s += "<option>" + vers[i].name + "</option>";
        }
        s += "</select>";
        s += "<input id=\"BeginBFSBtn\" type=\"button\" value=\"开始\" onclick=\"BeginBFSBtnClick();\" />";
        s += "<input id=\"NextBFSBtn\" type=\"button\" value=\"下一步\" onclick=\"NextBFSBtnClick();\" />";
        var ctrlDiv = document.getElementById('CtrlDiv');
        CtrlDiv.innerHTML = s;
    }
    function BeginBFSBtnClick() {
        var outputDiv = document.getElementById('OutputDiv');
        outputDiv.innerHTML = "";
        //初始化邻接矩阵，队列
        adj = [];
        for (var i = 0; i < vers.length; i++) {
            adj[i] = new Array();
            for (var j = 0; j < vers.length; j++)
                adj[i][j] = 0;
        }
        for (var i = 0; i < edges.length; i++) {
            adj[Locate(edges[i].v1)][Locate(edges[i].v2)] = 1;
            adj[Locate(edges[i].v2)][Locate(edges[i].v1)] = 1;
        }
        vstack = [];
        //获取开始顶点
        var vname = document.getElementById('VertexSelect').value;
        //开始顶点入队列，修改顶点状态，重绘图
        for (var i = 0; i < vers.length; i++)
            if (vers[i].name == vname) {
                vstack.push(vers[i]);
                vers[i].isVisit = true;
                vers[i].isSelect = true;
                Output(" * 访问顶点" + vers[i].name + "<br/>");
                Output(" * 顶点" + vers[i].name + "入队<br/>");
                Output("队列内元素:");
                OutVstack();
                Output("<font color='red'>  * 当前顶点为:" + vers[i].name + "</font><br/>");
            }
        DrawGraph();
    }
    function NextBFSBtnClick() {
        if (vstack.length <= 0) {
            alert("遍历结束");
            Output("<br/> * 遍历结束<br/>");
            return;
        }
        var cur = Locate(vstack[0]);
        for (var j = 0; j < vers.length; j++)
            if (adj[cur][j] == 1 && !vers[j].isVisit) {
                vers[j].isVisit = true;
                vstack.push(vers[j]);
                Output(" * 访问顶点" + vers[j].name + "并入队<br/>");
                edges[LocateEg(vers[cur], vers[j])].isVisit = true;
            }
        vstack.shift();
        vers[cur].isSelect = false;
        if (vstack.length <= 0) {
            alert("遍历结束");
            Output("<br/> * 遍历结束<br/>");
            DrawGraph();
            return;
        }
        vstack[0].isSelect = true;
        DrawGraph();
        Output("队列内元素:");
        OutVstack();
        Output("<font color='red'> * 当前顶点为:" + vstack[0].name + "</font><br/>");
    }
    
    function DelBtnClick() {
        var canvas = document.getElementById('MyCanvas');
        canvas.style.cursor = 'url(删除.png),auto';
    }