There is an algorithm implementation using DFS: rain.ifmo.ru/cat/view.php/vis...2007/algorithm

C++Code

The procedure returns true if the graph was topologically sorted, otherwise false is returned.

Color — the array which stores vertex colors (0 — white, 1 — grey, 2 — black).

N is the number of vertices.

Edges — array of lists of adjacent vertices.

Numbers — the array in which to store new number of peaks.

Stack — the stack where the stack tops after processing.

Cycle — true if the graph was found cycle.

Description:

3-6. Is called a DFS from all nodes. Finish the algorithm, if the detected cycle.

7-9. A recorded array of new vertex.

13-14. If the node is grey, then we found a cycle. Finish the search depth.

14. If the vertex is black, then finish processing.

15. Paint the vertex gray.

16-18. Treated a list of adjacent vertices.

19. Put the top on the stack.

20. Color the vertex black.

Can't understand how it all works, and how to apply this sort to an oriented graph defined by the adjacency matrix and return the result of sorting? Can someone show on a real example?

C++Code

```
boolean topological_sort(){
boolean Cycle;
for(int i = 1;i <= N;i ++){
Cycle = dfs(i);
if(Cycle)return false;
}
for(int i = 1;i <= n;i ++){
Numbers[Stack.pop()] = i;
}
return true;
}
boolean dfs(int v){
if(Color[v] == 1)return true;
if(Color[v] == 2)return false;
Color[v] = 1;
for(int i = 0;i < Edges[v].size();i ++){
if(dfs(Edges[v].get(i)))return true;
}
Stack.push(v);
Color[v] = 2;
return false;
}
```

The procedure returns true if the graph was topologically sorted, otherwise false is returned.

Color — the array which stores vertex colors (0 — white, 1 — grey, 2 — black).

N is the number of vertices.

Edges — array of lists of adjacent vertices.

Numbers — the array in which to store new number of peaks.

Stack — the stack where the stack tops after processing.

Cycle — true if the graph was found cycle.

Description:

3-6. Is called a DFS from all nodes. Finish the algorithm, if the detected cycle.

7-9. A recorded array of new vertex.

13-14. If the node is grey, then we found a cycle. Finish the search depth.

14. If the vertex is black, then finish processing.

15. Paint the vertex gray.

16-18. Treated a list of adjacent vertices.

19. Put the top on the stack.

20. Color the vertex black.

Can't understand how it all works, and how to apply this sort to an oriented graph defined by the adjacency matrix and return the result of sorting? Can someone show on a real example?

asked September 19th 19 at 00:08

2 answers

answered on

Solution

Need to be rewritten for the adjacency matrix of this code section.

Something like this.

I also do not like the constants 0, 1 and 2. To declare them as

Or WHITE, GRAY and BLACK, if you want — in textbooks on algorithms they are painted in three colors.

```
for(int i = 0;i < Edges[v].size();i ++){
if(dfs(Edges[v].get(i)))return true;
}
```

Something like this.

```
loop (i : all vertices)
if matricies[v, i]
if dfs(i)
return true;
```

I also do not like the constants 0, 1 and 2. To declare them as

```
UNVISITED = 0;
PARTLY_VISITED = 1;
VISITED = 2;
```

Or WHITE, GRAY and BLACK, if you want — in textbooks on algorithms they are painted in three colors.

answered on September 19th 19 at 00:12

To begin with, to explain himself

1. What is the count?

2. What is directed graph?

3. What is the adjacency matrix of a graph?

4. What is the adjacency matrix of the directed graph have?

5. What is topological sort?

1. What is the count?

2. What is directed graph?

3. What is the adjacency matrix of a graph?

4. What is the adjacency matrix of the directed graph have?

5. What is topological sort?

Find more questions by tags AlgorithmsProgrammingC++Graphs