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

菜鸟生成记(47)

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

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

#include<bits/stdc++.h>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<<x<<" ";    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<<x<<" ";   	q[r++]=x;   	while(r!=f)   	{      		int t=q[f++];   		p=s[t].next;   		while(p)   		{      			if(book[p->to]==0)   			{      				cout<<p->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<<"邻接表"<<endl;    for(int i=1;i<=n;i++)    {       	cout<<'['<<i<<']'<<" ";    	link p=s[i].next;    	while(p)    	{       		cout<<p->to<<" ";			p=p->nx;		}		cout<<endl;	}    cout<<"深搜遍历序列"<<endl;    dfs(1);//从编号为1的结点开始遍历     cout<<endl;    memset(book,0,sizeof(book));//标记数组置空     cout<<"广搜遍历序列"<<endl;    bfs(1);//从编号为1的结点开始遍历    return 0;}

vector构造邻接表和遍历

#include<bits/stdc++.h>//vecotr构造邻接表 using namespace std;#define N 100000struct st{       int to;//结点编号     int w;//权值 };//类型 vector<st> s[N];//定义容器 int n;int book[N]={   0};void dfs(int x){   	book[x]=1;	cout<<x<<" ";    vector<st>::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<s[x].size();i++)	{   		t=s[x][i];		if(book[t.to]==0)		{       		dfs(t.to);		}	}    return;}void bfs(int x){   	cout<<x<<" ";	int q[N];//队列	int r=0,f=0;	q[r++]=x;//入队	book[x]=1;//标记	while(f!=r)	{   		int t=q[f++];//出队		for(int i=0;i<s[t].size();i++)		{   			if(book[s[t][i].to]==0)			{   				cout<<s[t][i].to<<" ";				book[s[t][i].to]=1;				q[r++]=s[t][i].to;//入队			}		}	}        }void add(int from,int to,int w)//链接结点 {   	st t;	t.to=to;	t.w=w;	s[from].push_back(t);//入栈}/*5 1  2  2 1  3  1 2  4  5 2  5  4 */int main(){       int w;    cin>>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<<"邻接表"<<endl;    for(int i=1;i<=n;i++)    {       	cout<<'['<<i<<']'<<" ";    	for(int j=0;j<s[i].size();j++)    	{       		cout<<s[i][j].to<<" ";		}		cout<<endl;	}    cout<<"深搜遍历序列"<<endl;    dfs(1);//从编号为1的结点开始遍历     cout<<endl;    memset(book,0,sizeof(book));//标记数组置空     cout<<"广搜遍历序列"<<endl;    bfs(1);//从编号为1的结点开始遍历    return 0;}

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