簡単な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.