用STL实现编程竞赛的未加权和无向DFS

在本文中,将使用基于STL的不同表示形式,这有助于使用向量快速实现图形。该实现用于图形的邻接表表示。

下面是一个有5个顶点的无向图和无权图的例子。

下面是该图的邻接列表表示。

我们在STL中使用vector来实现使用邻接表表示的图形。

vector:序列容器。在这里,我们使用它来存储所有顶点的邻接列表。我们使用顶点数作为该向量的索引。

想法是将图表示为向量数组,以使每个向量都表示顶点的邻接表。 以下是用于DFS遍历的完整的基于STL的C ++程序。

// A simple representation of graph using STL, 
// for the purpose of competitive programming 
#include<bits/stdc++.h> 
using namespace std; 
  
// A utility function to add an edge in an 
// undirected graph. 
void addEdge(vector<int> adj[], int u, int v) 
{ 
    adj[u].push_back(v); 
    adj[v].push_back(u); 
} 
  
// A utility function to do DFS of graph 
// recursively from a given vertex u. 
void DFSUtil(int u, vector<int> adj[], 
                    vector<bool> &visited) 
{ 
    visited[u] = true; 
    cout << u << " "; 
    for (int i=0; i<adj[u].size(); i++) 
        if (visited[adj[u][i]] == false) 
            DFSUtil(adj[u][i], adj, visited); 
} 
  
// This function does DFSUtil() for all  
// unvisited vertices. 
void DFS(vector<int> adj[], int V) 
{ 
    vector<bool> visited(V, false); 
    for (int u=0; u<V; u++) 
        if (visited[u] == false) 
            DFSUtil(u, adj, visited); 
} 
  
// Driver code 
int main() 
{ 
    int V = 5; 
  
    // The below line may not work on all 
    // compilers.  If it does not work on 
    // your compiler, please replace it with 
    // following 
    // vector<int> *adj = new vector<int>[V]; 
    vector<int> adj[V]; 
  
    // Vertex numbers should be from 0 to 4. 
    addEdge(adj, 0, 1); 
    addEdge(adj, 0, 4); 
    addEdge(adj, 1, 2); 
    addEdge(adj, 1, 3); 
    addEdge(adj, 1, 4); 
    addEdge(adj, 2, 3); 
    addEdge(adj, 3, 4); 
    DFS(adj, V); 
    return 0; 
} 

输出:

0 1 2 3 4

六一编程网

发表评论

Next Post

如何创建你的第一个Python应用程序

周六 2月 29 , 2020
现在是创建第一个Python应用程序的时候了。初始的Python Shell窗口不适用于创建应用程序 […]