Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Графы - файл 1.docx


Графы
скачать (76.1 kb.)

Доступные файлы (1):

1.docx77kb.09.12.2011 03:33скачать

Загрузка...

1.docx

Реклама MarketGid:
Загрузка...


Министерство образования и науки РФ

Тверской государственный технический университет

Кафедра электронных вычислительных машин

Отчёт к лабораторной работе №13

по дисциплине «Программирование на языках высокого уровня»

Графы


Тверь, 2011



Цель работы:

Научиться создавать и использовать динамические структуры данных – графы. Поскольку стандартных классов для этих целей не существует, все уровни сложности данной лабораторной работы подразумевают создание собственного класса для представления графа

Задание на работу:

Создать класс неориентированного графа и использовать его для решения следующей задачи. Сеть дорог определяется следующим образом. Имеется N перекрестков и K дорог, связывающих перекрестки. Каждая дорога определяется тройкой чисел: двумя номерами перекрестков и временем, требующимся на проезд по этой дороге. Найти кратчайший путь машины от перекрестка i до перекрестка j, если на перекрестке машина должна ждать время, равное числу пересекающихся дорог. Движение по дороге возможно в обоих направлениях.

Дополнительный уровень сложности 5. Вариант 46.
Алгоритм программы:

Класс Cross

value

links

marked

Конструктор Cross(val)

value = val

links = new List<Link>()

marked = false

Класс Link

cross

length



Конструктор Link(cross,length)

this.length = length

this.cross = cross

Класс Graph

list

minLength

minPath

Конструктор Graph()

list = new List<Cross>()

minLength = int.MaxValue

minPath = new Stack<Cross>()

AddCross(val)

Для cross в list

Если cross.value = val

Вернуть false

Все если

Все для

list.Add(new Cross(val))

Вернуть true

AddLink(val1,val2,len)

c1 = null

c2 = null

Для cur В list

Если cur.value = val1

c1 = cur

Иначе Если cur.value = val2

c2 = cur

Все Если

Все Для

Если c1 = null или c2 = null

Вернуть false

Все Если

c1.links.Add(new Link(c2, len))

c2.links.Add(new Link(c1, len))

Вернуть true

SearchRoad(val1,val2)

c1 = null

c2 = null

Для cur в list

Если cur.value = val1



c1 = cur

Иначе Если cur.value = val2

c2 = cur

Все Если

Все Для

Если c1 = null или c2 = null

Вернуть "error"

Все Если

stack = new Stack<Cross>()

SearchCross(c1, c2, stack, 0)

str = ""

Если minLength = int.MaxValue

Вернуть "Не найден путь!"

Все Если

Пока minPath.Count != 0

str += minPath.Pop().value + " "

Все пока

Вернуть str + Convert.ToString(val2)

SearchCross(c1,c2,stack,curLength)

Если c1.value = c2.value

Если curLength < minLength

minLength = curLength

minPath = new Stack<Cross>(stack)

Все Если

Вернуть

Все Если

stack.Push(c1)

c1.marked = true

Для c in c1.links

Если c.cross.marked = false

SearchCross(c.cross, c2, stack, curLength + c.length + c1.links.Count);

Все Если

Все для

stack.Pop().marked = false

Класс Program

Main(string[] args)

g = new Graph()

Perekrestki(g)

Dorogi(g)

n = SearchWay(g)

Result(g, n)

Perekrestki(g)

Печать "Введите номера вершин: "



Ввод n

Пока n != "."

Если !g.AddCross(n)

Печать "error"

Все Если

Ввод n

Все Пока

Dorogi(g)

Печать "Введите пары вершин и вермя(v1 v2 t):"

Ввод n

Пока n != "."

t = n.Split()

Если !g.AddLink(t[0],t[1],t[2])

Печать "error"

Все Если

Ввод n

Все Пока

SearchWay(g)

Печать "Введите пару вершин для поиска пути (v1 v2): "

Ввод n

t = n.Split()

n = g.SearchRoad(t[0],t[1])

Вернуть n

Result(g,n)

Если n = "error"

Печать "Вершина не найдена!"

