2

在此处输入图像描述

如何从这样的图中删除所有循环？所有边长都是一，所有边要么是垂直的，要么是水平的。该图已连接。

我想计算为了使图形不包含循环而必须删除的最少边数。

如果您包含示例代码（最好是 C++、C 或 Java），那将非常有帮助。

更新：显然我必须找到顶点和边的数量。我遇到的问题给出了一组指令，例如（下、左、上、下、左、左、上、下）。您从坐标平面中的 (0, 0) 开始，沿指定方向移动一个单位。这将创建一个图表。我如何从这组指令中获得顶点和边的数量？

4

2 回答 2

2

由于图是连接的，如果点是，如你所写，

计算为使图不包含环而需要删除的最小边数

那么你真的不需要编写算法。众所周知，去除环的结果是一棵树，所有树的边数都相同（顶点数减一）。

如果重点是实际枚举剩余的边缘（或删除的边缘），那么您可以使用 DFS（深度优先搜索）。具体来说，在DFS 的输出中，您只需要保留那里标记为“树边”的内容。

虽然有用于 DFS 的 C++ 库，但它们可能不会以这种方式枚举边缘，并且您自己编写代码可能更容易。如您所见，伪代码非常简单。

于 2016-01-16T05:23:55.453 回答
0

要根据方向（上、下、左、右）绘制图形，并保持顶点、边的计数（并由此派生：基本循环），您可以：

  • 记录当前的 x、y 坐标——一只“乌龟”；
  • 保留一组已访问的顶点，因此您只计算唯一实例；
  • 对边做同样的事情，或者更节省内存：查看最近的移动是否包含至少一个之前未访问过的点，并且不是前一个移动的相反：如果是，则将其视为一条边。

这是一个 JavaScript 实现——作为奖励——也绘制图形：

function countEdgesAndVertices(directions, callback) {
    var turtle = [0, 0],
        vertices = {},
        revisit = false,
        edgeCount = 0,
        delta = {l: [-1, 0], r: [1, 0], u: [0, -1], d: [0, 1]},
        opposite = {l: 'r', r: 'l', u: 'd', d: 'u'},
        oppositeDir = '';
    vertices[turtle.join(',')] = true;
    directions.split('').forEach(function(dir) {
        if (!delta[dir]) return; // ignore invalid characters
        // Move turtle in given direction
        turtle[0] += delta[dir][0];
        turtle[1] += delta[dir][1];
        // Call caller's callback function with this vertex
        if (callback) callback(turtle);
        vertexId = turtle.join(',');
        // If this created a new edge, count it
        if (!vertices[vertexId] || !revisit && dir != oppositeDir) edgeCount++;
        // Remember whether we were here before
        revisit = vertices[vertexId];
        // Add vertice to set
        vertices[vertexId] = true;
        // Remember direction, so we wont count a move
        // in the opposite direction as a new edge
        oppositeDir = opposite[dir];
    });
    return {
        edges: edgeCount,
        vertices: Object.keys(vertices).length
    }
}

// IO
var input = document.querySelector('input');
var output = document.querySelector('span');
var canvas = document.querySelector('canvas');
var canvasContext;

// Drawing routines
function canvasDrawTo(vertex) {
    var scale = canvas.height/10;
    console.log('line to ', vertex[0],vertex[1]);
    canvasContext.lineTo(vertex[0]*scale,vertex[1]*scale);
    canvasContext.stroke();
}

function canvasClear(vertex) {
    canvas.width = canvas.width; // not nice, but this resets canvas
    canvasContext = canvas.getContext("2d");
    canvasContext.translate(canvas.width/2,canvas.height/2);
    canvasContext.beginPath();
    canvasContext.lineTo(0,0);
}

function update() {
    canvasClear();
    var result = countEdgesAndVertices(input.value, canvasDrawTo);
    output.textContent = 'Vertices: ' + result.vertices +
        '; Edges: ' + result.edges + 
        '; Non-divisable cycles: ' + (result.edges - result.vertices + 1);
};

// call update on any input change:
input.oninput = update;
// call update on load
update();
String of directions (u=up,d=down,l=left,r=right):<br>
<input type="text" size="40" value="uldrdddurulurdrdluurdur"><br>
Result: <span></span><br>
<canvas width="200" height="100"></canvas>

当您更改输入时，结果会实时更新。

于 2016-02-22T15:23:40.227 回答