Проверьте, связан ли неориентированный граф со списком смежности в C ++ - PullRequest
Новая
       15

Проверьте, связан ли неориентированный граф со списком смежности в C ++

0 голосов
/ 06 июля 2019

Мне нужно сделать функцию, которая проверяет, подключен ли данный неориентированный граф, реализованный с помощью списка смежности.Существует две структуры: одна, которая определяет узел в графе (который имеет метку (строку), которая его идентифицирует, указатель на его список смежности и одну на следующий узел в графе), и другая, которая определяет узлы в его смежности.list (с меткой, которая их идентифицирует, и указатель на следующий смежный узел в списке): 

struct graph::vertexNode {
    Label label;
    halfEdgeNode *adjList;
    vertexNode *next;
};   //typedef'ed as Graph

struct halfEdgeNode {
  Label label;
  halfEdgeNode* next; 
};

Я думал о запуске на нем BFS / DFS, но, учитывая эти структуры, у меня нетИдея, как реализовать такую ​​функцию: возможно ли вообще, БЕЗ ИЗМЕНЕНИЯ СТРУКТОВ, реализовать переменные bool, которые сообщают функции, был ли узел уже посещен или нет, что делает возможным обход?Как инициализировать DFS / BFS, так как я не знаю, как пометить все узлы как непосещенные?Или, может быть, есть способ проверить, подключен ли граф без использования DFS / BFS?

Вот возможные полезные вспомогательные функции, которые я сделал до сих пор: getVertex возвращает узел, идентифицированный этой меткой, проверки isVertexInGraphесли данный узел присутствует в графе, isEdgeInGraph проверяет, находится ли данный ребро в графе (только для вызова, когда присутствуют оба узла), и numVertices вычисляет количество узлов в данном графе. 

graph::Graph getVertex(Label l, const Graph& g) {
  for (graph::Graph v = g; v != NULL; v = v->next) {
      if (v->label == l) return  v; 
  }
  return NULL; 
}

bool isVertexInGraph(Label l, const Graph& g) {
  return (getVertex(l, g)!=NULL);
}

bool isEdgeInGraph(Label from, Label to, const Graph& g) {
 Graph h = getVertex(from, g);
 if (h == NULL) return false;
 for (halfEdgeNode* n = h->adjList; n != NULL; n = n->next) {
    if (n->label == to ) return true;
 }
 return false;
}

int numVertices(const Graph& g){
    int num = 0;
    for (Graph v = g; v != emptyGraph; v = v->next)
        num++;
    return num;
}

РЕДАКТИРОВАТЬ: Я не могу использовать любую библиотеку STD.РЕДАКТИРОВАТЬ: в шапке у меня это: 

typedef string Label;
typedef vertexNode* Graph;
...