Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 91, средняя оценка - 4.96
Kedr
0 / 0 / 0
Регистрация: 17.05.2009
Сообщений: 20
#1

Графы (с++) - C++

20.12.2009, 15:38. Просмотров 11722. Ответов 37
Метки нет (Все метки)

Помогите с задачей: граф задается своей матрицей смежностей; вывести на экран матрицу инцидентности графа.

Добавлено через 1 час 34 минуты
неужели никто не может помочь? пожалуйста, посмотрите кто-нибудь...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2009, 15:38     Графы (с++)
Посмотрите здесь:

C++ Графы
C++ [C++] графы
C++ Графы
Графы C++
Графы C++
Графы C++
Графы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
20.12.2009, 15:52     Графы (с++) #2
а что здесь помогать? вы теорию знаете, собственно осталось закодить.. если у вас будут ошибки, которые вы не можете поправить, когда милости просим..
Kedr
0 / 0 / 0
Регистрация: 17.05.2009
Сообщений: 20
20.12.2009, 16:00  [ТС]     Графы (с++) #3
в этой задаче, я не знаю, как вывести матрицу инцидентности...
Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
20.12.2009, 16:06     Графы (с++) #4
википедия говорит что:
Инцидентность — понятие, используемое только в отношении ребра и вершины: если v1,v2 — вершины, а e = (v1,v2) — соединяющее их ребро, тогда вершина v1 и ребро e инцидентны, вершина v2 и ребро e тоже инцидентны. Две вершины (или два ребра) инцидентными быть не могут. Для обозначения ближайших вершин (рёбер) используется понятие смежности.
получается - инцидентнось есть факт принадлежности ребра к вершине или наоборот.

т. е. Матрица инцидентности, это матрица, в которой отмечено какое ребро принадлежит какой вершине.

а так же, из той же википеди:
Матрица инцидентности графа — это матрица, значения элементов которой характеризуется инцидентностью соответствующих вершин графа (по вертикали) и его рёбер (по горизонтали). Для неориентированного графа элемент принимает значение 1, если соответствующие ему вершина и ребро инцидентны. Для ориентированного графа элемент принимает значение 1, если инцидентная вершина является началом ребра, значение -1, если инцидентная вершина является концом ребра; в остальных случаях (в том числе и для петель) значению элемента присваивается 0.
Матрица смежности графа — это матрица, значения элементов которой характеризуются смежностью вершин графа. При этом значению элемента матрицы присваивается количество рёбер, которые соединяют соответствующие вершины (то есть которые инцидентны обоим вершинам). Петля считается сразу двумя соединениями для вершины, то есть к значению элемента матрицы в таком случае следует прибавлять 2.
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
20.12.2009, 16:22     Графы (с++) #5
C++
1
2
3
4
5
for (int i = 0; i < n; ++i){
   for (int j = 0; j < v; ++j)
      cout << mi[i,j] << " ";
   cout << endl;
}
Добавлено через 1 минуту
i - количество вершин, v - количество ребер матрицы смежности..

Добавлено через 13 минут
mi - сама матрица смежности
Shved
9 / 9 / 1
Регистрация: 07.06.2009
Сообщений: 34
03.01.2010, 17:10     Графы (с++) #6
Нужна помощь...не могу никак разобраться в чём проблема...ничего не выводит... Сделал структуру ребро и класс граф с указателем на первое ребро...Проблема в том, что функция печати ничего не выводит... В чём проблема?

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
#include<iostream>
using namespace std;
 
struct rebro
{
    rebro *next;
    int weight;
    int a,b;
};
 
class graf
{
protected:
    rebro *first;
public:
    graf();
    graf(int kol);
    void print();
};
 
graf::graf()
{
    first=NULL;
};
 
graf::graf(int kol)
{
    int z=0,c=0,d=0;
    rebro *temp=first;
    
    for (int i=0;i<kol;i++)
    {
        z=c*4+d;
        c=rand()%kol;
        d=rand()%kol;
        temp->weight=z;
        temp->a=c;
        temp->b=d;
        temp=temp->next;
    }
}
 
