Удалить циклы из связного графа, находя вершины и ребра

Question

Как я могу удалить все циклы из графика, как это? Все длины кромок являются единичными, а все ребра - вертикальными или горизонтальными. График связан.

Я хочу вычислить наименьшее количество ребер, которые необходимо удалить, чтобы график не содержал циклов.

Было бы очень полезно, если бы вы включили пример кода (желательно C++, C или Java).

UPDATE: По-видимому, мне нужно найти количество вершин и ребер. Проблема, которую я задаю, дает набор инструкций, таких как (вниз, влево, вверх, вниз, влево, влево, вверх, вниз). Вы начинаете с (0, 0) в плоскости координат и перемещаете один блок в указанном направлении. Это создаст график. Как получить количество вершин и ребер из этого набора инструкций?

Answer 1

Поскольку граф соединен, если точка, как вы писать,

вычислить наименьшее число ребер, которые должны быть удалены для того, чтобы граф, не содержат циклов

, тогда вам не нужно писать алгоритм. Хорошо известно, что результатом удаления циклов является дерево, и все деревья имеют одинаковое количество ребер (число вершин минус единица).

---

Если точка на самом деле перечислить оставшиеся края (или удалены края), то вы можете использовать DFS (глубина первого поиска). Конкретно, в output of DFS вам нужно сохранить только то, что обозначено там как «ребро дерева».

Несмотря на то, что существуют библиотеки C++ для DFS, они могут не перечислить края таким образом, и, возможно, было бы проще закодировать это самостоятельно. Как вы можете видеть, pseudocode довольно прост.

Answer 2

Чтобы нарисовать график, основанный на направлениях (вверх, вниз, влево, вправо), и сохранить количество вершин, ребер (и производные от: элементарных циклов), вы можете:

• вести учет текущей координаты 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>

Результаты обновляются в режиме реального времени по мере изменения входного сигнала.