Я ищу краткое и точное представление списка смежности графа в С++. Мои узлы - это просто идентификаторы узлов. Вот как я это сделал. Просто хочется узнать, что об этом думают специалисты. Есть ли способ лучше?
Это реализация класса (ничего особенного, сейчас мне все равно на публичные/приватные методы)
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
using namespace std;
class adjList {
public:
int head;
vector<int> listOfNodes;
void print();
};
void adjList :: print() {
for (int i=0; i<listOfNodes.size(); ++i) {
cout << head << "-->" << listOfNodes.at(i) << endl;
}
}
class graph {
public:
vector<adjList> list;
void print();
};
void graph :: print() {
for (int i=0; i<list.size(); ++i) {
list.at(i).print();
cout << endl;
}
}
Моя основная функция анализирует входной файл построчно. Где каждая строка интерпретируется следующим образом:
<source_node> <node1_connected_to_source_node> <node2_connected_to_source_node <node3_connected_to_source_node> <...>
Вот основное:
int main()
{
fstream file("graph.txt", ios::in);
string line;
graph g;
while (getline(file, line)) {
int source;
stringstream str(line);
str >> source;
int node2;
adjList l;
l.head = source;
while (str >> node2) {
l.listOfNodes.push_back(node2);
}
g.list.push_back(l);
}
file.close();
g.print();
getchar();
return 0;
}
Я знаю, что должен добавить функцию addEdge() в класс adjList вместо того, чтобы напрямую изменять ее переменную из main(), однако сейчас я просто думаю о лучшей структуре.
EDIT: В моем подходе есть один недостаток. Для сложного графа с большим количеством узлов node действительно будет структурой/классом, и в этом случае я буду дублировать значения, сохраняя весь объект. В этом случае я думаю, что должен использовать указатели. Например, для неориентированного графа я буду хранить копии объектов узла в adjList (соединение между узлами 1 и 2 означает, что в списке смежности 1 будет 2, и наоборот). Я могу избежать этого, сохраняя указатели объектов узлов в adjList, а не весь объект. Проверьте реализацию dfs, которая извлекает выгоду из этого подхода. Там мне нужно убедиться, что каждый узел посещается только один раз. Наличие нескольких копий одного и того же узла усложнит мне жизнь. нет?
В этом случае мои определения классов изменятся следующим образом:
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>
using namespace std;
class node {
public:
node() {}
node(int id, bool _dirty): node_id(id), dirty(_dirty) {}
int node_id;
bool dirty;
};
class adjList {
public:
node *head;
vector<node*> listOfNodes;
void print();
~adjList() { delete head;}
};
void adjList :: print() {
for (int i=0; i<listOfNodes.size(); ++i) {
cout << head->node_id << "-->" << listOfNodes.at(i)->node_id << endl;
}
}
class graph {
public:
vector<adjList> list;
void print();
void dfs(node *startNode);
};
void graph::dfs(node *startNode) {
startNode->dirty = true;
for(int i=0; i<list.size(); ++i) {
node *stNode = list.at(i).head;
if (stNode->node_id != startNode->node_id) { continue;}
for (int j=0; j<list.at(i).listOfNodes.size(); ++j) {
if (!list.at(i).listOfNodes.at(j)->dirty) {
dfs(list.at(i).listOfNodes.at(j));
}
}
}
cout << "Node: "<<startNode->node_id << endl;
}
void graph :: print() {
for (int i=0; i<list.size(); ++i) {
list.at(i).print();
cout << endl;
}
}
И вот как я реализовал функцию main(). Я использую карту‹>, чтобы избежать дублирования объектов. Создание нового объекта только в том случае, если он не был определен ранее. Проверка существования объекта по его id.
int main()
{
fstream file("graph.txt", ios::in);
string line;
graph g;
node *startNode;
map<int, node*> nodeMap;
while (getline(file, line)) {
int source;
stringstream str(line);
str >> source;
int node2;
node *sourceNode;
// Create new node only if a node does not already exist
if (nodeMap.find(source) == nodeMap.end()) {
sourceNode = new node(source, false);
nodeMap[source] = sourceNode;
} else {
sourceNode = nodeMap[source];
}
adjList l;
l.head = sourceNode;
nodeMap[source] = sourceNode;
while (str >> node2) {
// Create new node only if a node does not already exist
node *secNode;
if (nodeMap.find(node2) == nodeMap.end()) {
secNode = new node(node2, false);
nodeMap[node2] = secNode;
} else {
secNode = nodeMap[node2];
}
l.listOfNodes.push_back(secNode);
}
g.list.push_back(l);
startNode = sourceNode;
}
file.close();
g.print();
g.dfs(startNode);
getchar();
return 0;
}
ВТОРОЕ РЕДАКТИРОВАНИЕ После предложения Ульриха Экхардта поместить список смежности в класс узла, вот что я думаю, это лучшая структура данных для хранения графа и выполнения dfs(), dijkstra( ) виды операций. Обратите внимание, что список смежности объединен в классе узла.
#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <map>
using namespace std;
class node {
public:
node() {
}
node(int id, bool _dirty): node_id(id), dirty(_dirty) {
//cout << "In overloaded const\n";
}
int node_id;
bool dirty;
vector<node*> listOfNodes;
};
class graph {
public:
vector<node*> myGraph;
void dfs(node* startNode);
};
void graph::dfs(node* startNode) {
startNode->dirty = true;
for (int j=0; j<startNode->listOfNodes.size(); ++j) {
if (!startNode->listOfNodes.at(j)->dirty) {
dfs(startNode->listOfNodes.at(j));
}
}
cout << "Node: "<<startNode->node_id << endl;
}
Можем ли мы сделать лучше, чем это?
