読者です 読者をやめる 読者になる 読者になる

簡単なgraphの実装

頂点とそれと接続する頂点の情報をもつグラフ表現を書いた
なんとなくprintメソッドが欲しくて書くけど,getメソッドを作ったほうがいいんだろうか

#include <iostream>
#include <vector>

using namespace std;

/*
 * グラフの表現
 */
class graph{
private:
	struct vertex{
		int id;
		vector <vertex*> edge;
	};
public:
	vertex *G;
	int graph_size;
	graph(int size){
		G = new vertex[size];
		graph_size = size;
		for(int i=0; i<size; i++){
			G[i].id = i;
		}
	}

	void append(int target_id, int insert_id){
		// if( find(G[target_id].edge->begin(),G[target_id].edge->end(),&G[insert_id])!=G[target_id].edge->end() ){
		// 	G[target_id].edge->push_back(&G[insert_id]);
		// }
		for(int i=0; i<G[target_id].edge.size(); i++){
			if(G[target_id].edge[i]->id == insert_id) return;
		}
		G[target_id].edge.push_back(&G[insert_id]);

	}

	void print(){
		for(int i=0; i<graph_size; i++){
			cout << "vertex: " << G[i].id << endl << "edge: ";
			for(int j=0; j<G[i].edge.size(); j++){
				cout <<  G[i].edge[j]->id << " ";
			}
			if(G[i].edge.size()==0) cout << "nothing.";
			cout << endl;
		}
	}

};

int main(void){
	int n; cin >> n;
	graph g(n);
	for(int i=0; i<n; i++){
		int id; cin >> id;
		int m; cin >> m;
		for(int j=0; j<m; j++){
			int temp; cin >> temp;
			g.append(id,temp);
		}
	}
	g.print();
	return 0;
}

/*
sample input
5
0 4 1 2 3 4
1 0
2 2 3 4
3 0
4 0


*/

出力結果

vertex: 0
edge: 1 2 3 4 
vertex: 1
edge: nothing.
vertex: 2
edge: 3 4 
vertex: 3
edge: nothing.
vertex: 4
edge: nothing.