Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Андрей Щербак
0 / 0 / 0
Регистрация: 29.09.2015
Сообщений: 3
#1

Реализация матрицы смежности и инцидентности, поиск циклов в графе - C++

24.09.2016, 17:55. Просмотров 699. Ответов 1
Метки нет (Все метки)

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

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#pragma once
#pragma once
#include <iostream>
#include <windows.h>
 
using namespace std;
 
class Doug
{
public:
    int p1;
    int p2;
    int k;
    int n;
    Doug() {}
    Doug(int i1, int i2, int k1 = 0, int n1 = 0) { p1 = i1; p2 = i2; k = k1; n = n1; }
    friend ostream & operator <<(ostream & os, Doug & D)
    {
        char *r[] = { "->","<-" };
        int i = 0;
        if (D.k < 0) i = 1;
        os << D.p1 << r[i] << D.p2 << "(" << D.n << ")";
        return os;
    };
 
};
 
class Mdoug
{
public:
    Doug* V;
    int M;
    Mdoug() {}
    Mdoug(int m1, Doug* E = 0)
    {
        M = m1; V = new Doug[M];
        if (E == 0) return;
        for (int i = 0; i < M; i++) V[i] = E[i];
    }
    Mdoug & operator += (Doug d)
    {
        int i = 0;
        for (i = 0; i < M; ++i)
        {
            if (d.p1 == V[i].p1 && d.p2 == V[i].p2 && d.k == V[i].k) { V[i].n += d.n; return *this; }
            if (d.p1 == V[i].p2 && d.p2 == V[i].p1 && d.k == -V[i].k) { V[i].n += d.n; return *this; }
        }
        Doug* Vnew = new Doug[M + 1];
        for (int i = 0; i < M; i++) Vnew[i] = V[i];
        Vnew[M] = d;
        V = Vnew;
        M++;
        return *this;
    }
    Mdoug & operator -= (Doug d)
    {
        int i = 0;
        for (i = 0; i < M; i++)
        {
            if (d.p1 == V[i].p1 && d.p2 == V[i].p2 &&  d.n == V[i].n) break;
            if (d.p2 == V[i].p1 && d.p1 == V[i].p2 &&  d.n == -V[i].n) break;
        }
        if (i == M) return  *this;
        V[i].k = V[i].k - d.k;
        if (V[i].k>0) return *this;
        for (int j = i + 1; j < M; j++) V[j - 1] = V[j];
        M--;
        return *this;
    }
    friend ostream & operator <<(ostream & os, Mdoug& D)
    {
        for (int i = 0; i < D.M; i++)
        {
            os << D.V[i];  if (i < D.M - 1) os << " ,  ";
        }
        os << endl;
        return os;
    }
};
 
class Graph : public Mdoug
{
protected:
    int max_index;
    int min_index;
public:
    Graph(int m, Doug* E = 0) : Mdoug(m, E) {}
    int*  AdjecMatrix;
    int*  IncidMatrix;
    int N;
    int  GetTops()
    {
        int*  Pt = new int[2 * M];
        int index = max_index = min_index = 0;
        for (int i = 0; i < M; i++)
        {
            int p1 = V[i].p1;
            int p2 = V[i].p2;
            if (p1 < min_index) min_index = p1;
            if (p2 < min_index) min_index = p2;
            if (p1 > max_index) max_index = p1;
            if (p2 > max_index) max_index = p2;
            int j = 0;
            for (j = 0; j < index; j++)  if (p1 == Pt[j])  break;
            if (j == index) Pt[index++] = p1;
            j = 0;
            for (j = 0; j < index; j++)  if (p2 == Pt[j])  break;
            if (j == index) Pt[index++] = p2;
        }
        N = index;
        return index;
    }
    void Fill_AdjecMatrix(bool show)
    {
        int N1 = max_index - min_index + 1;
        AdjecMatrix = new int[N1*N1];
        for (int i = 0; i < N1*N1; i++) AdjecMatrix[i] = 0;
        for (int i = 0; i < M; i++)
        {
            int p1 = V[i].p1;
            int p2 = V[i].p2;
            int ml = V[i].n;
            int r = V[i].k;
            int ind = (p1 - min_index)*N1 + p2 - min_index;
            if (r < 0) ind = (p2 - min_index)*N1 + p1 - min_index;
            AdjecMatrix[ind] = ml;
        }
        if (show) printf("\nМатрица смежности\n");
        { printf("     ");
        for (int i = 0; i < N1; i++)  printf("%5d ", min_index + i); printf("\n");
        printf("     ");
        for (int i = 0; i < N1; i++)  printf("------"); printf("\n");
 
        for (int i = 0; i < N1; i++)
        {
            printf("%4d |", min_index + i);
            for (int j = 0; j < N1; j++)
                printf("%5d ", AdjecMatrix[i*N1 + j]);
            printf("\n");
        }
        }
    }
    void Fill_IncidMatrix(bool show)
    {
        int N1 = max_index - min_index + 1;
        if (N1 <= 0) N1 = this->GetTops();
        IncidMatrix = new int[M*N1];
        for (int i = 0; i < M*N1; i++) IncidMatrix[i] = 0;
        for (int i = 0; i < M; i++)
        {
            int p1 = V[i].p1;
            int p2 = V[i].p2;
            int ml = V[i].n;
            int r = V[i].k;
            for (int j = 0; j < N1; j++)
            {
                IncidMatrix[i*N1 + p1] = -ml*r;
                IncidMatrix[i*N1 + p2] = ml*r;
            }
        }
        if (show)
        {
            printf("\nМатрица инцидентности\n");
            printf("          ");
            for (int i = 0; i < N1; i++)  printf("%5d ", min_index + i); printf("\n");
            printf("          ");
            for (int i = 0; i < N1; i++)  printf("------"); printf("\n");
            for (int i = 0; i < M; i++)
            {
                cout << V[i] << " |";
                for (int j = 0; j < N1; j++)
                    printf("%5d ", IncidMatrix[i*N1 + j]);
                printf("\n");
            }
        }
    }
};
 
