Вот мой код, который реализует граф с использованием списка смежности и выполняет поиск в ширину (BFS) и поиск в глубину (DFS).
При создании графа и добавлении ребер я сталкиваюсь с проблемой ошибки при создании графа. Я не уверен в указателе, который я использовал.
Можете подсказать, где я не прав?
#include "Graph.h"#include <iostream>
using namespace std;
int Graph::pop()
{
if (top = -1) {
cout << "empty";
return 0;
} else
return stack[top--];
}
void Graph::push(int value)
{
if (top >= 50) {
cout << "full";
} else
stack[++top] = value;
}
void Graph::add(int val)
{
if (rear != 49)
qu[++rear] = val;
else
cout << "full";
}
int Graph::del()
{
if (rear == front) {
cout << "empty";
return 0;
} else
front += 1;
return qu[front];
}
int Graph::gethead()
{
return rear;
}
int Graph::gettail()
{
return front;
}
node *Graph::createnode(int t)
{
node *temp;
temp = new node;
temp->val = t;
temp->next = NULL;
return temp;
}Graph::Graph()
{
rear = -1;
front = -1;
top = -1;
}
Graph::Graph(int t)
{
struct arr r[t];
a = r;
for (int i = 0; i < t; i++) {
a[i].key = i;
a[i].begin = NULL;
a[i].end = NULL;
}
int q[t];
p = q;
for (int k = 0; k < t; k++) {
p[k] = 0;
}
}
void Graph::visited(int v1)
{
p[v1] = 1;
}
bool Graph::isvisited(int v1)
{
if (p[v1] == 1)
return true;
else
false;
}
void Graph::addEdge(int v1, int v2)
{
if (a[v1].begin == NULL) {
node *temp = createnode(v2);
a[v1].begin = temp;
a[v1].end = temp;
} else {
node *temp = createnode(v2);
node *temp1 = a[v1].end;
temp1->next = temp;
a[v1].end = temp;
}
if (a[v2].begin == NULL) {
node *temp = createnode(v1);
a[v2].begin = temp;
a[v2].end = temp;
} else {
node *temp = createnode(v1);
//node *temp2=a[v2].end;
//temp2->next=temp;
a[v2].end->next = temp;
//a[v2].end->next=temp;
a[v2].end = temp;
}
}
void Graph::deleteEdge(int v1, int v2)
{
node *temp;
temp = a[v1].begin;
if (a[v1].begin->val == v2) {
a[v1].begin = a[v1].begin->next;
delete(temp);
temp = NULL;
} else {
node *t = temp->next;
while (t != NULL) {
if (t->val == v2) {
temp->next = t->next;
delete(t);
} else {
temp = t;
t = t->next;
}
}
}node *temp1;
temp1 = a[v2].begin;
if (a[v2].begin->val == v1) {
a[v2].begin = a[v2].begin->next;
delete(temp);
temp = NULL;
} else {
node *t = temp->next;
while (t != NULL) {
if (t->val == v1) {
temp->next = t->next;
delete(t);
} else {
temp = t;
t = t->next;
}
}
}
}
void Graph::BFS(int source)
{
add(source);
visited(source);
node *temp = a[source].begin;
while (temp != a[source].end) {
add(temp->val);
}
int r = del();
cout << r << endl;
while (gethead() != gettail()) {
int v1 = del();
visited(v1);
node *temp1;
temp1 = a[v1].begin;
while (temp1 != NULL) {
if (p[temp1->val] != 1) {
add(temp1->val);
temp1 = temp1->next;
} else
temp1 = temp1->next;
}
if (temp1 == NULL)
cout << v1 << endl;
}
}
void Graph::DFS(int source)
{
int c = source;
cout << c;
visited(c);
node *temp2 = a[source].begin;
while (a[source].end != NULL) {
push(temp2->val);
temp2 = temp2->next;
}
c = pop();
while (top != -1) {
node *temp = a[c].begin;
if (p[c] != 1) {
cout << c;
while (temp != NULL) {
push(temp->val);
temp = temp->next;
visited(c);
c = pop();
}
}
if (p[c] = 1) {
c = pop();
}
}
}
Первая очевидная ошибка заключается в том, что в линии if (top = -1)
, =
следует заменить на ==
,
Других решений пока нет …