本文共 2099 字，大约阅读时间需要 6 分钟。

菜鸟生成记(47)

有时候真的不是别人代码写的晦涩难懂,而是我的知识储备太少;时隔2个月蒻羁终于会理解vector邻接表了;

先写个普通的邻接表构造和遍历！

#include
   
    using namespace std;#define N 100000typedef struct st{       int to;//结点编号     int w;//权值     struct st *nx;//结点指针(指向下一个结点) }ll,*link;//类型 struct sx{       ll *next;//表头后面跟的结点 }s[N];//邻接表的表头 int n;int book[N]={   0};//标记数组 void dfs(int x){   	cout<
    
     <<" ";    link p;    p=s[x].next;   	book[x]=1;   	while(p)   	{      		if(book[p->to]==0)		{   			book[p->to]=1;			dfs(p->to);		}		p=p->nx;		}    return;}void bfs(int x){       link p;    int q[N];    int r=0,f=0;   	book[x]=1;   	cout<
     
      <<" ";   	q[r++]=x;   	while(r!=f)   	{      		int t=q[f++];   		p=s[t].next;   		while(p)   		{      			if(book[p->to]==0)   			{      				cout<
      
       to<<" ";   				book[p->to]=1;				q[r++]=p->to;				}   			p=p->nx;			}	}    return;}void add(int from,int to,int w)//前插建表 {   	link p;    p=new ll;//结点分配空间     p->to=to;//from后面的结点编号     p->w=w;//from到to的权值     p->nx=s[from].next;    s[from].next=p;}/*//from：to：权值 5 1  2  2 1  3  1 2  4  5 2  5  4 */int main(){       int w;    int from,to;    link p;    cin>>n;    for(int i=1;i<=n;i++)    {   //表头指针域赋空         s[i].next=NULL;    }    for(int i=1;i<=n-1;i++)    {           scanf("%d%d%d",&from,&to,&w);        add(from,to,w);        add(to,from,w);    }    cout<<"邻接表"<
       
        to<<" ";			p=p->nx;		}		cout<
       
      
     
    
   

vector构造邻接表和遍历

#include
   
    //vecotr构造邻接表 using namespace std;#define N 100000struct st{       int to;//结点编号     int w;//权值 };//类型 vector
    
      s[N];//定义容器 int n;int book[N]={   0};void dfs(int x){   	book[x]=1;	cout<
     
      <<" ";    vector
      
       ::iterator it;    //迭代器法     /*it=s[x].begin();//结点x的邻接的第一个结点     while(it!=s[x].end())//到达容器的尾部     {    	if(book[it->to]==0)    	{    		book[it->to]=1;    		dfs(it->to);		}		it++;	}*/	st t;	//下标法 	for(int i=0;i
       
        >n;    int x,y;    for(int i=1;i<=n;i++)    {           s[i].clear();    }    for(int i=1;i<=n-1;i++)    {           scanf("%d%d%d",&x,&y,&w);        add(x,y,w);        add(y,x,w);    }    cout<<"邻接表"<
       
      
     
    
   

转载地址：http://trel.baihongyu.com/