VPF::доказать, что граф связный - Форум программистов

4aineG

Дата 23.8.2008, 11:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 32
Регистрация: 7.8.2008

Репутация: нет
Всего: нет

Добрый день, Уважаемые эксперты!
Помогите пожалуйста
Задание: дан граф, доказать, что он связный
Ошибок не выдает порсто мигание курсора на черном экране и ничего не происходит
Ошибок в списке и очереди вроде как нет, скорее всего в Graph.h
И еще связный граф вроде как не должен содержать циклов
Тогда может внести изменения в BreadthFirstSearch

Код


#pragma once
#include <iostream>
using namespace std;

struct Link
{
    int data;
    Link *pNext;
};

struct List
{
    Link *pHead;
};

void InitList(List *pList)
{
    pList->pHead = 0;
}

bool IsEmpty(List *pList)
{
    if (pList->pHead == 0)
        return true;
    else
        return false;
}

Link *GoBack(List *pList)
{
    if (IsEmpty(pList))
        return 0;
    Link *pLink = pList->pHead;
    while (pLink->pNext != 0)
        pLink = pLink->pNext;
    return pLink;
}

void PushBack(List* pList, int data)
{
    Link* pLink = new Link();
    pLink->data = data;
    pLink->pNext = 0;

    if (!IsEmpty(pList))
    {
        Link* pLastLink = GoBack(pList);
        pLastLink->pNext = pLink;
    }
    else
        pList->pHead = pLink;
}

int GetFrontData(List *pList)
{
    Link *pLink = pList->pHead;
    return pLink->data;
}

void DeleteFront(List* pList)
{
    if (IsEmpty(pList))
        return;

    Link* pAfterHead = pList->pHead->pNext;
    delete pList->pHead;
    pList->pHead = pAfterHead;
}

    
void PrintList(List *pList)
{
    Link *pCurLink = pList->pHead;

    while(pCurLink != 0)
    {
        cout << pCurLink->data << "->";
        pCurLink = pCurLink->pNext;
    }
}

int ElementsCount(List* pList)
{
    Link* pLink = pList->pHead;

    int count = 0;
    while (pLink != 0)
    {
        count++;
        pLink = pLink->pNext;
    }

    return count;
}

void ClearList(List *pList)
{
    Link *pLink = pList->pHead;
    while(pLink != 0)
    {
        Link *pNextLink = pLink->pNext;
        delete pLink;
        pLink = pNextLink;
    }
    pList->pHead = 0;
}

#pragma once
#include "List.h"

class Queue
{
private:

    List *pList;
        
public:

    Queue()
    {
        this->pList=new List();
        InitList(this->pList);
    }

    bool IsEmpty()
    {
        return (::IsEmpty(this->pList));
    }

    void Enqueue(int data)
    {
        PushBack(this->pList, data);
    }

    int Dequeue()
    {
        int temp = GetFrontData(this->pList);
        DeleteFront(this->pList);
        cout << temp <<endl;
        return temp;
    }

    void PrintQueue()
    {
        PrintList(this->pList);
    }

    ~Queue()
    {
        ClearList(this->pList);
    }
};


#pragma once
#include "Queue.h"

class Graph
{

private:

    int V;
    int **E;
    List* pResList;

public:

    Graph(int Vcount)
    {
        E = new int *[V];
        for (int i=0; i<V; i++)
        {
            E[i] = new int[V];
            for (int j=0; i<V; j++)
                E[i][j]=0;
        }
    }

    void AddEdge(int i, int j)
    {
        E[i][j]=1;
        E[j][i]=1;
    }

    bool IsAdjacent(int i, int j)
    {
        if(E[i][j] == 1)
            return true;
        else 
            return false;
    }

    void BreadthFirstSearch(int vertex)
    {
        bool* visited = new bool[V];
        for(int i=0; i<V; i++)
            visited[i] = false;
        Queue que;
        que.Enqueue(vertex);
        visited[vertex]=true;
        while (que.IsEmpty() != true)
        {
            int temp = que.Dequeue();
            PushBack(pResList, temp);
            for(int i=0; i<V; i++)
            if((IsAdjacent(temp, i)) && (visited[i] == false))
            {
                que.Enqueue(i);
                visited[i]=true;
            }
        }
        delete [] visited;
    }

    bool FromAnyVertex()
    {
        int Vcount = ElementsCount(pResList);
        if (Vcount == V)
            return true;
        else
            return false;
    }

    void PrintGraph()
    {
        PrintList(pResList);
    }

    ~Graph()
    {
        delete [] E;
        ClearList(pResList); 
    }

};
#pragma once
#include "List.h"
#include "Queue.h"
#include "Graph.h"

int main()
{
    Graph gr(10);
    gr.AddEdge(1,2);
    gr.AddEdge(2,4);
    gr.AddEdge(2,3);
      gr.AddEdge(3,5);
    gr.AddEdge(3,6);
    gr.AddEdge(4,10);
    gr.AddEdge(4,8);
    gr.AddEdge(8,7);
    gr.AddEdge(8,9);
    gr.BreadthFirstSearch(1);

    gr.PrintGraph();
    if(gr.FromAnyVertex())
        cout << "Graph is coherent";
    else
        cout << "Graph is not coherent";

    return 0;
}

заранее благодарю за помощь smile

KEHT

Дата 24.8.2008, 15:49 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 67
Регистрация: 17.7.2006

Репутация: нет
Всего: 1

1) В конструкторе Graph надо было инициализировать V

Код


    Graph(int Vcount)
    {
        V=Vcount;
        E = new int *[V];
        for (int i=0; i<V; i++)
        {
            E[i] = new int[V];
            for(int j=0;j<V;j++){
                E[i][j]=0;
            }
        }
    }
    vo

Код


 gr.AddEdge(4,10);

Тут вы выходите за пределы объявленного массива.

4aineG

Дата 26.8.2008, 12:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 32
Регистрация: 7.8.2008

Репутация: нет
Всего: нет

не много переделал, но почему то всегда распечатывает "It is not connected graph", может мне в BFS что нибудь поменять, подскажите пожалуйста

Код



#pragma once
#include <iostream>
using namespace std;

struct Link
{
    int data;
    Link *pNext;
};

struct List
{
    Link *pHead;
};

void InitList(List *pList)
{
    pList->pHead = 0;
}

bool IsEmpty(List *pList)
{
    return (pList->pHead == 0);
}

Link *GoBack(List *pList)
{
    if (IsEmpty(pList))
        return 0;
    Link *pLink = pList->pHead;
    while (pLink->pNext != 0)
        pLink = pLink->pNext;
    return pLink;
}

void PushBack(List* pList, int data)
{
    Link* pLink = new Link();
    pLink->data = data;
    pLink->pNext = 0;

    if (!IsEmpty(pList))
    {
        Link* pLastLink = GoBack(pList);
        pLastLink->pNext = pLink;
    }
    else
        pList->pHead = pLink;
}

int GetFrontData(List *pList)
{
    Link *pLink = pList->pHead;
    return pLink->data;
}

void DeleteFront(List* pList)
{
    if (IsEmpty(pList))
        return;

    Link* pAfterHead = pList->pHead->pNext;
    delete pList->pHead;
    pList->pHead = pAfterHead;
}

    
void PrintList(List *pList)
{
    Link *pCurLink = pList->pHead;

    while(pCurLink != 0)
    {
        cout << pCurLink->data << "->";
        pCurLink = pCurLink->pNext;
    }
}

int ElementsCount(List* pList)
{
    Link* pLink = pList->pHead;

    int count = 0;
    while (pLink != 0)
    {
        count++;
        pLink = pLink->pNext;
    }

    return count;
}

void ClearList(List *pList)
{
    Link *pLink = pList->pHead;
    while(pLink != 0)
    {
        Link *pNextLink = pLink->pNext;
        delete pLink;
        pLink = pNextLink;
    }
    pList->pHead = 0;
}


#pragma once
#include "List.h"

class Queue
{
private:

    List *pList;
        
public:

    Queue()
    {
        pList=new List();
        InitList(pList);
    }

    bool QIsEmpty()
    {
        return (IsEmpty(pList));
    }

    int CountQueueElements() 
    {
        return ElementsCount(pList);
    }

    void Enqueue(int data)
    {
        PushBack(pList, data);
    }

    int Dequeue()
    {
        int temp = GetFrontData(pList);
        DeleteFront(pList);
        return temp;
    }

    void PrintQueue()
    {
        PrintList(pList);
    }

    ~Queue()
    {
        ClearList(pList);
    }
};


#pragma once
#include "Queue.h"

class Graph
{

private:

    int V;
    int **E;
    Queue qres;  // основной список
    Queue qex;  // дополнительный для проверки связности графа

public:

    Graph(int Vcount)
    {
        V = Vcount;
        E = new int *[V];
        for (int i=0; i<V; i++)
        {
            E[i] = new int[V];
            for (int j=0; j<V; j++)
                E[i][j]=0;
        }

    }

    void AddEdge(int i, int j)
    {
        E[i][j]=1;
        E[j][i]=1;
    }

    bool IsAdjacent(int i, int j)
    {
        return (E[i][j]==1);
    }

    void BreadthFirstSearch(int vertex)
    {
        bool* visited = new bool[V];
        for(int i=0; i<V; i++)
            visited[i] = false;
        Queue que;
        que.Enqueue(vertex);
        while (que.QIsEmpty() != true)
        {
            int temp = que.Dequeue();
            visited[temp] = true;
            qres.Enqueue(temp);
            for (int i=0; i<V; i++)
            {
                if (visited[i] == true) 
                    qex.Enqueue(i);
                if (IsAdjacent(temp, i) && (visited[i] == false))
                    que.Enqueue(i);
               
            }
        }
        delete [] visited;
    } 

    int GraphCountElements()
    {
        int c1 = qex.CountQueueElements();
        int c2 = qres.CountQueueElements();
        int sum = c1 + c2;
        return sum;
    }

    bool IsConected()
    {
        int Vc = GraphCountElements();
        if ((qex.QIsEmpty()) && (Vc == V))
            return true;
        else 
            return false;
    }

    void PrintGraph()
    {
        qres.PrintQueue();
        cout << endl;
    }

    ~Graph()
    {
        delete [] E;
    }

};



#pragma once
#include "List.h"
#include "Queue.h"
#include "Graph.h"



void main()
{

    
    Graph g(4);
    g.AddEdge(0, 1);
    g.AddEdge(1, 2);
    g.AddEdge(2, 3);
    
    g.BreadthFirstSearch(0);

    g.PrintGraph();

    g.GraphCountElements();


    if(g.IsConected())
        cout << "It's connected graph" << endl;
    else
        cout << "It is not connected graph" << endl; 
                                         
}

Это сообщение отредактировал(а) 4aineG - 26.8.2008, 19:48

NoliX

Дата 29.8.2008, 12:10 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 103
Регистрация: 5.7.2005

Репутация: 1
Всего: 1

я бы делал через матрицу смежности, рекурсивно и никаких обьектов, списков и прочего не нужно

Код


#include "stdafx.h"


bool Matr[7][7] = {
        {false, true, false, false, false, false, true},
        {true, false, true, false, true, true, false},
        {false, true, false, false, true, false, false},
        {false, false, false, false, true, false, false},
        {false, true, true, true, false, false, false},
        {false, true, false, false, false, false, false},
        {true, false, false, false, false, false, false}
                    };

bool MatrTmp[7] = {false, false, false, false, false, false, false};

void run(unsigned int pos){
    MatrTmp[pos]=true;
    for (int i=0;i<7;i++)
        if (Matr[i][pos] && !MatrTmp[i])
            run(i);
}

bool isConnected(){
    run(0);
    for (int i=0;i<7;i++)
        if (!MatrTmp[i]) 
            return false;
return true;
}


int _tmain(int argc, _TCHAR* argv[]){

    if(isConnected())
         printf("It's connected graph");
     else
         printf("It is not connected graph");
}

с вводом особо не запаривался.
Суть алгоритма такова:
по скольку связный граф - граф у которого одна компонента связности, значит из любой вершины можно попасть в любую, попробуем попасть из вершины A, тоесть самой первой, ходим по вершинам и помечаем в массиве MatrTmp вершины в которых были, ходим только в те, в которые можем пройти и которые не помечены, после прогонки смотрим, все ли вершины помечены, если все, то связный, если не все, то значит несколько компонент свзяности

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

Вот она, сила оптимизации, а то структуры, указатели, чем проще, тем быстрее)

Это сообщение отредактировал(а) NoliX - 29.8.2008, 13:00

--------------------

Опыт - это учитель, который очень дорого берет за свои уроки

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »