求连通分量.cpp

数据结构的一些实验

#include <iostream>
#include <malloc.h>
using namespace std; 
#define int_max 10000
#define inf 9999 
#define max 20
//…………………………………………邻接矩阵定义……………………
typedef struct ArcCell
{
	int adj;
	char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct 
{
	char vexs[20];
	AdjMatrix arcs;
	int vexnum,arcnum;
}MGraph_L;
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int localvex(MGraph_L G,char v)//返回V的位置
{
	int i=0;
	while(G.vexs[i]!=v)
	{
		++i;
	}
	return i;
}

int creatMGraph_L(MGraph_L &G)//创建图用邻接矩阵表示
{
	char v1,v2;
	int i,j,w;
	cout<<"…………创建无向图…………"<<endl<<"请输入图G顶点和弧的个数:(4 6)不包括“()”"<<endl;
	cin>>G.vexnum>>G.arcnum;
	for(i=0;i!=G.vexnum;++i)
	{
		cout<<"输入顶点"<<i<<endl;
		cin>>G.vexs[i];
	}
	for(i=0;i!=G.vexnum;++i)
		for(j=0;j!=G.vexnum;++j)
		{ 
			G.arcs[i][j].adj=int_max;
			G.arcs[i][j].info=NULL;
		}
		for(int k=0;k!=G.arcnum;++k)
		{ 
			cout<<"输入一条边依附的顶点和权:(a b 3)不包括“()”"<<endl;
			cin>>v1>>v2>>w;//输入一条边依附的两点及权值
			i=localvex(G,v1);//确定顶点V1和V2在图中的位置
			j=localvex(G,v2);
			G.arcs[i][j].adj=w;
			G.arcs[j][i].adj=w;
		}
		cout<<"图G邻接矩阵创建成功！"<<endl;
		return G.vexnum;
}
void ljjzprint(MGraph_L G)
{
	int i,j;
	for(i=0;i!=G.vexnum;++i)
	{
		for(j=0;j!=G.vexnum;++j)
			cout<<G.arcs[i][j].adj<<" ";
		cout<<endl;
	}
}
int visited[max];//访问标记
int we;
typedef struct arcnode//弧结点
{
	int adjvex;//该弧指向的顶点的位置
	struct arcnode *nextarc;//弧尾相同的下一条弧
	char *info;//该弧信息
}arcnode;
typedef struct vnode//邻接链表顶点头接点
{
	char data;//结点信息
	arcnode *firstarc;//指向第一条依附该结点的弧的指针
}vnode,adjlist;
typedef struct//图的定义
{
	adjlist vertices[max];
	int vexnum,arcnum;
	int kind;
}algraph;
//…………………………………………队列定义……………………
typedef struct qnode
{
	int data;
	struct qnode *next;
	
}qnode,*queueptr;

typedef struct
{
	queueptr front;
	queueptr rear;
	
}linkqueue;
//………………………………………………………………………
typedef struct acr
{
	int pre;//弧的一结点
	int bak;//弧另一结点
	int weight;//弧的权
}edg;

int creatadj(algraph &gra,MGraph_L G)//用邻接表存储图
{
	
	int i=0,j=0;
	arcnode *arc,*tem,*p;
	for(i=0;i!=G.vexnum;++i)
	{
		gra.vertices[i].data=G.vexs[i];
		gra.vertices[i].firstarc=NULL;
	}
	for(i=0;i!=G.vexnum;++i)
	{
		for(j=0;j!=G.vexnum;++j)
		{
			if(gra.vertices[i].firstarc==NULL)
			{
				if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
				{
					arc=(arcnode *)malloc(sizeof(arcnode));
					arc->adjvex=j;
					gra.vertices[i].firstarc=arc;
					arc->nextarc=NULL;
					p=arc;
					++j;
					while(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
					{
						tem=(arcnode *)malloc(sizeof(arcnode));
						tem->adjvex=j;    
						gra.vertices[i].firstarc=tem;
						tem->nextarc=arc;
						arc=tem;
						++j;
					}
					--j;
				}
			}
			else
			{
				if(G.arcs[i][j].adj!=int_max&&j!=G.vexnum)
				{
					arc=(arcnode *)malloc(sizeof(arcnode));
					arc->adjvex=j;
					p->nextarc=arc;
					arc->nextarc=NULL;
					p=arc;
				}
				
				
			}
			
		}
	}
	gra.vexnum=G.vexnum;
	gra.arcnum=G.arcnum;
	return 1;
}
void adjprint(algraph gra)
{
	int i;
	for(i=0;i!=gra.vexnum;++i)
	{
		arcnode *p;
		cout<<i<<" ";
		p=gra.vertices[i].firstarc;
		while(p!=NULL)
		{
			cout<<p->adjvex;
			p=p->nextarc;
		}
		cout<<endl;
	}
}

int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点
//即以V为尾的第一个结点
{
	if(v.firstarc!=NULL)
		return v.firstarc->adjvex;
	
}
int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点
{
	arcnode *p;
	p=v.firstarc;
	while(p!=NULL&&p->adjvex!=w)
	{
		p=p->nextarc;
	}
	if(p->adjvex==w&&p->nextarc!=NULL)
	{
		p=p->nextarc;
		return p->adjvex;
	}
	if(p->adjvex==w&&p->nextarc==NULL)
		return -10;
	
}
int initqueue(linkqueue &q)//初始化队列
{
	q.rear=(queueptr)malloc(sizeof(qnode));
	q.front=q.rear;
	if(!q.front)
		return 0;
	q.front->next=NULL;
	return 1;
}
int enqueue(linkqueue &q,int e)//入队
{
	queueptr p;
	p=(queueptr)malloc(sizeof(qnode));
	if(!p)
		return 0;
	p->data=e;
	p->next=NULL;
	q.rear->next=p;
	q.rear=p;
	return 1;
	
}
int dequeue(linkqueue &q,int &e)//出队
{
	queueptr p;
	if(q.front==q.rear)
		return 0;
	p=q.front->next;
	e=p->data;
	q.front->next=p->next;
	if(q.rear==p)
		q.rear=q.front;
	free(p);
	return 1;
	
}
int queueempty(linkqueue q)//判断队为空
{
	if(q.front==q.rear)
		return 1;
	return 0;
}


int dfs(algraph gra,int i);//声明DFS

int dfstra(algraph gra)
{
	int i,j;
	for(i=0;i!=gra.vexnum;++i)
	{
		visited[i]=0;
	}
	for(j=0;j!=gra.vexnum;++j)
	{
		if(visited[j]==0)
			dfs(gra,j);
	}
	return 0;
}
int dfs(algraph gra,int i)
{
	visited[i]=1;
	int we1;
	
	cout<<gra.vertices[i].data;
	
	for(we=firstadjvex(gra,gra.vertices[i]);we>=0;we=nextadjvex(gra,gra.vertices[i],we))
	{
		
		we1=we;
		
		if(visited[we]==0)
			
			dfs(gra,we);
		
		we=we1;
		
	}
	return 12;
}
int bfstra_fen(algraph gra)//求连通分量
{
	int i,j;
	for(i=0;i!=gra.vexnum;++i)
	{
		visited[i]=0;
	}
	for(j=0;j!=gra.vexnum;++j)
	{
		if(visited[j]==0)
		{
			dfs(gra,j);
			cout<<endl;
		}
	}
	return 0;
}



void main()
{ 
	algraph gra;
	MGraph_L G;
	int i,d,g[20][20];
	char a='a';
	d=creatMGraph_L(G);
	creatadj(gra,G);
	cout<<"邻接矩阵显示如下："<<endl;
	ljjzprint(G);
	
	//  cout<<"邻接表显示如下："<<endl;
	//  adjprint(gra);
	
	cout<<"连通分量:";
	bfstra_fen(gra);
	
	
}