• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Graph arsovski  Jan 21st, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include<iostream>
2. #include<vector>
3. #include<list>
4. #include <queue>
5. // INPUTS:
6. //    7
7. //    8
8. //
9. //    0 1 1
10. //    1 1 2
11. //    0 1 2
12. //    1 1 3
13. //    2 1 4
14. //    3 1 4
15. //    4 1 5
16. //    5 1 6
17.
18. struct Vertex
19. {
20.     int weight;
21.     int vertex_number;
22.
23.     Vertex(int weight, int vertex_number)
24.     {
25.         this->weight = weight;
26.         this->vertex_number = vertex_number;
27.     }
28. };
29.
30.
31. //undirected weight graph
32. std::vector<std::list<Vertex>> graph;
33.
34. //TODO make bfs and dfs
35.
36. bool connection_exists(int from, int to)
37. {
38.     for (auto element : graph[from])
39.     {
40.         if (element.vertex_number == to)
41.         {
42.             return true;
43.         }
44.     }
45.
46.     return false;
47. }
48.
49. void add_connection(int from, int weight, int to)
50. {
51.     if (!connection_exists(from, to))
52.     {
53.         graph[from].push_back({weight, to});
54.         graph[to].push_back({weight, from});
55.     }
56. }
57.
58. void print_graph()
59. {
60.     for (int i = 0; i < graph.size(); i++)
61.     {
62.         std::cout << "Vertex " << i << ": ";
63.
64.         for (auto element : graph[i])
65.         {
66.             std::cout << element.vertex_number << "->" << element.weight << " ";
67.         }
68.
69.         std::cout << std::endl;
70.     }
71. }
72.
73.
74. std::vector<bool> visited;
75.
76. void bfs(int from)
77. {
78.     std::queue<int> next_to_process;
79.     next_to_process.push(from);
80.
81.     while (!next_to_process.empty())
82.     {
83.         int next_index = next_to_process.front();
84.         next_to_process.pop();
85.         visited[next_index] = true;
86.
87.         std::cout << next_index << " ";
88.
89.         for (auto neighbor : graph[next_index])
90.         {
91.             if (!visited[neighbor.vertex_number])
92.             {
93.                 visited[neighbor.vertex_number] = true;
94.                 next_to_process.push(neighbor.vertex_number);
95.             }
96.         }
97.     }
98.
99.     std::cout << std::endl;
100. }
101.
102.
103. std::vector<bool> visited_dfs;
104.
105. void dfs(int from)
106. {
107.     std::cout << from << " ";
108.     visited_dfs[from] = true;
109.
110.     for (auto neighbor : graph[from])
111.     {
112.         if (!visited_dfs[neighbor.vertex_number])
113.         {
114.             visited_dfs[neighbor.vertex_number] = true;
115.             dfs(neighbor.vertex_number);
116.         }
117.     }
118. }
119.
120. std::vector<bool> visited_topo;
121. std::list<int>  ordered_nodes;
122.
123. //DFS na svi nodes
124. void _recursive_topological(int from)
125. {
126.     visited_topo[from] = true;
127.
128.     //go through neighbors
129.     for(auto element: graph[from])
130.     {
131.         if(!visited_topo[element.vertex_number])
132.         {
133.             visited_topo[element.vertex_number] = true;
134.             _recursive_topological(element.vertex_number);
135.         }
136.     }
137.
138.
139.     ordered_nodes.push_back(from);
140.
141.
142. }
143.
144. void topological_sort()
145. {
146.     for(int i=0; i < graph.size();i++)
147.     {
148.         if(!visited_topo[i])
149.             _recursive_topological(i);
150.     }
151.
152.     ordered_nodes.reverse();
153.
154.     for(auto element : ordered_nodes)
155.     {
156.         std::cout << element << " ";
157.     }
158.
159.     std::cout << std::endl;
160.
161. }
162.
163.
164. int main()
165. {
166.     int nodes, edges;
167.     std::cin >> nodes >> edges;
168.
169.     graph.resize(nodes);
170.     visited_dfs.resize(nodes, false);
171.     visited.resize(nodes, false);
172.     visited_topo.resize(nodes, false);
173.     for (int i = 0; i < edges; i++)
174.     {
175.         int from, weight, to;
176.         std::cin >> from >> weight >> to;
178.     }
179.
180.
181.     //print_graph();
182.
183.     //dfs(6);
184.     std::cout << std::endl;
185.
186.     //bfs(6);
187.
188.     //TODO topological sort
189.
190.     topological_sort();
191.
192.     return 0;
193. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top