使用 DFS C++ 实现从邻接列表到边列表的图

Question

我有一个包含无向图邻接表的文本文件，示例：
1 2 3
2 1 3 4
3 1 2 4
4 2 3
我正在读取文件并将其存储在邻接列表中，
我想将此数据传输到边缘列表，
我试图找出所有独特的边对，
使用 DFS 我得到了对，但它们不是唯一的，
我正在尝试消除重复对（重复对是 <1,2> 与 <2,1> 相同）但它没有发生......

这是我得到的结果：

1 的度数是：2
顶点数为：4
边数为：5
最大度数为：3
最小度数为：2
边列表：.........

1 2
边缘 1 2 已插入
返回：2 1
边 2 1 已插入

2 3
边缘 2 3 已插入
返回：3 1
边缘 3 1 已插入
返回：3 2
边 3 2 已插入

3 4
边缘 3 4 已插入
返回：4 2
边缘 4 2 已插入
返回：4 3
边缘 4 3 已插入
返回：2 4
边缘 2 4 已插入
返回：1 3
边缘 1 3 已插入

谢谢... 抱歉代码太长.........

#include <iostream>
#include <fstream>
#include <limits>
#include <vector>
#include <list>
#include <string>  
#include <sstream>
#include <cstdlib>
#include <map>

using namespace std;

typedef struct EdgeList
{
    int u;
    int v;
}EdgeList;


class Graph
{
    public:
        vector<list<int> > adj;
        int V;
        int E;

        EdgeList *edges;

        Graph(int N):adj(N+1)
        {
            V = N;
        }
        Graph(int N, int M):adj(N+1)
        {
            V = N; 
            E = M; 
            int x = E+550;
            edges = new EdgeList[x];
        }

        void addEdgeList(Graph g, int u, int v);
        bool ischeckEdge(Graph g,int u,int v);

        void addEdge(int u, int v);
        void deleteSelfLoops(Graph g);

        int degree(Graph g, int v);
        int maxDegree(Graph g);
        int minDegree(Graph g);
        int edgeCount(Graph g);
        int numberOfSelfLoops(Graph g); 

        bool isEdge(Graph g, int u,int v);

        void DFS(Graph g);
        void dfsUtil(Graph g, int v, bool visited[] );              
};

int e = 0;
void Graph::addEdgeList(Graph g, int u, int v)
{
    if(ischeckEdge(g,u,v))
    {
        cout<<"Edge "<<u<<" "<<v<<" Inserted "<<endl;
        g.edges[e].u = u;
        g.edges[e].v = v;
        e++;
    }
}

bool Graph::ischeckEdge(Graph g, int u, int v)
{
    bool a,b,c,d;


    for(int i=0;i<=g.E; i++)
    {

        if( ((g.edges[i].u == u || g.edges[i].v == v) && (!g.edges[i].u == u || !g.edges[i].v == v)) )
        {
            cout<<"First block" ;
            return false;

        }
        else if( ((g.edges[i].u == v || g.edges[i].v == u) && (!g.edges[i].u == v || !g.edges[i].v == u)))
        {
            cout<<" sec block";
            return false;
        }
        else 
        {
            return true;
        }
    }
}


void Graph::dfsUtil(Graph g, int v, bool visited[])
{
    list<int> temp;
    temp  = g.adj[v];

    if(!visited[v])
    {
         visited[v] = true; 
    }

    list<int>::iterator j;
    for(j = temp.begin();j != temp.end(); j++)
    {
        if(!visited[*j])
        {
            cout<<endl<<v<<" "<<*j<<endl;// print edges
            g.addEdgeList(g,v,*j);
            dfsUtil(g, *j, visited);
        }
        else //back edge
        {
            cout<<" Back : "<<v<<" "<<*j<<endl;
            g.addEdgeList(g,v,*j);
        }
    }   
}

void Graph::DFS(Graph g)
{
    bool *visited = new bool[g.V+1];
    int *parent = new int[g.V+1];

    for(int i = 0; i <= g.V; i++)
    {
         visited[i] = false;
         parent[i] = -1;
    }

    for(int v = 0; v <= g.V; v++)
    {
        if(!visited[v])
        {
            dfsUtil(g, v , visited);
        }
    }
 }

 bool Graph::isEdge(Graph g, int u, int v)
 {
     for(int w : adj[v])
     {
        if(u == w)
        {
            return true;
        }
     }
    return false;
 }


void Graph::addEdge(int u, int v)
{
    adj[u].push_back(v); //undirected graph
    //adj[v].push_back(u);
}

void Graph::deleteSelfLoops(Graph g)
{
    for(int v = 0; v <= g.V; v++)
   {
        for(int w : g.adj[v])
        {
            if(v == w)
            {
                g,adj[v].remove(w);
            }
       }
    }
}

int Graph::degree(Graph g, int v)
{
     int deg = 0;

    for(int i = 0;i < g.adj[v].size();i++)
    {
        deg++;
    }   
    return deg;
}

int Graph::edgeCount(Graph g)
{
    int edge = 0;
    int i;

    if(g.adj[0].empty())
    {
         i = 1;
    }
    else
    {
        i = 0;
    }

    for(i; i <= g.V; i++)
    {
        edge = edge + degree(g,i);
    }

   return edge/2; //handshaking lemma
}

int Graph::maxDegree(Graph g)
{
    int max = 0;

    for(int i = 0; i <= g.V; i++)
    {
        if(degree(g,i) > max)
        {
            max = degree(g,i);
        }
    }
    return max;
 }

int Graph::minDegree(Graph g)
{
    int min = g.V;
    int i;

    if(g.adj[0].empty())
    {
        i = 1;
    }
    else
    {
        i = 0;
    }

    for(i; i <= g.V; i++)
    {
        if(degree(g,i) < min)
        {
            min = degree(g,i);
        }
    }
    return min;
}

int Graph::numberOfSelfLoops(Graph g)
{
    int count = 0;

    for(int v = 0; v <= g.V; v++)
    {
        for(int w : g.adj[v])
        {
            if(v == w)
            {
                count++;
            }
        }
    }

    return count / 2;
 }



int main()
{
    ifstream fin("AdjList.txt");

    int V = 0;

    string str;

    while(getline(fin, str)) 
    {
    istringstream ss(str);
    int num;

    while(ss >> num)
    {
        // ... you now get a number ...
        int u;
        u = str[0] - '0'; //char can be coverted to int
        if(num != u )
        {
             //cout<<u<< "  "<< num<<endl;

        }
    }
    V++;
}
fin.close();

Graph g1(V);

fin.open("AdjList.txt");
while(getline(fin, str)) 
{
    istringstream ss(str);
    int num;

    while(ss >> num)
    {
        // ... you now get a number ...
        int u;
        u = str[0] - '0'; //char can be coverted to int
        if(num != u )
        {
             g1.addEdge(u,num);
             //cout<<u<< "  "<< num<<endl;

            }
        }
    }
    fin.close();

    Graph g(V,g1.edgeCount(g1));
    g.adj = g1.adj;

    cout<<"degree of 1 is : "<<g.degree(g,1)<<endl;
    cout<<"Nember of vertices is :"<<g.V<<endl;
    cout<<"Numbe rof edges is : "<< g.edgeCount(g)<<endl;
    cout<<"Max degree is : "<<g.maxDegree(g)<<endl;
    cout<<"Min degree is : "<<g.minDegree(g)<<endl;

    cout<<"List of edges : .........."<<endl;

    cout<< g.edges[4].u;

    for(int i=0; i<=g.E+500;i++)
    {
        g.edges[i].u=0;
        g.edges[i].v =0;
    }

    g.DFS(g); 


    return 0;
 }

Answer 1

因为你用整数索引顶点，你可以做的简单技巧是添加边 {v, u} 当且仅当 v <= u （如果没有自循环那么 v < u足够了）。为此，只需更改：

if(!visited[*j])
{
    cout<<endl<<v<<" "<<*j<<endl;// print edges
    g.addEdgeList(g,v,*j);
    dfsUtil(g, *j, visited);
}

至

if(!visited[*j])
{
    cout<<endl<<v<<" "<<*j<<endl;// print edges
    if(v <= *j)
    {
        g.addEdgeList(g,v,*j);
    }
    dfsUtil(g, *j, visited);
}

Answer 2

因为我认为问题出在 ischeckEdge 中。它正在将 (0,0) 作为边进行比较，因为在输入中没有顶点 '0'，

bool Graph::ischeckEdge(Graph g, int u, int v)
{
    bool a = false;

    swap(u,v);

    for(int i=0;i<=e; i++)
    {

        if(i == 0)
        {
            continue;
        }
        if(i ==1 && g.edges[i].u ==0 && g.edges[i].v ==0)
        {
            return true;
        }

        if(g.edges[i].u == u && g.edges[i].v ==v )
        {
            //cout<<"Same Edge"<<endl;
            a= false;
            break;
        }
        else 
        {
            //cout<<"Edge count : "<<e<<endl;
            //cout<<"Iteration : "<<i<<endl;
            //cout<<"edge u v : "<<g.edges[i].u<<" "<<g.edges[i].v<<endl;
            //cout<<"input u v : "<<u<<" "<<v<<endl;
            a= true;
        }
    }
    return a;
}

使用 DFS C++ 实现从邻接列表到边列表的图

Implement a graph from adjacency list to Edge list using DFS C++

c++

algorithm

graph

adjacency-list