图的基础操作在前两篇文章中，这里分享图的应用：深度优先和广度优先

连通图：

//其他定义见之前内容template <typename Graph>class Component{private: Graph &G; bool *visited; //是否访问 int ccount; //记录有多少条互不连通的路径 int *id; //记录节点在哪条路径中 void dfs( int v ){ //深度优先遍历 visited[v] = true; id[v] = ccount; typename Graph::adjIterator adj(G, v); for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){ if( !visited[i] ) dfs(i); } }public: Component(Graph &graph): G(graph){ visited = new bool[G.V()]; id = new int[G.V()]; ccount = 0; for( int i = 0 ; i < G.V() ; i ++ ){ //初始化 visited[i] = false; id[i] = -1; } for( int i = 0 ; i < G.V() ; i ++ ) //遍历图中每个点 if( !visited[i] ){ dfs(i); ccount ++; //有新的未连通路径 } } ~Component(){ delete[] visited; delete[] id; } int count(){ return ccount; } bool isConnected( int v , int w ){ assert( v >= 0 && v < G.V() ); assert( w >= 0 && w < G.V() ); return id[v] == id[w]; //两点是否在同一路径中 }};

寻路：

template <typename Graph>class Path{private: Graph &G; int s; //节点 bool* visited; int * from; //之前节点 void dfs( int v ){ visited[v] = true; typename Graph::adjIterator adj(G, v); for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){ if( !visited[i] ){ from[i] = v; //记录 dfs(i); } } }public: Path(Graph &graph, int s):G(graph){ // 算法初始化 assert( s >= 0 && s < G.V() ); visited = new bool[G.V()]; from = new int[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ visited[i] = false; from[i] = -1; } this->s = s; // 寻路算法 dfs(s); } ~Path(){ delete [] visited; delete [] from; } bool hasPath(int w){ //不越界判断 assert( w >= 0 && w < G.V() ); return visited[w]; } void path(int w, vector<int> &vec){ //路径存到vec向量中，利用栈取回 stack<int> s; int p = w; while( p != -1 ){ s.push(p); p = from[p]; } vec.clear(); while( !s.empty() ){ vec.push_back( s.top() ); //存入了正向的路径 s.pop(); } } void showPath(int w){ vector<int> vec; path( w , vec ); for( int i = 0 ; i < vec.size() ; i ++ ){ cout<<vec[i]; if( i == vec.size() - 1 ) cout<<endl; else cout<<" -> "; } }};

最短路径：广度优先求无权图最短路径

template <typename Graph>class ShortestPath{private: Graph &G; int s; bool *visited; int *from; int *ord; //记录s到每个节点的最短距离public: ShortestPath(Graph &graph, int s):G(graph){ // 算法初始化 assert( s >= 0 && s < graph.V() ); visited = new bool[graph.V()]; from = new int[graph.V()]; ord = new int[graph.V()]; for( int i = 0 ; i < graph.V() ; i ++ ){ visited[i] = false; from[i] = -1; ord[i] = -1; } this->s = s; queue<int> q; //广度优先利用队列 // 无向图最短路径算法 q.push( s ); visited[s] = true; ord[s] = 0; while( !q.empty() ){ int v = q.front(); q.pop(); typename Graph::adjIterator adj(G, v); for( int i = adj.begin() ; !adj.end() ; i = adj.next() ) if( !visited[i] ){ q.push(i); visited[i] = true; from[i] = v; ord[i] = ord[v] + 1; } } } ~ShortestPath(){ delete [] visited; delete [] from; delete [] ord; } bool hasPath(int w){ assert( w >= 0 && w < G.V() ); return visited[w]; } void path(int w, vector<int> &vec){ assert( w >= 0 && w < G.V() ); stack<int> s; int p = w; while( p != -1 ){ s.push(p); p = from[p]; } vec.clear(); while( !s.empty() ){ vec.push_back( s.top() ); s.pop(); } } void showPath(int w){ assert( w >= 0 && w < G.V() ); vector<int> vec; path(w, vec); for( int i = 0 ; i < vec.size() ; i ++ ){ cout<<vec[i]; if( i == vec.size()-1 ) cout<<endl; else cout<<" -> "; } } int length(int w){ assert( w >= 0 && w < G.V() ); return ord[w]; }};

测试用例：

int main() { string filename = "testG2.txt"; SparseGraph g = SparseGraph(7, false); ReadGraph<SparseGraph> readGraph(g, filename); g.show(); cout<<endl;// Path<SparseGraph> dfs(g,0); cout<<"DFS : "; dfs.showPath(6);// ShortestPath<SparseGraph> bfs(g,0); cout<<"BFS : "; bfs.showPath(6); return 0;}