void graf::print()
{
    rebro *temp=first;
    while (temp->next!=NULL)
    {
        cout<<temp->a<<" "<<temp->b<<" weight - "<<temp->weight<<endl;
        temp=temp->next;
    }
}
 
void main()
{
    graf a(5);
    a.print();
}
Добавлено через 16 минут
up
ISergey
Maniac
Эксперт С++
1347 / 880 / 52
Регистрация: 02.01.2009
Сообщений: 2,645
Записей в блоге: 1
03.01.2010, 17:16     Графы (с++) #7
Цитата Сообщение от Shved Посмотреть сообщение
Код
graf::graf(int kol)
{
 int z=0,c=0,d=0;
 rebro *temp=[COLOR="Red"]first[/COLOR]; // first - чему равно?
for (int i=0;i<kol;i++)
 {
 z=c*4+d;
 c=rand()%kol;
 d=rand()%kol;
 temp->weight=z;
 temp->a=c;
 temp->b=d;
 temp=temp->next;
 }
}


Цитата Сообщение от Shved Посмотреть сообщение
Код
void graf::print()
{
 rebro *temp=[COLOR="#ff0000"]first[/COLOR];//first - чему равно?
 while (temp->next!=NULL)
 {
 cout<<temp->a<<" "<<temp->b<<" weight - "<<temp->weight<<endl;
 temp=temp->next;
 }
}
У тебя в коде идет работа с указателями.. но я не увидел ни одного оператора new и delete
Shved
9 / 9 / 1
Регистрация: 07.06.2009
Сообщений: 34
11.01.2010, 19:51     Графы (с++) #8
Цитата Сообщение от ISergey Посмотреть сообщение
У тебя в коде идет работа с указателями.. но я не увидел ни одного оператора new и delete
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
graf::graf()
{
    first->a=0;
    first->b=0;
    first->weight=0;
    first->next=NULL;
};
 
graf::graf(int kol)
{
    int z=0,c=0,d=0;
    rebro *temp,*qw;
    first->a=0;
    first->b=0;
    first->weight=0;
    first->next=NULL;
    temp=new rebro[kol];
    temp=first;
    qw=temp;
    temp=temp->next;
    for (int i=0;i<kol-1;i++)
    {
        z=c*4+d;
        c=rand()%kol;
        d=rand()%kol;
        temp->weight=z;
        temp->a=c;
        temp->b=d;
        temp=temp->next;
    }
    first=qw;
}
 
void graf::print()
{
    rebro *temp=first;
    while (temp->next!=NULL)
    {
        cout<<temp->a<<" "<<temp->b<<" weight - "<<temp->weight<<endl;
        temp=temp->next;
    }
}
Но всё равно немного не то...как во втором конструкторе их связать и в выводе зачем заново задавать значения?
FMX
10 / 10 / 2
Регистрация: 13.11.2009
Сообщений: 87
17.01.2010, 22:26     Графы (с++) #9
Привет всем!!!

