Поиск в ширину с помощью списка инцидентности в ориентированном графе - C#

Узнай цену своей работы

Формулировка задачи:

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

Решение задачи: «Поиск в ширину с помощью списка инцидентности в ориентированном графе»

textual
Листинг программы
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
 
namespace Graf
{
    class Program
    {
        static void Main(string[] args)
        {
            BFS graf = new BFS();
            graf.readgr();
 
            Console.WriteLine("Выберете начальную вершину для поиска в ширину (от 1 до 6)"); 
            try
            {
                int key = int.Parse(Console.ReadLine());
                graf.bfs(key);
            }
            catch (System.Exception ex)
            {
            }
            
        }
    }
    class BFS
    {
        const int vert = 6;
        const int rib = 6;
        int[,] gr;
        int[] vstd;
 
        public void readgr()
        {
            gr = new int[rib, vert];
            gr[0, 0] = -1; gr[0, 1] = 0; gr[0, 2] = 0; gr[0, 3] = 0; gr[0, 4] = 0; gr[0, 5] = 1;
            gr[1, 0] = 0; gr[1, 1] = 0; gr[1, 2] = 0; gr[1, 3] = 0; gr[1, 4] = 1; gr[1, 5] = -1;
            gr[2, 0] = 0; gr[2, 1] = 0; gr[2, 2] = 0; gr[2, 3] = 1; gr[2, 4] = -1; gr[2, 5] = 0;
            gr[3, 0] = 0; gr[3, 1] = 0; gr[3, 2] = 1; gr[3, 3] = -1; gr[3, 4] = 0; gr[3, 5] = 0;
            gr[4, 0] = 0; gr[4, 1] = 1; gr[4, 2] = -1; gr[4, 3] = 0; gr[4, 4] = 0; gr[4, 5] = 0;
            gr[5, 0] = 1; gr[5, 1] = -1; gr[5, 2] = 0; gr[5, 3] = 0; gr[5, 4] = 0; gr[5, 5] = 0;
 
            Console.WriteLine("         v1   v2   v3   v4   v5   v6");
            for (int i = 0; i < rib; i++)
            {
                Console.Write("rib " + (i + 1).ToString() + " |");
                for (int j = 0; j < vert; j++)
                {
                    if (gr[i, j] == -1)
                    {
                        Console.Write(" " + gr[i, j] + "  ");
                    }
                    else
                        Console.Write("  " + gr[i, j] + "  ");
                }
                Console.Write("|\n");
            }
 
            vstd = new int[vert];
            for (int i = 0; i < vert; i++)  //инициализируем массив меток
                vstd[i] = 0;
        }
 
        public void bfs(int source)
        {
            vstd[source--] = 1;
            bool okflag = true;
            while (okflag)
            {
                for (int i = 0; i < vert; i++)
                {
                    if (vstd[i] == 2)
                    {
                        for (int j = 0; j < vert; j++)
                        {
                            if (gr[i,j] == -1)
                                    if (vstd[j] == 0)
                                    {
                                        vstd[j] = 1;
                                        Console.Write("v" + (j + 1).ToString());
                                    }
                        }
                        vstd[i] = 3;
                    }
                }
                for (int i = 0; i < vert; i++)
                {
                    if (vstd[i] == 1)
                        vstd[i] = 2;
                }
                okflag = false;
                for (int i = 0; i < vert; i++)
                    if (vstd[i] < 2)
                        okflag = true;
                Console.Write("\n");
 
            }
        }
    }
}

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

15   голосов , оценка 3.933 из 5
Похожие ответы