VPF::Поиск в ширину в графе - Форум программистов

Northex

Дата 5.1.2015, 20:30 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 5.1.2015

Репутация: нет
Всего: нет

Здравствуйте. Проблема такая есть матрица смежности обозначающая мой граф. Есть функция поиска в ширину. я указываю в ней целевую вершину ( в данном коде 5) и в текст бокс он выводит весь пусть что он прошел до целевой вершины. а мне нужен кратчайший путь ( из начального состояния в целевой). я понимаю
Вот мой граф

Код


 private void draw()
        {                         // 1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9
            a = new float[n, n] {   {0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0 },  //1
                                    {1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },//2
                                    {1,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0 },//3
                                    {0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0 },//4
                                    {0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0 },//5
                                    {0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0 },//6
                                    {0,0,1,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0 },//7
                                    {0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0 },//8
                                    {0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 },//9
                                    {0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0 },//10
                                    {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,0,0 },//11
                                    {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0 },//12
                                    {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0 },//13
                                    {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1 },//14
                                    {0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0 },//15
                                    {0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0 },//16
                                    {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0 },//17
                                    {0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,0,0 },//18
                                    {0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0 }//19
                                };
         
            

        }

Функция поиска:

Код


 private void button1_Click(object sender, EventArgs e)
        {
            draw();
            temp = "";
            rebra = new int[n, n];
            //Очередь вершин на рассмотрение
            Queue<int> openVertex = new Queue<int>();
            Queue<int> Way = new Queue<int>();
            //Список уже рассмотренных вершин
            List<int> CloseVertex = new List<int>();
            //Начинаем обход с 1й вершины
            openVertex.Enqueue(0);
            //До тех пор, пока не обошли все вершины
            while (openVertex.Count != 0)
            {
                //Выталкиваем из начала списка индекс текущей вершины
                int index = openVertex.Dequeue();
                if (index == 5) break;
              //  textBox2.Text += Convert.ToString(index);
                for (short j = 0; j < n; j++)
                {
                    //Если ребро не нулевое 
                    if (a[index, j] != 0)
                    {
                        //И вершина еще не была рассмотрена и не находится в очереди на рассмотрение
                        if (!CloseVertex.Contains(j) && !openVertex.Contains(j))
                        {
                            //Добавить вершину в список на рассмотрение
                            openVertex.Enqueue(j);

                            rebra[index, j] = 1;
                           
                            
                        }
                    }

                    else rebra[index, j] = 0;
                 
                }
                //Добавляем информацию о вершине в строку вывода
                temp += " -> " + Convert.ToString(index + 1);
                //Добавляем вершину в список уже рассмотренных
                CloseVertex.Add(index);
            }
            textBox1.Text += q + "Прохождение графа А в ширину:";
            textBox1.Text += q + temp;

        }

Вот мой граф визуально (сделал в виде дерева просто чтобы понять суть)

Cheloveck

Дата 6.1.2015, 15:06 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1578
Регистрация: 26.7.2008
Где: Тула

Репутация: нет
Всего: 32

Поиск в ширину принципиален? Используй A*
При поиске в ширину ты должен хранить спиок всех путей, по которым ходишь. Если граф достаточно кустистый, то ты рискуешь сожрать всю память.

Это сообщение отредактировал(а) Cheloveck - 6.1.2015, 15:13

--------------------

baldina

Дата 13.1.2015, 17:58 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

Репутация: нет
Всего: 101

Цитата(Cheloveck @ 6.1.2015, 15:06

)

Если граф достаточно кустистый

это не его случай. к тому же A* тот же поиск в ширину. т.е. если граф достаточно кустистый, то и ему мало не покажется.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Общие вопросы по .NET и C# \| Следующая тема »