5 / 5 / 2
Регистрация: 13.03.2017
Сообщений: 101
1

Орграф - предшественники

15.05.2018, 13:05. Показов 1230. Ответов 0
Метки нет (Все метки)

Задан орграф в виде количества вершин п<=10 и матрицы
смежности.
Напечатать номера вершин, имеющих и предшественни*ков, и преемников.

C++
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <iostream>
#include <windows.h>
#define  NMAX  10    /* максимальное число вершин графа */
#define  RMAX 100    /* максимальное число ребер          */
using namespace std;
 
void SMEJNOST(int g1[NMAX][NMAX], int n)
 
{
    int i, j;
    cout << "Номера смежных вершин" << endl;
    for (i = 0; i<n; i++)
    {
        cout << "Для " << i << " " << "вершины смежны: ";
        for (j = 0; j < n; j++)
        {
            if (g1[i][j] == 1)
            {
                cout << j << " ";
            }
        }
        cout << endl;
    }
 
 
}
 
/*---------------------------------------------------------*/
/*         функция ввода матрицы смежности      */
/*---------------------------------------------------------*/
void  VVOD_MATR_SM(int g1[NMAX][NMAX], int    n)
/*  Входные данные:    n  –  количество вершин    */
/*  Выходные данные:  g1 – матрица смежности  */
{
    int  i, j;  /* параметры циклов */
                /* Обнуление матрицы смежности */
    for (i = 0; i<n; i++)
        for (j = 0; j<n; j++)   g1[i][j] = 0;
    cout << "введите последовательность: ";
    while (cin >> i >> j)
    {
        if (i == -1 || j == -1)
            break;
        else
            g1[i][j] = g1[j][i] = 1;
    }
    cout << "  ";
    for (j = 0; j<n; j++)
        cout << j;
    cout << endl;
    cout << "  ";
    for (j = 0; j<n; j++)
        cout << "-";
 
    for (i = 0; i<n; i++)
    {
        cout << endl << i << "|";
        for (j = 0; j<n; j++)  cout << g1[i][j];
    }
}
/*------------------------------------------------------------*/
/*     функция вывода матрицы инцидентности    */
/*------------------------------------------------------------*/
void  VIVOD_MATR_IN(int g2[NMAX][RMAX], int    n, int  k)
/*  Входные данные:   g2 – матрица инцидентности ,
n  –  количество вершин ,
k  –  количество ребер */
{
    int  i, j;  /* параметры циклов */
    cout << "Матрица инцидентности\n\n";
    cout << "  ";
    for (j = 0; j<k; j++)
        cout << j;
    cout << endl;
    cout << "  ";
    for (j = 0; j<k; j++)
        cout << "-";
 
    for (i = 0; i<n; i++)
    {
        cout << endl << i << "|";
        for (j = 0; j<k; j++)  cout << g2[i][j];
    }
}
/*------------------------------*/
/*     главная функция     */
/*------------------------------*/
 
void main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    int  g1[NMAX][NMAX],     /* матрица смежности */
        g2[NMAX][RMAX] = { 0 },  /* м-ца инцидентности */
        n,               /* количество вершин */
        k;               /* количество ребер  */
    int  i, j; /* индексы элементов матриц g1,g2 */
    cout << "\nВведите количество вершин:";
    cin >> n;
    VVOD_MATR_SM(g1, n);   /* ввод матрицы смежности g1 */
                           /* Формировавание матрицы инц-ти g2 */
    SMEJNOST(g1, n);
    k = 0;
    for (i = 0; i<n; i++)
        for (j = i; j<n; j++)
            if (g1[i][j])
            {
                if (i == j && g1[i][j] == 1)
                {
 
                    g2[i][k] = 2;
                    k++;
                }
                else
                {
                    g2[i][k] = 1;
                    g2[j][k] = 1;
                    k++;
                }
            }
    VIVOD_MATR_IN(g2, n, k);   /* вывод м-цы  g2 */
    cout << endl;
    system("pause");
}
Добавлено через 18 минут
Проверьте пожалуйста, правильно ли написал?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void rebra(int g1[NMAX][NMAX], int n)
{
        int ans = 0;
        for (int i = 0; i<n; i++)
            for (int j = 0; j<n; j++)
        for (int i = 0; i<n; i++) 
        {
            int cnt = 0; //счётчик
            for (int j = 0; j<n; j++) 
                        {
                if (g1[i][j] == 1) cnt++;  //подсчёт степени
            }
            if (cnt == 1) ans++;  //проверка на висячую вершину
        }
        cout << "inc rebra = "<< ans << endl;
}
Добавлено через 11 минут
Прикреплённый снизу код - проверка на инцидентное ребро
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.05.2018, 13:05
Ответы с готовыми решениями:

орграф на С++
Пожалуйста, помогите! Может, кто-то когда-то писал такую программу: в файле задана матрица...

Как задать орграф структурой?
Вот у меня есть структура typedef struct node { struct node *t; unsigned char clr; } NODE; я...

Написание класса, описывающего граф/орграф
Написать на C++ класс, описывающий граф/орграф. Класс должен поддерживать следующую...

Реализация АТД Взвешенный орграф. Не корректно считает радиус и путь
Помогите пожалуйста найти ошибку в решении задачи: Реализация АТД «Взвешенный орграф». Граф...

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
15.05.2018, 13:05
Помогаю со студенческими работами здесь

Определить, имеет ли данный ациклический орграф корень. Список смежности
Корень ациклического графа-такая вершина u,что из нее существуют пути в каждую из остальных вершин...

Орграф
Доказать, что в любом конечном ациклическом орграфе существуют вершины с нулевой степенью исхода и...

Орграф
Доказать, что для любой вершины х є X орграфа G=(X,Г) найдется МНМ, содержащие х.

Орграф
Прошу,перевидете просто на С,ибо С++ не юзаю совсем.Заранее благодарю. Vvedite chislo vetvei...


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

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

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