我有一个包含无向图邻接表的文本文件，例子:
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
3
边缘2 3插入
背部:31 1
边缘1插入
背部:3 2
3
边缘3 4插入
背面:4 2
边缘4 2插入
背面:4 3
边缘4 3插入
背面:2 4
边缘2 4插入
背部: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;
}
因为你用整数索引顶点，你可以做的简单技巧是添加边{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);
}
因为我认为问题是在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;
}