ргр по алгоритмам и структурам данных. АиСД РГР, ключников. Разработка атд Простой граф

• Название: Разработка атд Простой граф
• Анкор: ргр по алгоритмам и структурам данных
• Дата: 20.12.2022
• Размер: 135.4 Kb.
• Имя файла: АиСД РГР, ключников.docx
• Тип: Документы; #854773
• страница: 12 из 12

Graph.cs

using System;

using System.Collections.Generic;
namespace АиСД_РГР

{

class Graph // простой граф - реальный класс

{

public AbstractGraph G;

public Graph()

{

G = new LGraph();

}
public Graph(int V, bool D, bool F)

{

G = AbstractGraph.MakeGraph(V, D, F);

}
public Graph(int V, int E, bool D, bool F)

{

G = AbstractGraph.MakeGraph(V, E, D, F);

}
public Edge GetEdge(Vertex v1, Vertex v2)

{

if (G.Type == true)

{

int i, j;

for (i = 0; i < G.Vertexes.Count; i++)

{

if (G.Vertexes[i].Index == v1.Index)

break;

}
for (j = 0; j < G.Vertexes.Count; j++)

{

if (G.Vertexes[j].Index == v2.Index)

break;

}
if (i >= G.Vertexes.Count || j >= G.Vertexes.Count)

return null;
return G.Matrix[i, j];

}

else

{

for (int i = 0; i < G.Vertexes.Count; i++)

{

if (G.Adj[i].AdjIndex == v1.Index)

{

for (var q = G.Adj[i].Head; q != null; q = q.Next)

{

if (q == null)

return null;

if (q.AdjEdge.Vertex1.Index == v1.Index && q.AdjEdge.Vertex2.Index == v2.Index)

return q.AdjEdge;

if (q.AdjEdge.Vertex1.Index == v2.Index && q.AdjEdge.Vertex2.Index == v1.Index)

return q.AdjEdge;

}

}

}

return null;

}

}
public bool Dense()

{

return G.Type;

}
public void Reverse()

{

// var g = G;

if (G.Type == true)//если M, то в L

{

var NewGraph = AbstractGraph.MakeGraph(0, 0, G.Oriented, false);

NewGraph.Vertexes = G.Vertexes;

NewGraph.Type = G.Type;

NewGraph.Oriented = G.Oriented;

NewGraph.Weighted = G.Weighted;

NewGraph.CurrentIndex = G.CurrentIndex;

NewGraph.EdgesCount = G.EdgesCount;

NewGraph.Adj = G.Adj;

NewGraph.Matrix = G.Matrix;
NewGraph.Adj = new List>();

for (int i = 0; i < NewGraph.Vertexes.Count; i++)//пополняем вектор смежности

{

NewGraph.Adj.Add(new AdjacencyList());

NewGraph.Adj[i].AdjIndex = NewGraph.Vertexes[i].Index;

}
for (int i = 0; i < NewGraph.Vertexes.Count; i++)

{

for (int j = 0; j < NewGraph.Vertexes.Count; j++)

{

if (NewGraph.Matrix[i, j] != null)

{

NewGraph.Adj[i].AddNode(NewGraph.Matrix[i, j]);

}

}

}
G = NewGraph;

G.Type = false;

G.Matrix = null;

// g = null;

}
else//из L в M

{

var NewGraph = AbstractGraph.MakeGraph(0, 0, G.Oriented, true);
NewGraph.Vertexes = G.Vertexes;

NewGraph.Type = G.Type;

NewGraph.Oriented = G.Oriented;

NewGraph.Weighted = G.Weighted;

NewGraph.CurrentIndex = G.CurrentIndex;

NewGraph.EdgesCount = G.EdgesCount;

NewGraph.Adj = G.Adj;

NewGraph.Matrix = G.Matrix;
NewGraph.Matrix = new Edge[G.Vertexes.Count, G.Vertexes.Count];
NewGraph.Matrix = new Edge[NewGraph.Vertexes.Count, NewGraph.Vertexes.Count];

for (int i = 0; i < NewGraph.Vertexes.Count; i++)

{

for (var q = NewGraph.Adj[i].Head; q != null; q = q.Next)

{
if (q != null)

{

NewGraph.Matrix[G.Vertexes.IndexOf(q.AdjEdge.Vertex1), G.Vertexes.IndexOf(q.AdjEdge.Vertex2)] = q.AdjEdge;

if (!NewGraph.Oriented)

NewGraph.Matrix[G.Vertexes.IndexOf(q.AdjEdge.Vertex2), G.Vertexes.IndexOf(q.AdjEdge.Vertex1)] = q.AdjEdge;

}

}

}
G = NewGraph;

G.Adj = null;

G.Type = true;

}

}

public void Print()

{

string str = "";

if (G.Type)

{

string numb1 = " ";

string line = " ";

for (int y = 0; y < G.Vertexes.Count; y++)

{

numb1 = numb1 + y.ToString();

line = line + "-";
}

Console.WriteLine(numb1);

Console.WriteLine(line);

for (int i = 0; i < G.Vertexes.Count; i++)

{

// Console.WriteLine("_");

str = str + i.ToString() + "|";

for (int j = 0; j < G.Vertexes.Count; j++)

{

if (G.Matrix[i, j] != null)

str = str + G.Matrix[i, j].Weight.ToString();

else

str = str + "-";

}

Console.WriteLine(str);

str = "";

}

}

else

{

for (int i = 0; i < G.Adj.Count; i++)

{

Console.WriteLine("*" + G.Adj[i].AdjIndex.ToString());

var q = G.Adj[i].Head;

if (q != null && q.AdjEdge != null)

{

for (q = G.Adj[i].Head; (q != null); q = q.Next)

{

if (G.Oriented == false)

{

if (G.Adj[i].AdjIndex == q.AdjEdge.Vertex1.Index)

{

str = str + " " + q.AdjEdge.Vertex2.Index.ToString();

}

else

{

str = str + " " + q.AdjEdge.Vertex1.Index.ToString();

}

}
else

{

str = str + " " + q.AdjEdge.Vertex2.Index.ToString();

}

}

Console.WriteLine(" ->" + str);

}

str = "";

}

}

}

}

}

