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

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

13.04.2016, 14:31. Показов 4241. Ответов 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.04.2016, 14:31
Ответы с готовыми решениями:

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

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

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

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

1
-2 / 8 / 2
Регистрация: 01.02.2013
Сообщений: 187
15.04.2016, 12:24  [ТС] 2
Может быть кому-то понадобится:
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.04.2016, 12:24
Помогаю со студенческими работами здесь

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

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

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

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru