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

#include<stdio.h>
#include<iostream.h>
#include<malloc.h>
#define M 50
typedef char vextype;//顶点数据类型char
typedef struct node //定义表结点类型
{
int adjvex;//邻接点域
struct node *link;//指针域
}edgenode,*Edgenode;
typedef struct headnode//定义表头结点类型
{
vextype vexdata;//顶点数据域
struct node *firstarc;//指针域指向链表中的第一个结点
}vexnode,*Vexnode;
typedef vexnode adjlist[M];//adjlist为邻接表类型
//无向图的邻接表生成算法
void creatlist1(vexnode ag[],int n)
{
edgenode *p;
int i,j;
char ch;
cout<<"请输入顶点个数:";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"个顶点为:";
cin>>ch;//读入顶点信息
ag[i].vexdata=ch;//设顶点为字符型
ag[i].firstarc=NULL;//将每个链表初始化为空
}
cout<<"以(0,0)为输入结束符"<<endl;
cout<<"输入一条边依附的两个顶点序号:";
cin>>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(edgenode));//生成临界点序号为i的表结点
p->adjvex=i;
p->link=ag[j].firstarc;
ag[j].firstarc=p;//结点i插入到第j个链表的头部
cout<<"输入下一条边的两个顶点序号:";
cin>>i>>j;//再次输入下一条边的两个顶点序号
}
}/*creatlist1*/
//有向图邻接表生成算法
void creatlist2(vexnode ag[],int n)
{
edgenode *p;
int i,j;
char ch;
cout<<"请输入顶点个数:";
cin>>n;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"个顶点为:";
cin>>ch;//读入顶点信息
ag[i].vexdata=ch;//设顶点为字符型
ag[i].firstarc=NULL;//将每个链表初始化为空
}
cout<<"以(0,0)为输入结束符"<<endl;
cout<<"输入一条边依附的两个顶点序号:";
cin>>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个链表
cout<<"输入下一条边的两个顶点序号:";
cin>>i>>j;//再次输入下一条边的两个顶点序号
}
}/*creatlist2*/
void DFS(vexnode ag[],int v,int flag[])//从序号为v的顶点对图进行深度优先遍历
{
edgenode *p;
int i;
flag[v]=1;
cout<<ag[v].vexdata<<" ";
p=ag[v].firstarc;//p最初指向v的第一个邻接点
while(p!=NULL)
{
i=p->adjvex;//取出p指针所指向的邻接点的序号
if(flag[i]==0)
DFS(ag,i,flag);
//对尚未被访问的邻接点递归调用DFS算法进行深度优先遍历
p=p->link;//查找下一个邻接点
}
}/*DFS*/
void blt(vexnode ag[],int n)//对图按深度优先遍历搜索
{
int i;
int flag[M];
for(i=1;i<=n;i++)
flag[i]=0;//初始化标志组flag
for(i=1;i<=n;i++)
if(flag[i]==0)
DFS(ag,i,flag);//调用深度优先算法DFS
}
void BFS(Vexnode g,int v,int c[])//对图进行广度遍历
{
int q[M],r=0,f=0;
Edgenode p;
c[v]=1;
cout<<g[v].vexdata<<" ";
q[0]=v;
while(f<=r)
{
v=q[f++];
p=g[v].firstarc;
while(p!=NULL)
{
v=p->adjvex;
if(c[v]==0)
{
c[v]=1;
cout<<g[v].vexdata<<" ";
q[++r]=v;
}
p=p->link;
}
}
}/*BFS*/
void main()
{
int n=0,j,k,kind,i;
char flag='y';
int f[M];
vexnode v1[M],v2[M];
while(flag=='y')
{
cout<<"请选择图的种类(1代表有向图，2代表无向图)"<<endl;
cin>>kind;//输入图的种类
switch(kind)
{
case 1:cout<<"---------------创建有向图---------------"<<endl;
creatlist1(v1,n);//创建有向图
cout<<"开始遍历的结点序号为:";
cin>>j;
for(i=0;i<M;i++)
f[i]=0;
cout<<"深度遍历为:";
DFS(v1,j,f);//深度遍历
cout<<endl;
for(i=0;i<M;i++)
f[i]=0;
cout<<"广度遍历为:";
BFS(v1,j,f);//广度遍历
break;
case 2:cout<<"---------------创建无向图----------------"<<endl;
creatlist2(v2,n);//创建无向图
cout<<"开始遍历的结点序号为:";
cin>>k;
for(i=0;i<M;i++)
f[i]=0;
cout<<"深度遍历为:";
DFS(v2,k,f);//深度遍历
cout<<endl;
for(i=0;i<M;i++)
f[i]=0;
cout<<"广度遍历为:";
BFS(v2,k,f);//广度遍历
break;
default:cout<<"输入错误,程序结束!"<<endl;
return;
}
cout<<endl;
cout<<"是否继续?(输入n结束,输入y有效!)"<<endl;
cin>>flag;
}
cout<<"程序结束，再见!"<<endl;
}