6. AdjacencyList.cs

namespace АиСД_РГР

{

internal class AdjacencyList // список смежных вершин

{

public int AdjIndex;
public int Length;
public Node Head;
public class Node

{

public Node Next;

public Edge AdjEdge;
public Node()

{

AdjEdge = null;

Next = null;

}
public Node(Edge edge)

{

AdjEdge = edge;

Next = null;

}

}
public AdjacencyList()

{

Length = 0;

Head = null;

}
public bool AddNode(Edge edge)

{

if (Length == 0)

{

// Head.Next = new Node(edge);

Head = new Node(edge);

//Head.AdjEdge = edge;

Length++;

return true;

}
Node q = Head;

if ((q.AdjEdge.Vertex1.Index == edge.Vertex1.Index) && q.AdjEdge.Vertex2.Index == edge.Vertex2.Index)

return false;

for (int i = 0; i < Length - 1; i++)

{

if ((q.AdjEdge.Vertex1.Index == edge.Vertex1.Index) && q.AdjEdge.Vertex2.Index == edge.Vertex2.Index)

return false;

q = q.Next;

}

if ((q.AdjEdge.Vertex1.Index == edge.Vertex1.Index) && q.AdjEdge.Vertex2.Index == edge.Vertex2.Index)

{

return false;

}

else

{

q.Next = new Node(edge);

Length++;

return true;

}

}
public bool DeleteNode(Vertex vertex1, Vertex vertex2)

{

if (Length == 0)

return false;
if ((Length == 1) && ((((Head.AdjEdge.Vertex2.Index == vertex2.Index) && (Head.AdjEdge.Vertex1.Index == vertex1.Index)) || ((Head.AdjEdge.Vertex2.Index == vertex1.Index && Head.AdjEdge.Vertex1.Index == vertex2.Index)))))

{

Length--;

Head = null;

return true;

}
Node q = Head;

if (((Head.AdjEdge.Vertex2.Index == vertex2.Index) && (Head.AdjEdge.Vertex1.Index == vertex1.Index)) || ((Head.AdjEdge.Vertex2.Index == vertex1.Index && Head.AdjEdge.Vertex1.Index == vertex2.Index)))

{

if (q.Next == null)

{

q = null;

Length--;

return true;

}

Head = q.Next;

Length--;

return true;

}

for (int i = 0; i < Length - 1; i++)

{

if (q == null)//не нашли

return false;
if ((((q.Next.AdjEdge.Vertex2.Index == vertex2.Index) && (q.Next.AdjEdge.Vertex1.Index == vertex1.Index)) || ((q.Next.AdjEdge.Vertex2.Index == vertex1.Index && q.Next.AdjEdge.Vertex1.Index == vertex2.Index))) && (q.Next.Next == null))//если стоит в конце

{

q.Next = null;

Length--;

return true;

}
if ((q.Next.AdjEdge.Vertex2.Index == vertex2.Index) && (q.Next.AdjEdge.Vertex1.Index == vertex1.Index) || (q.Next.AdjEdge.Vertex2.Index == vertex1.Index && q.Next.AdjEdge.Vertex1.Index == vertex2.Index))//если не в конце

{

q.Next = q.Next.Next;

Length--;

return true;

}
q = q.Next;

}

return false;

}
public Node Prev(Node q)

{

if (Length == 1)

return null;

Node p = Head;

for (int i = 0; i < Length; i++)

{

if (p == null)

return null;

if (p.Next == null)

return null;

if (p.Next.AdjEdge.Vertex1.Index == q.AdjEdge.Vertex1.Index && p.Next.AdjEdge.Vertex2.Index == q.AdjEdge.Vertex2.Index)

return p;

p = p.Next;

}

return null;

}

}

}

