学习：图的存储（领接表和领接矩阵）

青旅半醒 2023-03-13 06:37 77阅读 0赞

## 学习：图的存储（领接表和领接矩阵） ##

#include <iostream>
    #include <cassert> 
    #include <ctime>
    #include <cstdlib>
    #include <vector>
    using namespace std;
    
    //稀疏图 - 领接表
    class SparseGraph
    { 
    private:
    	int n,m;//顶点个数、边的2
    	bool directed;//是否为有向图
    	vector<vector<int> > g;
    public:
    	SparseGraph(int n, bool directed)
    	{ 
    		this->n = n;
    		this->m = 0;
    		this->directed = directed;
    		for(int i=0; i<n; i++)
    			g.push_back(vector<int>());	
    	} 
    	~SparseGraph(){ 
    	}
    	int V() const
    	{ 
    		return n;
    	}
    	int E() const
    	{ 
    		return m;
    	}
    	void addEdge(int v, int w)//在顶点v和顶点w之间加入一条边 
    	{ 
    		assert(v>=0 && v<n); 
    		assert(w>=0 && w<n);
    		
    		if(hasEdge(v,w) || v==w)//去除自环边和平行边 
    			return;
    		
    		g[v].push_back(w);
    		if( !directed )
    			g[w].push_back(v);
    		m++;
    	}
    	
    	bool hasEdge(int v, int w)//判断顶点v和顶点w之间是否已经有边 
    	{ 
    		assert(v>=0 && v<n); 
    		assert(w>=0 && w<n);
    		for(int i=0; i<g[v].size(); i++)
    			if(g[v][i] == w)
    				return true;
    		return false;
    	}
    	
    	void print() const
    	{ 
    		for(int i=0; i<g.size(); i++)
    		{ 
    			cout<<i<<": ";
    			for(int j=0; j<g[i].size(); j++)
    			{ 
    				cout<<g[i][j]<<" ";
    			}
    			cout<<endl;
    		}
    	}
    };
    
    //稠密图 - 领接表 
    class DenseGraph
    { 
    private: 
    	int n,m;
    	bool directed;
    	vector<vector<bool> > g;
    public:
    	DenseGraph(int n, bool directed)
    	{ 
    		this->n = n;
    		this->m = 0;
    		this->directed = directed;
    		for(int i=0; i<n; i++)
    			g.push_back(vector<bool>(n, false));
    	}
    	~DenseGraph(){ 
    	}
    	int V() const
    	{ 
    		return n;
    	}
    	int E() const
    	{ 
    		return m;
    	}
    	void addEdge(int v, int w)
    	{ 
    		assert(v>=0 && v<n);
    		assert(w>=0 && w<n);
    		
    		if( v==w || hasEdge(v,w) )
    			return;
    		
    		g[v][w]=true;
    		if( !directed )
    			g[w][v]=true;
    		m++;
    	}
    	bool hasEdge(int v, int w)
    	{ 
    		assert(v>=0 && v<n);
    		assert(w>=0 && w<n);
    		return g[v][w];	
    	}
    	void print() const
    	{ 
    		for(int i=0; i<g.size(); i++)
    		{ 
    			cout<<i<<": ";
    			for(int j=0; j<g[i].size(); j++)
    			{ 
    				cout<<g[i][j]<<" ";
    			}
    			cout<<endl;
    		}
    	}
    };
    
    int main()
    { 
    	SparseGraph g1(5,false);
    	int m;
    	srand(time(NULL));
    	cout<<"领接表:"<<endl; 
    	for(int i=0; i<5; i++)
    	{ 
    		m=rand()%5;
    		for(int j=0; j<m; j++)
    			g1.addEdge(i,j);
    	}
    	g1.print();
    	
    	DenseGraph g2(5,false);
    	cout<<"领接矩阵:"<<endl; 
    	for(int i=0; i<5; i++)
    	{ 
    		m=rand()%5;
    		for(int j=0; j<m; j++)
    			g2.addEdge(i,j);
    	}
    	g2.print();
    	return 0;
    }