0

我做了很多研究，似乎所有示例都使用邻接列表来存储图形，这似乎改变了在图形中查找循环的方式。我正在使用邻接矩阵存储图形。这是我的图表的代码。isCyclic 函数是我发现的，但不适用于邻接矩阵，它们也不打印循环。

#pragma once
#include"edge1.h"
#include <string>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <vector>

using namespace std;

class Graph
{
public:
    Graph(string f);
    void display(); 
    void computeTour();
    bool isCyclic();
private:
    char getChar(int n) { return (n + 'A'); }
    int getInt(char c) { return (c - 'A'); }

    void markCycles();
    void createGraphFromFile(string file);
    void addEdge(char a, char b);
    bool isCyclicUtil(int v, bool* visited, int parent);
    int totalNodes;
    int totalEdges;
    int **adj;
    bool *visited;
    vector<Edge> edges;
};

Graph::Graph(string f)
{
    createGraphFromFile(f);
}

void Graph::createGraphFromFile(string file)
{
    fstream fin;
    fin.open(file);

    fin >> totalNodes >> totalEdges;
    visited = new bool[totalNodes];
    adj = new int*[totalNodes];
    for (int i = 0; i < totalNodes; i++)
    {
        adj[i] = new int[totalNodes];
        for (int j = 0; j < totalNodes; j++)
        {
            adj[i][j] = 0;
        }
    }
    char a, b;
    while (fin >> a >> b)
    {
        addEdge(a,b);
    }
    fin.close();
}

void Graph::addEdge(char a, char b)
{
    Edge e;
    e.set(a, b);
    edges.push_back(e);
    int x = getInt(a);
    int y = getInt(b);
    if (x > totalNodes || y > totalNodes || x < 0 || y < 0)
    {
        cout << "Invalid edge!\n";
    }
    adj[x][y] = 1;
    adj[y][x] = 1;
}

bool Graph::isCyclicUtil(int v, bool* visited, int parent)
{
    visited[v] = true;

    for (int i = 0; i < totalNodes; i++)
    {
        if (!visited[i])
        {
            if (isCyclicUtil(i, visited, v))
                return true;
        }
        else if (i != parent)
            return true;
    }
    return false;
}

bool Graph::isCyclic()
{
    for (int i = 0; i < totalEdges; i++)
        visited[i] = false;
    for (int i = 0; i < totalEdges; i++)
    {
        if (!visited[i])
            if (isCyclicUtil(i, visited, -1))
                return true;
    }
    return false;
}

还有一个边缘类包含有关边缘的信息：

#include <sstream>
#include <assert.h>
using namespace std;

class Edge
{  public:
     int toNode;  // Subscript of one endpoint in node array.  Nodes are stored as numbers, but printed as characters.
     int fromNode; // Subscript of other endpoint in node array
     int cycleID;  // Cycle which the edge is a member of, -1 if it is included in no cycle
     bool used;    // true if edge is used in final tour

   // Create a string version of Edge
   // Edge endpoints are stored as numbers, but printed as characters.
   string toString()
   { ostringstream os;  // allows string to act like stream to use stream operations
     char t = toNode + 'A';
     char f = fromNode + 'A';
       os << "   "<<f << "-"<<t  << "(" << cycleID << ")" ;
       return os.str();
   }  

   // if oneNode is an endpoint, return other endpoint
   int getOtherEndpoint(int oneNode)
   { if (fromNode==oneNode) return toNode;
     assert(toNode==oneNode);
     return fromNode;
   }

   // Set initial values of an edge from Node f to Node t
   void set(char f, char t)
   {  fromNode = f -'A';
      toNode = t-'A';
      cycleID = -1;
      used = false;
      cout << "creating Edge " << toString()<<endl;
   }
};

我正在使用的图表有 7 个节点和 9 个边。这是创建图表时的输出，仅供参考。(-1) 只是每个边的循环 ID，因为它们都是刚刚创建的，它们还不属于循环。那就是我需要帮助的地方。

creating Edge    A-B(-1)
creating Edge    B-C(-1)
creating Edge    C-A(-1)
creating Edge    A-E(-1)
creating Edge    E-D(-1)
creating Edge    D-A(-1)
   A B C D E
A  0 1 1 1 1
B  1 0 1 0 0
C  1 1 0 0 0
D  1 0 0 0 1
E  1 0 0 1 0

我不知道如何遍历图表并找到并打印所有循环。

4

0 回答 0