Народ, помощи прошу. задача про графы. в main-функции я задал один граф списком смежности (то есть какой узел с каким узлом связан.), а другую через for-шлейф. методы в классе создают узлы, ребра, считают их и должны показывать, сколько ребер максимум (int maxGrad()) и минимум (int minGrad()) висит на узлах графа. и ещё лдин метод должен проверять наличие пути от одного узла к другому (bool reachable(uint Node1, uint Node2). все придумал, тока на эти три метода не остается мозгов уже. насчет первых 2 есть задумка, по которой в каждой строчке матрицы считается кол-во ребер и оно потом сравнивается. потом выбирается максимум и минимум. нет идей, как это в коде написать. про путь от узла к узлу ваще идей нет.

вот, что имеется:

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
#include <iostream>
using namespace std;
 
typedef unsigned int uint;
 
class Graph {
 
public:
    Graph(uint NoOfNodes);
    void addEdge(uint Node1, uint Node2);
    bool hasEdge(uint Node1, uint Node2);
    uint noOfEdges();
    uint noOfNodes();
    void printGraph();
    int maxGrad();
    int minGrad();
    bool reachable(uint Node1, uint Node2);
    ~Graph();
private:
    uint mNoOfNodes;
    uint **AdjacencyMatrix;
};
 
Graph :: Graph (uint NoOfNodes ) {
    mNoOfNodes = NoOfNodes ;
    AdjacencyMatrix = new uint *[ NoOfNodes ];
    for ( uint i =0; i < NoOfNodes ; i ++)
    AdjacencyMatrix [ i ] = new uint [ NoOfNodes ];
  }
 
Graph::~Graph() {
    if (mNoOfNodes > 0) delete[] AdjacencyMatrix;
}
 
void Graph::addEdge(uint Node1, uint Node2)
{
    AdjacencyMatrix[Node1][Node2]=1;
    AdjacencyMatrix[Node2][Node1]=1;
}
 
bool Graph::hasEdge(uint Node1, uint Node2) {
    if (mNoOfNodes < 1) return false;
    return AdjacencyMatrix[Node1][Node2]==1;
}
 
uint Graph::noOfEdges() {
    uint cnt = 0;
    for (uint i = 0; i < mNoOfNodes; i++){
        for(uint e=0; e<mNoOfNodes; e++){
            if(AdjacencyMatrix[i][e]==1) cnt++;
    }
    }
    return cnt / 2;
}
uint Graph::noOfNodes() {
    return mNoOfNodes;
}
 
int Graph::maxGrad() {
 
}
 
int Graph::minGrad(){
 
}
 
bool Graph::reachable(uint Node1, uint Node2){
 
}
 
void Graph::printGraph(){
    if (noOfNodes() == 0) return;
    cout<<"Anzahl der Knoten: "<<noOfNodes()<<endl;
    cout<<"Anzahl der Kanten: "<<noOfNodes()<<endl;
    cout<<"Maxgrad: "<<maxGrad()<<endl;
    cout<<"Mingrad: "<<minGrad()<<endl;
    for(uint z=0; AdjacencyMatrix[z]!=0; z++){
    cout<<"Knoten "<<z+1<<" ist verbunden mit den/dem Knoten: ";
    for(uint e=0; AdjacencyMatrix[e]!=0; e++){
            if(AdjacencyMatrix[z][e]==1) cout<<e+1<<"  ";
            }
    cout<<endl;
    }
    cout<<endl;
    cout<<endl;
}
 
int main() {
    
    //Statt a, b, c... wird 1, 2, 3... verwendet
 
    Graph b(8);
    cout << "Beispiel b):" << endl;
    uint n = b.noOfNodes();
    for (uint i = 0; i < n; i++)
    b.addEdge(i, (i+1) % n);
    if (b.hasEdge(3,4))
    cout << "Kante (3,4) existiert!" << endl;
    else cout << "Kante (3,4) existiert nicht!" << endl;
    b.maxGrad();
    b.minGrad();
    b.printGraph();
 
    Graph a(7);
    cout << "Beispiel a):" << endl;
    uint f = a.noOfNodes();
    a.addEdge(0, 2);
    a.addEdge(2, 1);
    a.addEdge(1, 6);
    a.addEdge(2, 4);
    a.addEdge(6, 5);
    a.addEdge(5, 4);
    a.addEdge(4, 3);
    a.addEdge(5, 3);
    if (a.hasEdge(0,5))
    cout << "Kante (0,5) existiert!" << endl;
    else cout << "Kante (0,5) existiert nicht!" << endl;
    a.maxGrad();
    a.minGrad();
    a.printGraph();
    return 0;
}
подскажите пожалуйста, кто как может! задание сдавать во вторник (я студент). Заранее благодарю!
PS: не удивляйтесь, что выводы на немецком.
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
17.04.2012, 11:51     Графы (с++) #10
Добрый день форумчяни, с этим я разобрался, с теорией, могу даже по графу в ручную написать матрицы смежности и инцидентности, Ни как не могу придумать алгоритм построения матрицы инцидентности используя матрицу смежности. Подскажите алгоритм, за ранние спасибо!
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
17.04.2012, 15:22     Графы (с++) #11
Вот таким образом изображается матрица инцидентности
А вот как реализовать! не как не могу придумать
Миниатюры
Графы (с++)  
Shved
9 / 9 / 1
Регистрация: 07.06.2009
Сообщений: 34
17.04.2012, 16:18     Графы (с++) #12
Путь от узла к узлу читай Алгоритм Дейкстры. Для ориентированых графов находит кратчайшее расстояние от одного узла до указанного.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
17.04.2012, 16:24     Графы (с++) #13
Цитата Сообщение от gorin Посмотреть сообщение
Вот таким образом изображается матрица инцидентности
А вот как реализовать! не как не могу придумать
Если в v3 петля, то построить матрицу инцидентности нельзя.
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
17.04.2012, 16:34     Графы (с++) #14
Shved, что то в интернете не могу найти этот алгоритм

Добавлено через 1 минуту
Nekto, я в этом не ас, не знаю препод приводил такой пример!

Добавлено через 2 минуты
Shved, нашол!

Добавлено через 4 минуты
Shved, мне не нужно кратчайший путь найти нужно просто матрицу инцидентности найти!
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
17.04.2012, 16:39     Графы (с++) #15
Цитата Сообщение от gorin Посмотреть сообщение
Shved, что то в интернете не могу найти этот алгоритм

Добавлено через 1 минуту
Nekto, я в этом не ас, не знаю препод приводил такой пример!
идёшь по строкам матрицы. Находишь ребро в строке i, столбце j, записываешь в матрицу инцидентности в столбец k в строке i -1, столбец k, строка j 1. Увеличиваешь k на 1, продолжаешь цикл.
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
17.04.2012, 16:41     Графы (с++) #16
Nekto, можно маленький примерчик?
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
17.04.2012, 17:33     Графы (с++) #17
Цитата Сообщение от gorin Посмотреть сообщение
Nekto, можно маленький примерчик?
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
#include <iostream>
using namespace std;
int main()
{
 int rows,cols;
 cout<<"Rows: ";
 cin>>rows;
 cout<<"Cols: ";
 cin>>cols;
 int i,j,k=0;
 int vcount=0;
 int **matrix=new int*[rows];
 for (i=0;i<rows;i++) 
  matrix[i]=new int[cols];
 for (i=0;i<rows;i++)
  for (j=0;j<cols;j++)
   {
    if (i!=j)
     {
      cout<<"a["<<i<<"]["<<j<<"]=";
      cin>>matrix[i][j];
      if (matrix[i][j]!=0) vcount++; 
     }
    else matrix[i][j]=0;
   }
 int **vmatrix=new int*[rows];
 for (i=0;i<rows;i++) 
  {
   vmatrix[i]=new int[vcount];
   for (j=0;j<vcount;j++)
    vmatrix[i][j]=0;
  }
 for (i=0;i<rows;i++)
  {
   for (j=0;j<cols;j++)
    {
     if (matrix[i][j]!=0)
      {
       vmatrix[i][k]=-1;
       vmatrix[j][k]=1;
       k++;
      }
    }
  }
 cout<<endl<<endl;
 for (i=0;i<rows;i++)
  {
   for (j=0;j<vcount;j++)
    {
     cout<<vmatrix[i][j]<<" ";
    } 
   cout<<endl;
  }
 system("pause");
 return 0;
}
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
17.04.2012, 17:54     Графы (с++) #18
Nekto, Как то неправильно переводит в матрицу инцидентности!
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
17.04.2012, 17:55     Графы (с++) #19
Цитата Сообщение от gorin Посмотреть сообщение
Nekto, Как то неправильно переводит в матрицу инцидентности!
Почему? Для ориентированного графа строит верно.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.04.2012, 17:59     Графы (с++)
Еще ссылки по теме:

Графы C++
C++ Графы
C++ Графы
Графы C++
C++ С++ и графы

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

Или воспользуйтесь поиском по форуму:
gorin
207 / 14 / 2
Регистрация: 18.08.2009
Сообщений: 571
17.04.2012, 17:59     Графы (с++) #20
Nekto, Ну смотри Ориентированый граф - это когда по обе стороны диагонали матрицы смежности (количество "1" равны), так?
Yandex
Объявления
17.04.2012, 17:59     Графы (с++)
Ответ Создать тему
Опции темы

Текущее время: 13:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru