문제 설명
C++에서 깊이 우선 검색 알고리즘을 구현하려고 할 때 읽기 액세스 위반 (read access violation when I tried to implement Depth First Search algorithm in c++)
이것은 내 DFS 기능입니다. 내가 메인 함수에서 방문 배열을 할당했는데도 방문[start_vertex]이 작동하지 않는 이유를 모르겠다!
6 typedef Node** PtP;
void DFS(PtP list, int start_vertex, bool* visited)
{
cout << "the crash under this line";
if (visited[start_vertex])
{
cout << "ignore";
}
visited[start_vertex] = true;
Node* adj = list[start_vertex]; // linked list list[0]
// after this line start_vertex will be adjacency vertex of start vertex
while (adj != NULL)
{
DFS(list, adj‑>data, visited);
adj = adj‑>next;
}
}
이것은 내가 bool 배열을 생성하고 그것을 4개의 요소로 할당한 나의 메인 함수이다. DFS 기능을 연결합니다.
int main()
{
PtP list;
list = new Node * [4];
for (int i = 0; i < 4; i++)
{
list[i] = new Node[4];
list[i] = NULL;
}
for (int i = 0; i < 4; i++)
{
cout << "enter number of vertices adjacency with " << i << ": ";
int temp;
cin >> temp;
addEdge2(list, i, temp);
}
for (int i = 0; i < 4; i++)
{
cout << "list[" << i << "]: ";
traverse(list[i]);
}
bool* visited = new bool[4];
for (int i = 0; i < 4; i++)
{
visited = false;
}
DFS(list, 0, visited);
for (int i = 0; i < 4; i++)
{
cout << "visisted: " << visited[i] << " ";
}
for (int i = 0; i < 4; i++)
{
delete [] list[i];
}
delete [] list;
return 0;
}
DFS 방법 테스트를 위한 전체 프로그램입니다.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};
typedef Node* Ptr;
typedef Node** PtP;
void addFront(Ptr& First, int x)
{
Ptr p;
p = new Node;
p‑>data = x;
p‑>next = First;
First = p;
}
void addEdge(PtP &list, int v1, int v2)
{
addFront(list[v1], v2);
addFront(list[v2], v1);
}
void addEdge2(PtP& list, int v, int num_of_adj_vtex)
{
cout << "enter vertices adjacency with " << v << ": ";
int temp;
for (int i = 0; i < num_of_adj_vtex; i++)
{
cin >> temp;
addFront(list[v], temp);
}
}
void traverse(Node* first)
{
Node* p = first;
while (p != NULL)
{
cout << p‑>data<<" ";
p = p‑>next;
}
cout << "\n";
}
void DFS(PtP list, int start_vertex, bool* visited)
{
if (visited[start_vertex])
{
cout << "vertex: " << start_vertex << " visited ";
}
visited[start_vertex] = true;
// linked list list[0] after this line start_vertex will be adjaceny vertex of start vertex
Node* adj = list[start_vertex];
while (adj != NULL)
{
DFS(list, adj‑>data, visited);
adj = adj‑>next;
}
}
int main()
{
PtP list; //type def node ** ptp
list = new Node * [4];
for (int i = 0; i < 4; i++)
{
list[i] = NULL;
}
for (int i = 0; i < 4; i++)
{
cout << "enter number of vertices adjacency with " << i << ": ";
int temp;
cin >> temp;
addEdge2(list, i, temp);
}
for (int i = 0; i < 4; i++)
{
cout << "list[" << i << "]: ";
traverse(list[i]);
}
bool* visited = new bool[4];
for (int i = 0; i < 4; i++)
{
visited[i] = false;
}
DFS(list, 0, visited);
for (int i = 0; i < 4; i++)
{
cout << "visisted: " << i << " "<< visited[i] << " ";
}
delete [] list;
return 0;
}
참조 솔루션
방법 1:
Ok, from what I can see, the problem seems to be user input related. The method:
void addEdge2(PtP& list, int v, int num_of_adj_vtex)
{
cout << "enter vertices adjacency with " << v << ": ";
int temp;
for (int i = 0; i < num_of_adj_vtex; i++)
{
cin >> temp;
addFront(list[v], temp); //Here if temp > 3 your later code will fail.
}
}
Requests user input and stores it at the front of the list...whatever is the value of temp, and puts it into the data field.
Later on when you do the DFS method you call the same method recursively:
DFS(list, adj‑>data, visited);
adj = adj‑>next;
This depends on what adj‑>data has stored, from the addEdge2 function. Since you have set the boolean array to a length of 4, that adj‑>data must be pointing to any value > 3 which would throw the error you mentioned because it is trying to access unallocated memory.
It seems like the code is not wrong, exactly, even though you could probably set some safeguards like making sure the user enters a value from 0 to 3.
(by Phạm Hoàng Việt、MiltoxBeyond)