首页 > 代码库 > 临接表

临接表

2024-07-10 04:07:24   210人阅读

（2）邻接表

  • 邻接表的C语言描述

  • 基本运算的算法——建立无向网的邻接表、求图中与顶点i邻接的第一个顶点、求图中顶点i相对于顶点j的下一个邻接点、若图G中存在顶点u，则返回该顶点在图中的位置、图的广度优先遍历、图的深度优先遍历2.

 

#include<iostream>#include<string.h>using namespace std;class linjiebiao{public:    struct Node    {        int data;        Node * next;        int flag;        Node ():next(NULL) {}        Node (int a,int b):data(a),flag(b),next(NULL) {}    };    Node * ljbsz;    Node * cur;    int *visit;    int maxsize;    linjiebiao(int tem = 10)    {        maxsize = tem;        ljbsz = new Node[maxsize];        for(int i = 0 ; i < maxsize ; i++)        {            ljbsz[i].data = http://www.mamicode.com/i;"please input "<<i<<" point"<<endl;            cur = &ljbsz[i];            while(1)            {                int tem;                cin>>tem;                if(tem==-1)                {                    cur -> next = NULL;                    break;                }                else                {                    Node * temnode = new Node(tem,1);                    cur -> next = temnode;                    cur = cur -> next;                }            }            cur = ljbsz;        }    }    void print()    {        for(int i = 0 ; i < maxsize ; i++)        {            cur = &ljbsz[i];            cur = cur -> next;            while(cur!= NULL)            {                if(cur -> flag==1)cout<<cur->data<<" ";                cur = cur -> next;            }            cout<<endl;        }    }    void chazhaodian(int a)//求图中与顶点i邻接的第一个顶点    {        cout<<ljbsz[a-1].next -> data<<endl;    }    void chazhaoweizhi(int a)//若图G中存在顶点u，则返回该顶点在图中的位置    {        cur = &ljbsz[a];        cur = cur -> next;        cout<<"yu "<<a<<" xiang lin de dian you:"<<endl;        while(cur != NULL)        {            cout<<cur->data<<" ";            cur = cur -> next;        }    }    void dfs(Node * tem)    {        if(tem -> flag==1)cout<<tem->data<<" ";        while(tem != NULL)        {            if(tem->next!=NULL&&visit[tem->data]==0)            {                visit[tem->data] = 1;                dfs(tem->next);            }            tem = tem -> next;        }    }    void bfs()    {        cout<<"begining bfs!!!!!!!!!!!!!!!!!!!!!!!"<<endl;        int temsz[maxsize+1];        int Front;        int rear;        memset( visit , 0 , sizeof(int)*maxsize);        temsz[0] = 0;        Front = temsz[0];        rear = Front + 1;        visit[0] = 1;        cout<<temsz[0]<<" ";        while(Front != rear)        {            cur = ljbsz[Front].next;            while ( cur != NULL)            {                if(visit[cur->data]==0)                {                    cout<<cur -> data<<" ";                    temsz[rear++] = cur -> data;                    visit[cur->data] = 1;                }                cur = cur -> next;            }            Front ++;        }    }};int main(){    int j = 3;    linjiebiao duskcl(j);    duskcl.creat();    int tem = 2;    //duskcl.chazhaodian(2);    //duskcl.chazhaoweizhi(tem);    //duskcl.dfs(duskcl.cur);    //duskcl.print();    duskcl.bfs();}

 

　　

 


联系
我们