7. Task1.cs

using System;

using System.Collections.Generic;
namespace АиСД_РГР

{

internal class Task1 // задача 1 - формирование двусвязного неориентированного графа

{

public Graph FBgraph;

public List BadVertexes;

public List Sons;

public int[] Parents;

public bool[] used;

public int[] dd, low;

public int counter = 0;
public Task1(Graph g)

{

FBgraph = g;
Parents = new int[FBgraph.G.Vertexes.Count * 2];
used = new bool[FBgraph.G.Vertexes.Count * 2];

dd = new int[FBgraph.G.Vertexes.Count * 2];

low = new int[FBgraph.G.Vertexes.Count * 2];
for (int p = 0; p < FBgraph.G.Vertexes.Count; p++)

{

Parents[p] = -1;

}
BadVertexes = new List();

Sons = new List();

}
public void FindBV(Vertex v1, int parent = -1)

{

Vertex z;

int x = v1.Index;

int kids = 0;

int y = 0;

used[x] = true;

dd[x] = low[x] = counter++;
var it1 = AbstractGraph.IteratorAllEdges.MakeIt(FBgraph.G);
for (it1.Beg(); it1.Input() != null; it1.Next())

{

AbstractGraph.IteratorAllEdges it2 = it1;

if (x == it1.Input().Vertex1.Index)

{

y = it2.Input().Vertex2.Index;

z = it2.Input().Vertex2;

}
else if (x == it1.Input().Vertex2.Index)

{

y = it2.Input().Vertex1.Index;

z = it2.Input().Vertex1;

}
else continue;

if (y == parent) continue;

if (used[y])

low[x] = Math.Min(low[x], dd[y]);

else

{

FindBV(z, v1.Index);

low[x] = Math.Min(low[x], low[y]);

if (low[y] >= dd[x] && parent != -1)

{

BadVertexes.Add(x);

int w1;

for (w1 = 0; w1 < FBgraph.G.Vertexes.Count; w1++)

{

if (parent == FBgraph.G.Vertexes[w1].Index)

break;

}

int w2;

for (w2 = 0; w2 < FBgraph.G.Vertexes.Count; w2++)

{

if (y == FBgraph.G.Vertexes[w2].Index)

break;

}

FBgraph.G.AddEdge(FBgraph.G.Vertexes[w1], FBgraph.G.Vertexes[w2]);

}

kids++;

/* return;*/

}

}

if (parent == -1 && kids > 1)

{

BadVertexes.Add(x);
var it3 = AbstractGraph.IteratorOutEdge.MakeIt(v1, FBgraph.G);

it3.Beg();

if (it3.Input().Vertex1.Index == v1.Index)

{

for (it3.Beg(); it3.Input() != null;)

{

Sons.Add(it3.Input().Vertex2.Index);

it3.Next();

}

}

else if (it3.Input().Vertex2.Index == v1.Index)

{

for (it3.Beg(); it3.Input() != null; it3.Next())

{

Sons.Add(it3.Input().Vertex1.Index);
}

}

for (int b = 0; b < Sons.Count; b++)

{

int b2, b3;

for (b2 = 0; b2 < FBgraph.G.Vertexes.Count; b2++)

{

if (b == FBgraph.G.Vertexes[b2].Index)

break;

}

for (b3 = 0; b3 < FBgraph.G.Vertexes.Count; b3++)

{

if ((b + 1) == FBgraph.G.Vertexes[(b2 + 1)].Index)

break;

}

FBgraph.G.AddEdge(FBgraph.G.Vertexes[b2], FBgraph.G.Vertexes[(b2 + 1)]);
}
}
}

}

}