数据结构中有向图和无向图的c语言实现

《数据结构中有向图和无向图的c语言实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、#include#include#include#defineM50typedefcharvextype;//顶点数据类型chartypedefstructnode//定义表结点类型{intadjvex;//邻接点域structnode*link;//指针域}edgenode,*Edgenode;typedefstructheadnode//定义表头结点类型{vextypevexdata;//顶点数据域structnode*firstarc;//指针域指向链表中

2、的第一个结点}vexnode,*Vexnode;typedefvexnodeadjlist[M];//adjlist为邻接表类型//无向图的邻接表生成算法voidcreatlist1(vexnodeag[],intn){edgenode*p;inti,j;charch;cout<<"请输入顶点个数:";cin>>n;for(i=1;i<=n;i++){cout<<"第"<>ch;//读入顶点信息ag[i].vexdata=ch;//设顶点为字符型ag[i].firstarc=NULL;//将

3、每个链表初始化为空}cout<<"以(0,0)为输入结束符"<>i>>j;while((i>0)&&(j>0))//输入的(i,j)为(0,0)作为结束符号{p=(edgenode*)malloc(sizeof(edgenode));//生成邻接序号为j的表结点p->adjvex=j;p->link=ag[i].firstarc;ag[i].firstarc=p;//结点j插入到第i个链表p=(edgenode*)malloc(sizeof(edgenod

4、e));//生成临界点序号为i的表结点p->adjvex=i;p->link=ag[j].firstarc;ag[j].firstarc=p;//结点i插入到第j个链表的头部cout<<"输入下一条边的两个顶点序号:";cin>>i>>j;//再次输入下一条边的两个顶点序号}}/*creatlist1*///有向图邻接表生成算法voidcreatlist2(vexnodeag[],intn){edgenode*p;inti,j;charch;cout<<"请输入顶点个数:";cin>>n;for(i=1;i<=n;i++)

5、{cout<<"第"<>ch;//读入顶点信息ag[i].vexdata=ch;//设顶点为字符型ag[i].firstarc=NULL;//将每个链表初始化为空}cout<<"以(0,0)为输入结束符"<>i>>j;while((i>0)&&(j>0))//输入的(i,j)为(0,0)作为结束符号{p=(edgenode*)malloc(sizeof(edgenode));//生成邻接序号为j的表结点p->adjvex=j

6、;p->link=ag[i].firstarc;ag[i].firstarc=p;//结点j插入到第i个链表cout<<"输入下一条边的两个顶点序号:";cin>>i>>j;//再次输入下一条边的两个顶点序号}}/*creatlist2*/voidDFS(vexnodeag[],intv,intflag[])//从序号为v的顶点对图进行深度优先遍历{edgenode*p;inti;flag[v]=1;cout<

7、p!=NULL){i=p->adjvex;//取出p指针所指向的邻接点的序号if(flag[i]==0)DFS(ag,i,flag);//对尚未被访问的邻接点递归调用DFS算法进行深度优先遍历p=p->link;//查找下一个邻接点}}/*DFS*/voidblt(vexnodeag[],intn)//对图按深度优先遍历搜索{inti;intflag[M];for(i=1;i<=n;i++)flag[i]=0;//初始化标志组flagfor(i=1;i<=n;i++)if(flag[i]==0)DFS(ag,i,flag)

8、;//调用深度优先算法DFS}voidBFS(Vexnodeg,intv,intc[])//对图进行广度遍历{intq[M],r=0,f=0;Edgenodep;c[v]=1;cout<