граф

[Гост]

Да се състави функция, която показва и преброява всички върхове само с по една входяща дъга. ПОМОЩ моляяя

[Добромир Глухаров]

Ако графът е даден с матрица за съседство:

Код: Избери целия код

#include <iostream>

using namespace std;

int V[10][10]={
                {0,1,0,1,1,0,0,0,0,1},
                {1,0,1,0,0,0,1,0,1,0},
                {0,1,0,0,0,1,0,0,0,0},
                {1,1,1,0,0,1,1,0,0,1},
                {0,0,1,1,0,1,1,0,0,0},
                {1,1,1,0,0,0,1,1,0,0},
                {0,0,0,0,0,0,0,0,0,0},
                {1,1,0,0,0,1,1,0,1,0},
                {0,1,0,1,0,1,0,0,0,1},
                {1,0,1,0,0,0,1,0,1,0},
                                        };

void prebr_varh_s1_vhod_daga()
{
    int r,c,br_vh_d,br=0;
    for(c=0;c<10;c++)
    {
        br_vh_d=0;
        for(r=0;r<10;r++)
            if(V[r][c]) br_vh_d++;
        if(br_vh_d==1)
        {
            cout<<1+c<<" ";
            br++;
        }
    }
    cout<<endl<<br<<endl;
}

int main()
{
    prebr_varh_s1_vhod_daga();
    return 0;
}


Ако е даден със свързан списък, трябва да се обходи рекурсивно и да се преброят върховете със само едно изходящо ребро, но е трудно да се предпазим от зацикляне - трябва да маркираме върховете, през които минаваме, за да не ги повторим. Дадена ли е структурата на свързания списък?

[Гост]

Имам следната основа на код
#include<iostream>
using namespace std;

const int n = 10;
struct elem {
char key;
elem *next;
}*g[n];

void init(elem *g[n]) {
for (int i = 0; i < n; i++)
g[i] = NULL;
}

void list(elem *g[n])
{
for (int i = 0; i<n; i++)
{
if (g[i])
{
elem *p = g[i];
while (p)
{
cout << p->key << "\t";
p = p->next;
}
cout << endl;
}
}
if (!g[0])
{
cout << "nqma";
}
}

int srch_node(char c, elem *g[n]) {
int flag = 0;
for(int i=0;i<n;i++)
if (g[i])
if(g[i]->key==c)
flag = 1;
return flag;
}

int srch_arc(char c1, char c2, elem *g[n]) {
int flag = 0;
if(srch_node(c1,g)&&srch_node(c2,g))
{
int i = 0;
while (g[i] == NULL || g[i]->key != c1) i++;
elem *p = g[i];
while (p->key != c2&&p->next)
p = p->next;
if(p->key==c2)
flag = 1;
}
return flag;
}
void add_node(char c, elem*g[n]) {
if (srch_node(c,g))
cout << "\n Existing node";
else {
int i = 0;
while (g[i] && (i < n)) i++;
if (g[i] == NULL)
{
g[i] = new elem;
g[i]->key = c;
g[i]->next = NULL;
}
else
cout << "\n Overflow";
}
}

void add_arc(char c1, char c2, elem *g[n]) {
if(srch_arc(c1,c2,g))
cout << "\n Existing arc";
else
{
if (!srch_node(c1, g))
add_node(c1, g);
if (!srch_node(c2, g))
add_node(c2, g);
if(srch_node(c1,g)&&srch_node(c2,g))
{
int i = 0;
while (g[i] == NULL || g[i]->key != c1) i++;
elem *p = new elem;
p->key = c2;
p->next = g[i]->next;
g[i]->next = p;
}
}
}


Трябва само да се направи функцията която показва и преброява всички върхове само с по една входяща дъга..Евентуално и мейн функцията която трябва да е с меню..Ако някой ми помогне ще съм много благодарен