Каково максимальное количество ребер E в орграфе с V вершинами и без параллельных ребер?
Вероятно, E=V; Но возможны петли.
Нарисовать по аналогии для входного потока
Пример того как должно получиться
|
1 2 3 4 5 6 7 8 9 10 |
0 -> 6,5 2 -> 0 3 -> 10,6 4 -> 1 5 -> 10 6 ->2 7 ->8,11 8 -> 4,1 10 -> 3 11 -> 8 |
Написать конструктор копирования для класса Digraph, который принимает в качестве аргумента граф G
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
/** * Initializes a new digraph that is a deep copy of the specified digraph. * * @param G the digraph to copy */ public Digraph(Digraph G) { this.V= (G.GetVertices()); this.E = G.GetEdges(); for (int v = 0; v < V; v++) this.indegree[v] = G.GetInDegree(v); for (int v = 0; v < G.GetVertices(); v++) { // reverse so that adjacency list is in same order as original Stack<int> reverse = new Stack<int>(); foreach (int w in G.adj[v]) { reverse.Push(w); } foreach (int w in reverse) { adj[v].Push(w); } } } |
|
1 |
Создать метод IsEdge(v,w)
|
1 2 3 4 5 6 |
public bool IsEdge(int v,int w) { foreach (int x in adj[v]) if (x == w) return true; return false; } |
Проверка
|
1 2 3 |
// isEdge Console.WriteLine("Is Edge ? 0,12 "+G.IsEdge(0,12)); Console.WriteLine("Is Edge ? 0,5 " + G.IsEdge(0, 5)); |
Добавить в конструктор проверку на параллельные ребра и петли
|
1 2 3 4 5 |
if (!IsAllowParallelEdgesAndLoops) { if ((IsEdge(v, w)) || (v == w)) {/*do smth*/} AddEdge(v, w); } |
Добавить в класс Digraph определение стоков, источников, отображения
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// sources, with indegree=0 public IEnumerable<int> Sources() { Stack<int> sources = new Stack<int>(); for(int v=0;v<V;v++) { if (GetInDegree(v) == 0) sources.Push(v); } return sources; } // sinks, with outdegree=0 public IEnumerable<int> Sinks() { Stack<int> sinks = new Stack<int>(); for (int v = 0; v < V; v++) { if (GetOutDegree(v) == 0) sinks.Push(v); } return sinks; } // isMap public bool IsMap() { for (int v = 0; v < V; v++) { if (GetOutDegree(v) != 0) { return false; } } return true; } |
Является ли заданная перестановка вершин ОАГ топологическим порядком ?
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public bool IsOrderIsTopologicalOrder(Digraph G, Stack<int> SomeOrder) { DigraphTopological2 o = new DigraphTopological2(G); Stack<int> topologicalOrder = new Stack<int>(o.Order); for (int i = 0; i < G.GetVertices(); i++) { int v = SomeOrder.Pop(); int w = topologicalOrder.Pop(); if (v != w) return false; } return true; } |