图论——邻接表表示法 图的遍历(深度优先搜索和广度优先搜索)

1·图的建立

邻接法表示法：

对于图中的每个节点Vi,建立一个单链表,把与Vi相邻的节点放入这个链表中；

该表有三部分组成:

(1):    point结构体,由节点的位置,边的信息(例如边的权值),下个节点的地址构成；

(2):     firstpoint结构体,即单链表的首节点,主要由节点的数据,与首节点连接的第一个节点的地址构成;

(3):    graphy结构体,主要由所有节点构成的数组,图的节点总数和边的总数构成;

代码:

#include <iostream>
using namespace std;

typedef struct point{
    int position;                   //首节点的位置
    int otherimfor;                 //与边相关的信息,例如边的权值;
    struct point *nextnode;
}point;
typedef struct firstpoint{
    int data;
    point *next;
}firstpoint,manypoints[100];
typedef struct graph{
    manypoints p;
    int pointnum,sidenum;
}graph;
void createWuXianggraph(graph &g,int v,int e){            //无向图
    g.pointnum=v;   g.sidenum=e;
    for(int i=1;i<=v;i++)
    {
        cin>>g.p[i].data;
        g.p[i].next=NULL;
    }   int v1,v2;
    for(int i=0;i<e;i++)
    {
        cin>>v1>>v2;
        int po1=v1,po2=v2;
        point *p=new point;
        p->position=po2;
        p->nextnode=g.p[po1].next;   g.p[po1].next=p;
        point *pp=new point;
        pp->position=po1;
        pp->nextnode=g.p[po2].next;  g.p[po2].next=pp;
    }
}


void createYouXianggraph(graph &g,int v,int e){            //有向图
      g.pointnum=v;   g.sidenum=e;
    for(int i=1;i<=v;i++)
    {
        cin>>g.p[i].data;
        g.p[i].next=NULL;
    }   int v1,v2;
    for(int i=0;i<e;i++)
    {
        cin>>v1>>v2;
        int po1=v1,po2=v2;
        point *p=new point;
        p->position=po2;
        p->nextnode=g.p[po1].next;   g.p[po1].next=p;
    }
}
void showgraph(graph g){
    for(int i=0;i<g.pointnum;i++)
    {
        cout<<"V"<<g.p[i].data;
        point *p=new point;
        p=g.p[i].next;
        if(p)   cout<<"->";
        while(p)
        {
            cout<<p->position;
            if(p->nextnode) cout<<"->";
            p=p->nextnode;
        }   cout<<endl;
    }
}

int main(){
    graph g;
    int v,e;
    while(cin>>v>>e)
    {
        creategraph(g,v,e);
        showgraph(g);
    }
}

2·图的遍历:

深度优先搜索,类似与树的先序遍历:

数组visited用来记录每个点是否被访问

函数 firstvisitpoint(g,v)用于查找在链表中与每个顶点相邻的第一个点,并返回其位置;

函数 nextvistpoint（g,v)用于查找在链表中每个顶点相邻的且没被访问的点,并返回其位置;

int visited[100];

int firstvisitpoint(graph g,int v){
    return g.p[v].next->position;
}
int nextvistpoint(graph g,int v){ 
    point *tmp=g.p[v].next; 
    while(tmp){ 
        if(!visited[tmp->position]) 
            return tmp->position; 
        tmp=tmp->nextnode; 
    } return -1;}
void dfs(graph g,int v,int visited[100]){ 
    cout<<g.p[v].data<<" "; 
    visited[v]=1; 
    point *p=g.p[v].next; 
    while(p){ 
        int vv=p->position; 
        if(!visited[vv]) 
            dfs(g,vv,visited); 
        p=p->nextnode; 
    }
}

int main(){
    graph g;
    int v,e;            //图的点和边的总数;
    while(cin>>v>>e)
    {
        for(int i=1;i<=v;i++)
        visited[i]=0;
        createYouXianggraph(g,v,e);
        showgraph(g);
        dfs(g,1,visited);        cout<<endl;
    }
}

 

广度优先搜素:

 

从某顶点v开始访问,依此访问v的未被访问的邻接点,并在访问的过程中将这些点存进队列.

将队列里的元素vi依此弹出,访问vi的未被访问的邻接点,并在访问的过程中将这些点存进队列.

重复上一行的操作,直至队列元素为空

typedef struct List{
    int num;
    struct List *next;
}List,*PList;
typedef struct{
    List *head,*tail;
}Queue;
void InitQueue(Queue &q){
    q.head=q.tail=new List;
    q.head->next=NULL;
}

void Push(Queue &q,int x){
    PList tmp=new List;
    tmp->num=x;         tmp->next=NULL;
    q.tail->next=tmp;   q.tail=tmp;
}

void Pop(Queue &q,int &x){
    PList tmp=q.head->next;
    x=tmp->num;
    q.head->next=tmp->next;
    if(tmp==q.tail)     q.tail=q.head;
    delete tmp;
}
int firstvisitpoint(graph g,int v){
    return g.p[v].next->position;
}

int nextvistpoint(graph g,int v){
        point *tmp=g.p[v].next;
        while(tmp)
        {
            if(!visited[tmp->position])
                return tmp->position;
            tmp=tmp->nextnode;
        }
        return -1;
}

void bfs(graph g,int v,int visited[100]){
    Queue q;    InitQueue(q);   Push(q,v);   visited[v]=1;
     cout<<g.p[v].data<<" ";

    while(!IsEmpty(q))
    {
        int x;          Pop(q,x);
        for(int i=firstvisitpoint(g,x);i>=1;i=nextvistpoint(g,x))
        {
            if(!visited[i])
            {
                 cout<<g.p[i].data<<" ";
                 Push(q,i);
                 visited[i]=1;
            }
        }
    }
}
int main(){
    graph g;
    int v,e;
    while(cin>>v>>e)
    {
        for(int i=1;i<=v;i++)
        visited[i]=0;
        createYouXianggraph(g,v,e);
        showgraph(g);
        bfs(g,1,visited);        cout<<endl;
    }
}