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

Question

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

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

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

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

ОБНОВЛЕНИЕ: Видимо, я должен найти количество вершин и ребер.
У меня проблема дает набор инструкций, таких как (вниз, влево, вверх, вниз, влево, влево, вверх, вниз). Вы начинаете с (0, 0) в координатной плоскости и перемещаете одну единицу в указанном направлении. Это создаст график. Как я могу получить количество вершин и ребер из этого набора инструкций?

2

c++cycle cyclic graph undirected-graph

Решение

Другие решения

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

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

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

0

Источник

Accepted Answer

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

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

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

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

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

2