Иначе

Печать "******Результат******"

Печать "Путь от " + n[0] + " до " + n[2] + " длина пути " + (g.minLength - 1)

Все Если

Текст программы:
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;
namespace ConsoleApplication18

{

class Cross

{

public int value;

public List<Link> links;

public bool marked;



public Cross(int val)

{

value = val;

links = new List<Link>();

marked = false;

}

}

class Link

{

public Cross cross;

public int length;

public Link(Cross cross, int length)

{

this.length = length;

this.cross = cross;

}

}

class Graph

{

List<Cross> list;

public int minLength;

Stack<Cross> minPath;

public Graph()

{

list = new List<Cross>();

minLength = int.MaxValue;

minPath = new Stack<Cross>();

}

public bool AddCross(int val)

{

foreach (Cross cross in list)

{

if (cross.value == val)

{

return false;

}

}

list.Add(new Cross(val));

return true;

}

public bool AddLink(int val1, int val2, int len)

{

Cross c1 = null;

Cross c2 = null;

foreach (Cross cur in list)

{

if (cur.value == val1)

{

c1 = cur;

}

else if (cur.value == val2)

{

c2 = cur;

}

}

if (c1 == null || c2 == null)

{

return false;

}

c1.links.Add(new Link(c2, len));

c2.links.Add(new Link(c1, len));

return true;

}

public string SearchRoad(int val1, int val2)

{

Cross c1 = null, c2 = null;

foreach (Cross cur in list)

{

if (cur.value == val1)

{



c1 = cur;

}

else if (cur.value == val2)

{

c2 = cur;

}

}

if (c1 == null || c2 == null)

{

return "error";

}

Stack<Cross> stack = new Stack<Cross>();

SearchCross(c1, c2, stack, 0);

string str = "";

if (minLength == int.MaxValue)

{

return "Не найден путь!";

}

while (minPath.Count != 0)

{

str += minPath.Pop().value + " ";

}

return str + Convert.ToString(val2);

}

void SearchCross(Cross c1, Cross c2, Stack<Cross> stack, int curLength)

{

if (c1.value == c2.value)

{

if (curLength < minLength)

{

minLength = curLength;

minPath = new Stack<Cross>(stack);

}

return;

}

stack.Push(c1);

c1.marked = true;

foreach (Link c in c1.links)

{

if (c.cross.marked == false)

{

SearchCross(c.cross, c2, stack, curLength + c.length + c1.links.Count);

}

}

stack.Pop().marked = false;

}

}


class Program

{

static void Main(string[] args)

{

Graph g = new Graph();

Perekrestki(g);

Dorogi(g);

string n = SearchWay(g);

Result(g, n);

Console.ReadLine();

}

static void Perekrestki(Graph g)

{

Console.WriteLine("Введите номера вершин: ");

string n = Console.ReadLine();

while (n != ".")

{

if (!g.AddCross(Convert.ToInt32(n))) Console.Write("error");

n = Console.ReadLine();

}



}

static void Dorogi(Graph g)

{

Console.WriteLine("Введите пары вершин и вермя(v1 v2 t): ");

string n = Console.ReadLine();

string[] t;

while (n != ".")

{

t = n.Split();

if (!g.AddLink(Convert.ToInt32(t[0]), Convert.ToInt32(t[1]), Convert.ToInt32(t[2])))

{

Console.WriteLine("error");

}

n = Console.ReadLine();

}

}

static string SearchWay(Graph g)

{

Console.Write("Введите пару вершин для поиска пути (v1 v2): ");

string n = Console.ReadLine();

string[] t = n.Split();

n = g.SearchRoad(Convert.ToInt32(t[0]), Convert.ToInt32(t[1]));

return n;

}

static void Result(Graph g,string n)

{

if (n == "error")

{

Console.WriteLine("Вершина не найдена!");

}

else

{

Console.WriteLine("******Результат******");

Console.WriteLine("Путь от " + n[0] + " до " + n[n.Length-1] +

" длина пути " + (g.minLength - 1));

}

}

}

}

Результаты выполнения программы:






Скачать файл (76.1 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации