Đồ thị: Cài đặt bằng danh sách liên kết + DFT + BFT

[xwaystyle]

Đây là bài đồ thị, được mình cài đặt bằng danh sách liên kết.
Có hai hàm duyệt đồ thị bằng phương pháp đệ qui:
-DFT (Depth First Traverse): Duyệt theo chiều sâu
-BFT (Breadth First Traverse): Duyệt theo chiều rộng
Code viết bằng borland C++.

#include <iostream.h>#include <conio.h>#include <stdio.h>#include <stdlib.h> #define max_member 100class graph;class list;class node{        int data; // chua vi tri cua dinh lien ket thu data tren mang cac danh sach head        node *next;    public:        node(int a=-1)            {                data = a;                next = 0;            }        friend class list;        friend class graph;}; class list{        node *head;    public:        list()            {                head = 0;            }        ~list()            {                while(head)                    {                        node *temp= head;                        head = head->next;                        delete temp;                    }            }        bool set_contact(int a)            {                node *p= new node(a);                if(!p)                    return false;                if(!head)                    head = p;                else                    {                        node *temp = head;                        while(temp->next&&temp->next->data>a)                            {                                if(temp->data == a)                                    return false;                                temp = temp->next;                            }                        p->next = temp->next;                        temp->next = p;                    }                return true;            }        bool remove_contact(int a)            {                if(head)                {                    node *temp = head;                    if(temp->data == a)                        {                            head = head->next;                            delete temp;                            return true;                        }                    else                        while(temp)                            {                                if(temp->next->data ==a)                                    {                                        node *p = temp->next;                                        temp = temp->next->next;                                        delete p;                                        return true;                                    }                                temp = temp->next;                            }                }                return false;            }        void view_contact()const            {                if(head)                {                    node *temp = head->next;                    cout<<"Dinh : "<<(head->data+1)<<"\t";                    while(temp)                    {                        cout<<(head->data+1)<<"-"<<(temp->data+1)<<"     ";                        temp = temp->next;                    }                    cout<<endl;                }            }        friend class graph;        list operator = (const list &a)            {                if(head)                {                    while(head)                    {                        node *temp= head;                        head = head->next;                        delete temp;                    }                    head = 0;                }                if(a.head)                {                    head = new node(a.head->data);                    node *p =head, *q=a.head->next;                    while(q)                        {                            p->next = new node(q->data);                            p=p->next;                            q=q->next;                        }                }                return *this;            }}; class graph{        list rank[max_member];        int member;    public:        graph()            {                member = -1;            }        void set_member(int a)            {                member = a;                for(int i=0;i<a;i++)                    {                        rank[i].head= new node(i);                    }            }        void insert_member()            {                member++;            }        void remove_member(int a)            {            a--;                if(a<=member&&a>=0)                {                    for(int i=0;i<=member;i++)                        if(i!=a)                            rank[i].remove_contact(a);                    for(int i=a;i<member;i++)                        rank[i]=rank[i+1];                    rank[member].~list();                    member--;                }            }        void add_contact(int a,int b)            {            a--;b--;                if(a<=member&&a>=0)                {                    rank[a].set_contact(b);                }            }        void remove_contact(int a,int b)            {            a--;b--;                if(a<=member&&a>=0)                {                    rank[a].remove_contact(b);                }            }        void view_graph()const            {                if(member>=0)                    {                        for(int i = 0;i<=member;i++)                        {                                                   rank[i].view_contact();                        }                    }            }        void dft_graph()const            {                bool check[max_member];                for(int i=0;i<=member;i++)                    check[i]=false;                for(int i=0;i<member;i++)                    {                        if(!check[i])                            {                                if(i<member&&i>0)cout<<" -> ";cout<<(i+1);                                dft_func(i,check);                            }                    }            }        void dft_func(int i,bool check[])const            {                check[i] = true;                node *temp = 0;                if(rank[i].head->next)                    temp = rank[i].head->next;                else                    return;                while(temp)                    {                        if(!check[temp->data])                            {                                cout<<" -> "<<(temp->data+1);                                dft_func(temp->data,check);                            }                        temp = temp->next;                    }            }        void bft_graph()const            {                bool check[max_member],read[max_member];                for(int i=0;i<=member;i++)                    check[i]=read[i]=false;                for(int i=0;i<member;i++)                    {                        if(!check[i])                            {                                if(i<member&&i>0)cout<<" -> ";cout<<(i+1);                                check[i]=true;                                node *temp = rank[i].head->next;                                while(temp)                                    {                                        cout<<" -> "<<(temp->data+1);                                        read[temp->data]=true;                                        temp = temp->next;                                    }                                temp = rank[i].head->next;                                while(temp)                                    {                                        if(!check[temp->data])                                            bft_func(temp->data,check,read);                                         temp=temp->next;                                    }                            }                    }            }        void bft_func(int i,bool check[],bool read[])const            {                check[i] = true;                node *temp = 0;                        if(rank[i].head->next)                    temp = rank[i].head->next;                else                    return;                while(temp)                    {                        if(!check[temp->data]&&!read[temp->data])                            {                                cout<<" -> "<<(temp->data+1);                                bft_func(temp->data,check,read);                            }                        temp = temp->next;                    }            }}; void main(){    graph a;    int n,m;    /*cout<<"\n Moi nhap so dinh cua do thi: ";cin>>n;    a.set_member(n);    cout<<"\n Nhap vao -1 de thoat.\n";    while(1)    {        cout<<"\n Nhap vao dinh xet moi quan he:";cin>>n;        cout<<" Co quan he voi dinh: "; cin>>m;        if(n<0||m<0)            break;        else            a.add_contact(n,m);    }    clrscr();*/    a.set_member(7);    a.add_contact(1,5);    a.add_contact(1,2);    a.add_contact(2,5);    a.add_contact(2,4);    a.add_contact(5,3);    a.add_contact(4,3);    a.add_contact(5,7);    a.add_contact(5,6);    a.add_contact(7,6);    a.add_contact(6,3);   a.add_contact(3,4);   a.add_contact(5,2);    a.add_contact(5,4);   a.add_contact(4,2);   a.add_contact(1,7);/*  a.set_member(5);    a.add_contact(1,2);    a.add_contact(1,4);    a.add_contact(1,5);    a.add_contact(2,1);    a.add_contact(2,3);    a.add_contact(2,4);    a.add_contact(2,5);    a.add_contact(3,2);    a.add_contact(3,4);    a.add_contact(4,1);    a.add_contact(4,2);    a.add_contact(4,3);    a.add_contact(4,5);    a.add_contact(5,1);    a.add_contact(5,2);    a.add_contact(5,4);*/        cout<<"\n Cac moi quan he tren do thi vua nhap la: \n\n";    a.view_graph();    cout<<"\n\n Duyet DFT \n";    a.dft_graph();    cout<<"\n\n Duyet BFT \n";    a.bft_graph();    getch();}

Và ví dụ kèm theo ( +code)

[andy_lau]

Em đang làm bài tập này , lên mạng kiếm thử thì tìm dc. kết quả này ^^ , anh ơi , anh vui lòng giải thích thêm để em hiểu về các hàm với :"> thanks anh !

[teenylove]

hiểu rồi không hỏi nữa nên em edit lại ^^