-2 / 8 / 2
Регистрация: 01.02.2013
Сообщений: 187

Является ли граф связным

13.04.2016, 14:31. Показов 4654. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
В задаче нужно определить является ли неориентированный граф связным. Нужно использовать стек. Только начал изучать Java, а задача сложная и не могу разобраться.
Есть на данный момент:
Java
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
33
34
35
36
37
38
39
40
import java.util.Scanner; 
 
class Graph {
    private int[][] graphMatrix;
    // массив
    public Graph(int size) {
        graphMatrix = new int[size][size];
    }
    // добавляем ребро в массив
    public void addComm(int left, int right) {
        graphMatrix[left][right] = 1; // пусть вес пока равен 1
    }
    // читаем ребро по вершинам
    public int readComm(int left, int right) {
        return graphMatrix[left][right];
    }
}
public class AwesomeStack {
    
    public static void main(String[] args) {        
        Scanner sc = new Scanner(System.in);   
        String[] graf_sc = sc.nextLine().split(" ");        
        int n = Integer.parseInt( graf_sc[0]), // количество вершин
            m = Integer.parseInt( graf_sc[1]); // количество ребер                       
        
        Graph mStack = new Graph(n-1);
        
        for ( int i = 0; i < m; i++ ) {
            String[] input = sc.nextLine().split(" ");
            int left = Integer.parseInt( input[0] );
            int right = Integer.parseInt( input[1] );
            mStack.addComm( left, right );  
        }
 
        // Выводим да, если граф является связным
        // или нет
                        
        System.out.println("");                             
    }
}
каких либо идей уже у меня нет
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
13.04.2016, 14:31
Ответы с готовыми решениями:

Определить является ли граф связным
Нужно определить является ли граф связным. Но при работе программы появляется ошибка при нажатии на кнопку, которая определяет связный граф...

Проверить , является ли граф связным
Доброго времени суток. В очередной раз без Вашей помощи не обойтись!!!!!! ЗАДАНИЕ: Дан неориентированный граф, содержащий n вершин....

Проверить, является ли заданный граф связным
Помогите, пожалуйста, исправить ошибку!!! edge(a, c). edge(a, b). edge(c, d). edge(b, d). edge(e, d). ...

1
-2 / 8 / 2
Регистрация: 01.02.2013
Сообщений: 187
15.04.2016, 12:24  [ТС]
Может быть кому-то понадобится:
Java
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.Scanner; 
 
class Stack {
    private int mSize;
    private int[] stackArray;
    
    public Stack(int m) {
        this.mSize = m;
        stackArray = new int[mSize];
    }
    public void addElement(int x, int i) {
        stackArray[x] = i;
    }
    public int readElement(int x) {
        return stackArray[x];
    }
    public int size() {
        return stackArray.length;
    }
}
 
public class connectGraph {
    
    public static void main(String[] args) {                
        Scanner sc = new Scanner(System.in);     
        int n = sc.nextInt(),
            m = sc.nextInt();                 
        
        if ( n - 1 >  m ) {
            System.out.println("NO");   
            System.exit(0);
        }
        
        Stack mStack = new Stack(n);
        
        for ( int i = 0; i < mStack.size(); i++ )
            mStack.addElement(i, i);                    
        
        for ( int i = 0; i < m; i++ ) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            
            int color = mStack.readElement(v);
            
            for ( int z = 0; z < mStack.size(); z++ ) 
                if ( mStack.readElement(z) == color )
                    mStack.addElement(z, mStack.readElement(u));            
        }
        
        boolean allVertices = true;     
        for ( int i = 0; i < mStack.size(); i++ ) 
            allVertices = allVertices && ( mStack.readElement(i) == mStack.readElement(0) );
                                        
        if ( allVertices ) System.out.println("YES");
        else System.out.println("NO");                  
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
15.04.2016, 12:24
Помогаю со студенческими работами здесь

Определить, является ли заданный граф связным
Пожалуйста, помогите, очень-очень нужна ваша помощь в задании: &quot;определить является ли заданный граф связным&quot;.

Определить, является ли связным заданный граф
Определить, является ли связным заданный граф

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

Является ли граф ациклическим
Можно ли это реализовать с помощью path :: Graph -&gt; Vertex -&gt; Vertex -&gt; Bool path g v w = w ‘elem‘ (reachable g v), которая...

Является ли граф деревом
Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является деревом, если граф - связный и в графе...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

Новые блоги и статьи
Как использовать Bluetooth-модуль HC-05 с Arduino
Wired 08.07.2025
Bluetooth - это технология, созданная чтобы заменить кабельные соединения. Обычно ее используют для связи небольших устройств: мобильных телефонов, ноутбуков, наушников и т. д. Работает она на частоте. . .
Руководство по структурам данных Python
AI_Generated 08.07.2025
Я отчетливо помню свои первые серьезные проекты на Python - я писал код, он работал, заказчики были относительно довольны. Но однажды мой наставник, взглянув на мою реализацию поиска по огромному. . .
Тестирование энергоэффективности и скорости вычислений видеокарт в BOINC проектах
Programma_Boinc 08.07.2025
Тестирование энергоэффективности и скорости вычислений видеокарт в BOINC проектах Опубликовано: 07. 07. 2025 Рубрика: Uncategorized Автор: AlexA Статья размещается на сайте с разрешения. . .
Раскрываем внутренние механики Android с помощью контекста и манифеста
mobDevWorks 07.07.2025
Каждый Android-разработчик сталкивается с Context и манифестом буквально в первый день работы. Но много ли мы задумываемся о том, что скрывается за этими обыденными элементами? Я, честно говоря,. . .
API на базе FastAPI с Python за пару минут
AI_Generated 07.07.2025
FastAPI - это относительно молодой фреймворк для создания веб-API, который за короткое время заработал бешеную популярность в Python-сообществе. И не зря. Я помню, как впервые запустил приложение на. . .
Основы WebGL. Раскрашивание вершин с помощью VBO
8Observer8 05.07.2025
На русском https:/ / vkvideo. ru/ video-231374465_456239020 На английском https:/ / www. youtube. com/ watch?v=oskqtCrWns0 Исходники примера:
Мониторинг микросервисов с OpenTelemetry в Kubernetes
Mr. Docker 04.07.2025
Проблема наблюдаемости (observability) в Kubernetes - это не просто вопрос сбора логов или метрик. Это целый комплекс вызовов, которые возникают из-за самой природы контейнеризации и оркестрации. К. . .
Проблемы с Kotlin и Wasm при создании игры
GameUnited 03.07.2025
В современном мире разработки игр выбор технологии - это зачастую балансирование между удобством разработки, переносимостью и производительностью. Когда я решил создать свою первую веб-игру, мой. . .
Создаем микросервисы с Go и Kubernetes
golander 02.07.2025
Когда я только начинал с микросервисами, все спорили о том, какой язык юзать. Сейчас Go (или Golang) фактически захватил эту нишу. И вот почему этот язык настолько заходит для этих задач: . . .
C++23, квантовые вычисления и взаимодействие с Q#
bytestream 02.07.2025
Я всегда с некоторым скептицизмом относился к громким заявлениям о революциях в IT, но квантовые вычисления - это тот случай, когда революция действительно происходит прямо у нас на глазах. Последние. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru