A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d8/db9/topological__sort_8cpp_source.html below:

TheAlgorithms/C++: graph/topological_sort.cpp Source File

Go to the documentation of this file. 41

std::vector<std::vector<int>> adj;

48 Graph

(

int

nodes) : n(nodes), adj(nodes) {}

55 void addEdge

(

int

u,

int

v) { adj[u].push_back(v); }

79void dfs

(

int

v, std::vector<int>& visited,

80 const

std::vector<std::vector<int>>&

graph

, std::stack<int>& s) {

82 for

(

int

neighbour :

graph

[v]) {

83 if

(!visited[neighbour]) {

96 int

n = g.getNumNodes();

97 const auto

& adj = g.getAdjacencyList();

98

std::vector<int> visited(n, 0);

101 for

(

int

i = 0; i < n; i++) {

103 dfs

(i, visited, adj, s);

107

std::vector<int> ans;

114 if

(ans.size() < n) {

115 throw

std::invalid_argument(

"cycle detected in graph"

);

128

std::cout <<

"Testing for graph 1\n"

;

138

std::vector<int> expected_1 = {5, 4, 2, 3, 1, 0};

139

std::cout <<

"Topological Sorting Order: "

;

140 for

(

int

i : ans_1) {

141

std::cout << i <<

" "

;

144

assert(ans_1 == expected_1);

145

std::cout <<

"Test Passed\n\n"

;

148

std::cout <<

"Testing for graph 2\n"

;

158

std::vector<int> expected_2 = {0, 1, 2, 4, 3};

159

std::cout <<

"Topological Sorting Order: "

;

160 for

(

int

i : ans_2) {

161

std::cout << i <<

" "

;

164

assert(ans_2 == expected_2);

165

std::cout <<

"Test Passed\n\n"

;

168

std::cout <<

"Testing for graph 3\n"

;

176

}

catch

(std::invalid_argument& err) {

177

assert(std::string(err.what()) ==

"cycle detected in graph"

);

179

std::cout <<

"Test Passed\n"

;

Class that represents a directed graph and provides methods for manipulating the graph.

void addEdge(int u, int v)

Function that adds an edge between two nodes or vertices of graph.

const std::vector< std::vector< int > > & getAdjacencyList() const

Get the adjacency list of the graph.

Graph(int nodes)

Constructor for the Graph class.

int getNumNodes() const

Get the number of nodes in the graph.

Topological Sort Algorithm.

std::vector< int > topologicalSort(const Graph &g)

Function to get the topological sort of the graph.

static void test()

Self-test implementation.

void dfs(int v, std::vector< int > &visited, const std::vector< std::vector< int > > &graph, std::stack< int > &s)

Function to perform Depth First Search on the graph.

int main()

Main function.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4