void Test()
{
    setlocale(LC_ALL, "RUSSIAN");
    Doug  D[] = { Doug(2,1,1,2), Doug(2,2,1,1) , Doug(1,3,1,1),
        Doug(1,2,1,1), Doug(3,0,1,1), Doug(3,2,1,1) };
    Graph G(6, D);
    cout << "Перечень дуг в графе c с указанием кратности\n"
        << G << endl;
    cout << "Число вершин графа = " << G.GetTops() << endl;
    G.Fill_AdjecMatrix(true);
    G.Fill_IncidMatrix(true);
    Doug d[] = { Doug(1, 4, 1, 1), Doug(4,1,-1,1), Doug(0, 1, 1, 1) };
    G += d[0];
    cout << "Добавлена дуга (1,4, 1,1). Число вершин графа = "
        << G.GetTops() << endl;
    G += d[1];
    cout << "Добавлена дуга (4,1,-1,1). Число вершин графа = "
        << G.GetTops() << endl;
    G -= d[2];
    cout << "Удалена   дуга (0,1, 1,1). Число вершин графа = "
        << G.GetTops() << endl;
    G.Fill_AdjecMatrix(true);
    G.Fill_IncidMatrix(true);
 
}
Вот что получается в итоге
0
Миниатюры
Реализация матрицы смежности и инцидентности, поиск циклов в графе  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.09.2016, 17:55
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Реализация матрицы смежности и инцидентности, поиск циклов в графе (C++):

Как из матрицы смежности получить матрицу инцидентности? - C++
Здравствуйте. Можно ли из матрицы смежности получить матрицу инцидентности? Матрица смежности у меня для связного неориентированного графа...

Определение матрицы смежности графа по заданной матрице инцидентности - C++
Доброй ночи :) Изучаю графы, написал фукнцию для конвертации матрицы инцидентности в матрицу смежности, а наоборот не выходит. ...

С матрицы смежности в матрицу инцидентности, список рёбер и вершин, диаграмма - C++
Помогите, пожалуйста. На C# или C++ нужна такая программа, что когда задается матрица смежности (5 на 5 можно) и выводились: 1) матрица...

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

Поиск циклов в графе - C++
Как узнать что граф имеет цикл?

Поиск Ф-циклов в графе - C++
Нужно вывести на печать все фундаментальные циклы графа. Мой код выводит правильно(судя по данному примеру),но помоему он не разделяет сами...

1
Андрей Щербак
0 / 0 / 0
Регистрация: 29.09.2015
Сообщений: 3
25.09.2016, 10:48  [ТС] #2
Ап
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.09.2016, 10:48
Привет! Вот еще темы с ответами:

Поиск отрицательых циклов в графе - C++
подскажите пожалуйста, как определить, есть ли в графе отрицательные циклы....граф задаётся матрицей смежности P.S очень срочно...

Поиск отрицательных циклов в графе - C++
Добрый день. Имеется код производящий обход графа. Мне надо &quot;Определить, имеются ли //у него циклы отрицательного веса. . Я...

Поиск циклов в ориентированном графе - C++
Доброго времени суток. Может кому-нибудь из вас не составит особого труда, или возможно кто-то писал похожую программу. В общем, я написал...

Поиск всех циклов в неориентированном графе. - C++
На входе программа принимает номера вершин и вес ребра между ними. Например: 2 3 1 - между вершинами 2 и 3 есть ребро весом 1. Нужно...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru