0
저는 stackoverflow를 처음 사용하므로 나와 함께 맨발로하십시오.C++에서 그리드 모양의 방향이 지정되지 않은 비가 중 그래프를 만드는 방법
대각선을 포함하여 그리드 모양으로 그래프를 초기화하기 위해 for 루프를 구현하려고합니다. 기본적으로 그래프에 복제하려는 값으로 초기화되는 배열이 있습니다. 그래서 몇 가지 if 문을 포함하는 for 중첩 루프가 있습니다. if 문은 특수한 경우를 처리하는 데 사용됩니다. 즉, 인덱스 1,1의 요소에는 3 개의 이웃 만 있습니다.
그래프 함수가 작동하는 것으로 알고 있습니다. 수동으로 초기화해도 폴트가 발생하지 않고 적절한 BFS가 인쇄되기 때문에 루프가 작동하지 않습니다. 봐 주시기 바랍니다 :
그래프 클래스 :
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s, int d)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
int trail[V];
for(int i = 0; i < V; i++){
visited[i] = false;
trail[i] = -1;
}
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
if(s == d){
break;
}
else
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for(i = adj[s].begin(); i != adj[s].end(); ++i)
{
if(!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
trail[*i] = s;
}
}
}
int x = d;
while(x != -1){
cout<<x<<endl;
x = trail[x];
}
}
을 메인 프로그램에서 :
이int num = 2;
int arr[num+1][num+1];
int x = 1;
for(int i = 1; i<=num; i++){
for(int j = 1; j<= num; j++){
arr[i][j] = x;
cout<<x<<" ";
x++;
}
cout<<endl;
}
int max = 2;
Graph g(max+1);
for(int row = 1; row <= max; row++){
for(int col = 1; col <= max; col++){
if(row == 1 && col == 1){
g.addEdge(arr[row][col],(arr[row][col] +1));
g.addEdge(arr[row][col],(arr[row][col] +max));
g.addEdge(arr[row][col],(arr[row][col] + max+1));
}
else if(row ==1 && col == max){
g.addEdge(arr[row][col],(arr[row][col]-1));
g.addEdge(arr[row][col],(arr[row][col]+max));
g.addEdge(arr[row][col],(arr[row][col]+max-1));
}
else if(row == max && col == max){
g.addEdge(arr[row][col],(arr[row][col]-1));
g.addEdge(arr[row][col],(arr[row][col]-max));
g.addEdge(arr[row][col],(arr[row][col]-max-1));
}
else if(row == max && col == 1){
g.addEdge(arr[row][col],(arr[row][col]-max));
g.addEdge(arr[row][col],(arr[row][col]-max+1));
g.addEdge(arr[row][col],(arr[row][col]+1));
}
else if(row == max){
g.addEdge(arr[row][col],(arr[row][col]-1));
g.addEdge(arr[row][col],(arr[row][col]+1));
g.addEdge(arr[row][col],(arr[row][col]-max));
g.addEdge(arr[row][col],(arr[row][col]-max-1));
g.addEdge(arr[row][col],(arr[row][col]-max+1));
}
else if(col == max){
g.addEdge(arr[row][col],(arr[row][col]-1));
g.addEdge(arr[row][col],(arr[row][col]-max));
g.addEdge(arr[row][col],(arr[row][col]+max));
g.addEdge(arr[row][col],(arr[row][col]-max-1));
g.addEdge(arr[row][col],(arr[row][col]+max-1));
}
else if(col == 1){
g.addEdge(arr[row][col],(arr[row][col]+1));
g.addEdge(arr[row][col],(arr[row][col]+max));
g.addEdge(arr[row][col],(arr[row][col]-max));
g.addEdge(arr[row][col],(arr[row][col]-max+1));
g.addEdge(arr[row][col],(arr[row][col]+max+1));
}
else if(row == 1){
g.addEdge(arr[row][col],(arr[row][col]-1));
g.addEdge(arr[row][col],(arr[row][col]+1));
g.addEdge(arr[row][col],(arr[row][col]+max));
g.addEdge(arr[row][col],(arr[row][col]+max-1));
g.addEdge(arr[row][col],(arr[row][col]+max+1));
}
else{
g.addEdge(arr[row][col],(arr[row][col]+1));
g.addEdge(arr[row][col],(arr[row][col]-1));
g.addEdge(arr[row][col],(arr[row][col]+max));
g.addEdge(arr[row][col],(arr[row][col]-max));
g.addEdge(arr[row][col],(arr[row][col]-max-1));
g.addEdge(arr[row][col],(arr[row][col]-max+1));
g.addEdge(arr[row][col],(arr[row][col]+max-1));
g.addEdge(arr[row][col],(arr[row][col]+max+1));
}
}
}
참고 : I는 1에서 시작하는 내 그래프의 정점을 원하지만 0에서이가 왜 내 행렬에 여분의 행과 열이 있는지. 또한 내 그래프는 양방향으로 가장자리를 추가해야하므로 1 -> 0 및 0 ---> 1이됩니다.
감사합니다.