数据结构中有向图和无向图的C语言实现.docx

#include#include#include#define M 50typedef char vextype;/顶点数据类型chartypedef struct node /定义表结点类型int adjvex;/邻接点域struct node *link;/指针域edgenode,*Edgenode;typedef struct headnode/定义表头结点类型vextype vexdata;/顶点数据域struct node *firstarc;/指针域指向链表中的第一个结点vexnode,*Vexnode;typedef vexnode adjlistM;/adjlist为邻接表类型/无向图的邻接表生成算法void creatlist1(vexnode ag,int n)edgenode *p;int i,j;char ch;coutn;for(i=1;i=n;i+)cout第ich;/读入顶点信息agi.vexdata=ch;/设顶点为字符型agi.firstarc=NULL;/将每个链表初始化为空cout以(0,0)为输入结束符endl;coutij;while(i0)&(j0)/输入的(i,j)为(0,0)作为结束符号p=(edgenode*)malloc(sizeof(edgenode);/生成邻接序号为j的表结点p-adjvex=j;p-link=agi.firstarc;agi.firstarc=p;/结点j插入到第i个链表p=(edgenode*)malloc(sizeof(edgenode);/生成临界点序号为i的表结点p-adjvex=i;p-link=agj.firstarc;agj.firstarc=p;/结点i插入到第j个链表的头部coutij;/再次输入下一条边的两个顶点序号/*creatlist1*/有向图邻接表生成算法void creatlist2(vexnode ag,int n)edgenode *p;int i,j;char ch;coutn;for(i=1;i=n;i+)cout第ich;/读入顶点信息agi.vexdata=ch;/设顶点为字符型agi.firstarc=NULL;/将每个链表初始化为空cout以(0,0)为输入结束符endl;coutij;while(i0)&(j0)/输入的(i,j)为(0,0)作为结束符号p=(edgenode*)malloc(sizeof(edgenode);/生成邻接序号为j的表结点p-adjvex=j;p-link=agi.firstarc;agi.firstarc=p;/结点j插入到第i个链表coutij;/再次输入下一条边的两个顶点序号/*creatlist2*/void DFS(vexnode ag,int v,int flag)/从序号为v的顶点对图进行深度优先遍历edgenode *p;int i;flagv=1; coutagv.vexdataadjvex;/取出p指针所指向的邻接点的序号if(flagi=0)DFS(ag,i,flag);/对尚未被访问的邻接点递归调用DFS算法进行深度优先遍历p=p-link;/查找下一个邻接点/*DFS*/void blt(vexnode ag,int n)/对图按深度优先遍历搜索int i;int flagM;for(i=1;i=n;i+)flagi=0;/初始化标志组flagfor(i=1;i=n;i+)if(flagi=0)DFS(ag,i,flag);/调用深度优先算法DFSvoid BFS(Vexnode g,int v,int c)/对图进行广度遍历int qM,r=0,f=0;Edgenode p;cv=1;coutgv.vexdata ;q0=v;while(fadjvex;if(cv=0)cv=1;coutgv.vexdatalink;/*BFS*/void main()int n=0,j,k,kind,i;char flag=y; int fM;vexnode v1M,v2M; while(flag=y)cout请选择图的种类(1代表有向图，2代表无向图)kind;/输入图的种类switch(kind)case 1:cout-创建有向图-endl; creatlist1(v1,n);/创建有向图 coutj; for(i=0;iM;i+) fi=0; cout深度遍历为:; DFS(v1,j,f);/深度遍历 coutendl; for(i=0;iM;i+) fi=0; cout广度遍历为:; BFS(v1,j,f);/广度遍历 break;case 2:cout-创建无向图-endl; creatlist2(v2,n);/创建无向图 coutk; for(i=0;iM;i+) fi=0; cout深度遍历为:; DFS(v2,k,f);/深度遍历 coutendl; for(i=0;iM;i+) fi=0; cout广度遍历为:; BFS(