在遍历有向图时移除边 [英] Removing an edge while traversing a directed graph

问题描述

大家好，



如果元素等于传递给函数的顶点，我想从邻接列表中删除一个元素（这是一个有向图）在这种情况下，如果它等于'u'）。我想在遍历图表时（使用BFS）执行此操作。有谁知道我怎么做？



这是我用来遍历图表（BFS）和擦除边缘的代码。但它没有正常工作：

Hello everyone,

I want to erase an element from adjacency list (this is a digraph) if the element is equal to the vertex passed to the function (in this case, if it is equal to 'u'). I want to do it while traversing the graph (using BFS). Does anyone know how I can do it?

Here is the code I'm using to traverse the graph (BFS) and erase the edges. But it doesn't do the job properly:

void Graph::BFS(int u) {
	int w;
	bool *visited = new bool[V];
	queue<int> q;
    visited[u] = true;
    q.push(u);

    while(!q.empty()) {
    	w = q.front();
    	cout << w << " ";
    	q.pop();
    	list<int>::iterator i;

    	for(i=adj[w].begin(); i!= adj[w].end(); ) {
    		if(!visited[*i]) {
    			if(u == *i)
    				adj[w].erase(i++);
			visited[*i] = true;
			q.push(*i);
			++i;
			}
    		++i;
	        }
    }
}

BFS功能中使用的全局变量：

int V; //顶点数

list< int> * ADJ 的; //指向包含邻接列表的数组的指针





我尝试过：



我在下面的图表中测试了我的代码：



0-> 0,0-> 1 ，0-> 2，1-> 2，2-> 3,3-> 3



我的代码从我开始时正确完成工作0或1，但是当我将2或3传递给BFS时，陷入无限循环（可能）。

Global variables used in BFS function:
int V; //Number of vertices
list<int> *adj; //Pointer to an array containing adjacency lists


What I have tried:

I tested my code on following Graph:

0->0 , 0->1 , 0->2, 1->2, 2->3, 3->3

My code does the job correctly when I start from 0 or 1, but trapped in an infinite loop (probably) when I pass 2 or 3 to the BFS.

推荐答案

你应该学会尽快使用调试器可能。而不是猜测你的代码在做什么，现在是时候看到你的代码执行并确保它完成你期望的。



调试器允许你跟踪执行逐行检查变量，你会看到它有一个停止做你期望的点。

调试器 - 维基百科，免费的百科全书 [ ^ ]

掌握Visual Studio 2010中的调试 - A初学者指南 [ ^ ]

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

引用：

但被困在一个无限循环（可能）当我将2或3传递给BFS时。

but trapped in an infinite loop (probably) when I pass 2 or 3 to the BFS.

使用调试器，您将看到无限循环的位置。

With the debugger, you will see where is the infinite loop.

让我们从我能看到的最明显的问题开始，你要避开初始化访问的bool数组

Lets start with the most obvious problem I can see, that you haven't initialized the bool array visited

bool *visited = new bool[V]; // this leaves all the values in the array random 

你确定你不是故意这样初始化它吗？

are you sure you didn't mean to initialize it like so?

bool *visited = new bool[V](); // this zeros the entire array 

或者只是memset等数组来初始化它。

Alternatively just memset etc the array to initialize it.

这篇关于在遍历有向图时移除边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！