图的邻接表储存及其遍历[数据结构学习]
好长时间没有写代码(感觉自己更弱了)，今天晚上就把数据结构的链表和邻接表部分实现了（手都生了），第一次写邻接表，觉得还是邻接矩阵好很多，毕竟建表还是挺麻烦的.....顺便把bfs和dfs加了进去，刚学数据结构或者算法入门的可以看看，我是小菜，大神 求别喷......
过两天再把几种排序和查找的时空分析和代码实现总结一下，顺便自己也能学到很多，快要考试了，ACM的步伐就放缓一下下......
//图的邻接表储存及搜索 ，第一次写邻接表，还是比较麻烦的 ，下面的代码以有向图为例进行分析 //邻接矩阵就比较简单了，直接把p=p->next改为循环查找，然后操作都是一样的 //其实我觉得邻接表比邻接矩阵没有好到哪去，建表多出一步啊 ，做题还是矩阵来的方便 #include<iostream>#include<queue>#include<stack>#include<cstring> #define N 10000 //顶点个数using namespace std;int vist[N];struct ArcNode //顶点的一个边节点{ int value ; //该邻接点 的值 ArcNode *nextver; //下一个 邻接点的指针 };struct K_Node{ //int value; // 可有可无，如果顶点是从0开始计数value=数组下标，否则等于数组下标加一 ArcNode *nextver; // 顶点的出边表表头指针 //ArcNode *head2; // 如果有向图需要记录每个顶点的入边表的节点，可加上此指针 };struct Grf{ //邻接表的建造 K_Node node[N]; //定点 int arcnum; //邻接表边数 int vexnum; //邻接表点数 };Grf CreatGf(){ Grf GT; cout<< "请输入邻接表的边数和点数："<<endl; cin>>GT.arcnum>>GT.vexnum; for(int i=0;i<GT.vexnum;i++) GT.node[i].nextver=NULL; //GT.node[i].head2=NULL 需建立入边表时可用到 ArcNode *pi; cout<<"请输入每条边的两个顶点"<<endl; int v1,v2; for(int i=0;i<GT.arcnum;i++) { cin>>v1>>v2; pi=new ArcNode; pi->value=v2; pi->nextver=GT.node[v1].nextver; GT.node[v1].nextver=pi; /* 如果需要建立入边表 或者是无向图则需要下列代码 pi=new ArcNode; pi->value=v1; pi->next=GT.node[v2].head2; GT.node[v2].head1=p1; */ } return GT;}void DFS( int vertex,Grf GT) //深度优先搜索{ vist[vertex]=1; //搜索到后做标记 cout<<vertex<<" "; ArcNode *p=GT.node[vertex].nextver; while(p!=NULL) { if(vist[p->value]==0) DFS(p->value,GT); p=p->nextver; } }void BFS(int vertex ,Grf GT) //广度优先搜索{ vist[vertex]=1; queue<int> q; q.push(vertex); while(!q.empty()) { int k=q.front(); cout<<k<<" "; q.pop(); ArcNode *p=GT.node[k].nextver; while(p!=NULL) { if(vist[p->value]==0) { vist[p->value]=1; q.push(p->value); } p=p->nextver; } }} int main() { Grf GT=CreatGf(); //建表 memset(vist,0,sizeof(vist)); cout<<"DFS测试结果为："<<endl; DFS(1,GT); //深搜 cout<<endl<<"BFS测试结果为：" <<endl ; memset(vist,0,sizeof(vist)); BFS(1,GT); //广搜 system("pause"); return 0;}/*测试数据如下8 81 2 2 32 55 11 44 66 77 8*/