I wrote code to implement graph's ADT with adjacent matrix. Then I want to build a project and desperate code.
#include<iostream>
#include<iomanip>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e3+10;
class Graph{
private:
int vertex;
int side;
int is_vis[maxn];
int degree[maxn];
int Edges[maxn][maxn];
public:
Graph(){
vertex=0;
memset(Edges,0x3f,sizeof Edges);
memset(is_vis,0,sizeof is_vis);
memset(degree,0,sizeof degree);
}
void Clear(){
vertex=0;
memset(Edges,0x3f,sizeof Edges);
memset(is_vis,0,sizeof is_vis);
memset(degree,0,sizeof degree);
}
void Clear_Vis(){memset(is_vis,0,sizeof is_vis);}
void PreVisit(int v){cout<<v<<" ";}
void SetMark(int u,int vis){is_vis[u]=vis;}
void Set_vertex(int n){vertex=n;} //顶点数
int Get_vertex(){return vertex;}
int Get_side() {return side;} //边数
void Add_edge(int u,int v,int val){ //加边
if(Edges[u][v]==INF){
side++;
degree[u]++;degree[v]++;
}
Edges[u][v]=Edges[v][u]=val;
}
void Cancle_edge(int u,int v){ //删边
if(Edges[u][v]!=INF){
side--;
degree[u]--;degree[v]--;
}
Edges[u][v]=Edges[v][u]=INF;
}
bool Have_edge(int u,int v){ //判断边是否存在
return Edges[u][v]==INF?0:1;
}
int Get_degree(int u){ //返回顶点u的度数
return degree[u];
}
void The_edge_node(int u){ //与顶点u相邻的点
int flag=1;
for(int i=0;i<vertex;i++){
if(i!=u&&Edges[u][i]!=INF){
cout<<i<<" ";flag=0;
}
}
if(flag)cout<<"No node next to "<<u<<".";
cout<<endl;
}
void DFS(int u){ //深度优先遍历
if(is_vis[u])return;
PreVisit(u);
SetMark(u,1);
for(int i=0;i<vertex;i++){
if(i==u||Edges[u][i]==INF||is_vis[i])continue;
DFS(i);
}
}
void BFS(int u){ //宽度优先遍历
memset(is_vis,0,sizeof is_vis);
queue<int>Q;
Q.push(u);
is_vis[u]=1;
while(!Q.empty()){
int out=Q.front();Q.pop();
cout<<out<<" ";
for(int i=0;i<vertex;i++){
if(i==out||Edges[out][i]==INF||is_vis[i])continue;
is_vis[i]=1;
Q.push(i);
}
}
}
void prt_Gra(){ //打印邻接矩阵
cout<<" ";
for(int i=0;i<vertex;i++){
cout<<" "<<left<<setw(3)<<i;
}
cout<<endl;
for(int i=0;i<vertex;i++){
cout<<" ";
for(int j=0;j<vertex*4;j++)cout<<"-";cout<<"-"<<endl;
cout<<left<<setw(2)<<i;
for(int j=0;j<vertex;j++){
cout<<"|";
if(i==j)cout<<left<<setw(3)<<0;
else if(Edges[i][j]==INF)cout<<left<<setw(3)<<'-';
else cout<<left<<setw(3)<<Edges[i][j];
}
cout<<"|"<<endl;
}
cout<<" ";
for(int j=0;j<vertex*4;j++)cout<<"-";cout<<"-"<<endl;
}
}My_graph;
void Get_menus(){
cout<<"1.新建一个图。"<<endl;
cout<<"2.增加一条边。"<<endl;
cout<<"3.删除一条边。"<<endl;
cout<<"4.判断边是否存在。"<<endl;
cout<<"5.查询顶点的度数。"<<endl;
cout<<"6.输出图的邻接矩阵。"<<endl;
cout<<"7.查询与顶点相邻的点。"<<endl;
cout<<"8.对图进行深度优先遍历。"<<endl;
cout<<"9.对图进行宽度优先遍历。"<<endl;
}
int main(){
My_graph.Clear();
int cmd,n,m,u,from,to,dist;
Get_menus();
while(1){
cout<<"请输入对应操作的序号:";cin>>cmd;cout<<endl;
if(cmd==1){
My_graph.Clear();
cout<<"请输入图的顶点数:";cin>>n;
My_graph.Set_vertex(n);cout<<endl;
cout<<"请输入图的边数:";cin>>m;cout<<endl;
cout<<"请依次输入各边的端点与长度:"<<endl;
for(int i=0;i<m;i++){
cin>>from>>to>>dist;
My_graph.Add_edge(from,to,dist);
}
cout<<"图的初始化完成!"<<endl;
}
if(cmd==2){
cout<<"请输入新增边的端点与长度:"<<endl;
cin>>from>>to>>dist;
My_graph.Add_edge(from,to,dist);
cout<<"加边完成!"<<endl;
}
if(cmd==3){
cout<<"请输入边的两个端点:";
cin>>from>>to;
My_graph.Cancle_edge(from,to);
cout<<"删边完成!"<<endl;
}
if(cmd==4){
cout<<"请输入边的两个端点:";
cin>>from>>to;
if(My_graph.Have_edge(from,to))cout<<"该边存在!"<<endl;
else cout<<"该边不存在!"<<endl;
}
if(cmd==5){
cout<<"请输入需要查询度数的顶点:";
cin>>u;cout<<endl;
cout<<"顶点"<<u<<"的度数为:"<<My_graph.Get_degree(u)<<endl;
}
if(cmd==6){
cout<<"图的邻接矩阵为:"<<endl;
My_graph.prt_Gra();
}
if(cmd==7){
cout<<"请输入需要查询相邻点的顶点:";
cin>>u;cout<<endl;
cout<<"与顶点"<<u<<"相邻的点有:"<<endl;
My_graph.The_edge_node(u);
}
if(cmd==8){
My_graph.Clear_Vis();
cout<<"请输入起点:";
cin>>u;cout<<endl;
cout<<"深度优先遍历的结果为:"<<endl;
My_graph.DFS(u);cout<<endl;
}
if(cmd==9){
cout<<"请输入起点:";
cin>>u;cout<<endl;
cout<<"宽度优先遍历的结果为:"<<endl;
My_graph.BFS(u);cout<<endl;
}
}
return 0;
}
/*
6 9
0 1 10
0 3 20
0 5 3
1 2 3
1 3 5
3 4 11
2 4 15
3 5 10
4 5 3
*/
But when I run the code, CodeBlocks says ''multiple definition of My_graph'
.
Then I choose to define Graph's object in main()
instead of in Graph.h
. But this time the exe will exit before execute main()
.
Process returned -1073741571 (0xC00000FD)
This is main()
code
I want to figure out what happened in constructor.
Even if you are not allocating your data on the stack, you won't be able to execute your code. This is the amount of data you want to allocate:
const int maxn=1e3+10;
int is_vis[maxn];
int degree[maxn];
int Edges[maxn][maxn];
I don't think your computer has enough space.
Use vectors, and resize the edges matrix ont he fly (do you need a matrix anyway? Probably not)
std::vector<int> is_vis;
std::vector<int> degree;
std::vector<std::vector<int>> Edges; // Change this to something sensible, perhaps a list of connections?
This is only for one error message "multiple definition...". For the other error see @MatthieuBrucher answer.
class Graph{
....
} My_graph;
This declares an instance global object of type Graph
called My_graph
.
Once you have this instance you can not declare it again:
Graph My_graph; //ERROR
This re-declaration may come not only in some function ('main' is a function) , but also from including the same .h header several times without include-guards.
User contributions licensed under CC BY-SA 3.0