graph.cpp

创建静态

typedef struct arcnode
{
	int adjvex;
	struct arcnode *nex;
}arcnode,*arclink;

typedef struct vnode
{
	char data;
	arcnode *first;
}vnode;

typedef struct
{
	vnode xlist[20];
	int vexnum,arcnum;
//	int kind;
}graph;


graph G;
bool visited[20];
vnode xlist[20];
int j,k,vexnum,arcnum,v,w;
void (*visitfunc)(int v);


int locate(graph G, char c)
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(G.xlist[i].data==c)
			return i;
}


void creat(graph &G)
{
	int i,k;
	char v1,v2;
	arclink p;
	cout<<"输入顶点和弧的个数，比如 3 2回车"<<endl;
	cin>>G.vexnum>>G.arcnum;
	cout<<"输入"<<G.vexnum<<"个顶点信息，比如 abc或1 2 3"<<endl;
	for(i=0;i<G.vexnum;i++)
	{
		cin>>G.xlist[i].data;
		G.xlist[i].first=NULL;
	}
    cout<<"输入"<<G.arcnum<<"条弧，比如abac或1 2 1 3"<<endl;
	for(k=0;k<G.arcnum;k++)
	{
		cin>>v1>>v2;
		i=locate(G,v1);
		j=locate(G,v2);
		p=(arclink)malloc(sizeof(arcnode));
		p->adjvex=j;
		p->nex=G.xlist[i].first;
		G.xlist[i].first=p;
	}	
}


int firstvex(graph G,int i)
{
	arclink p;
	p=G.xlist[i].first;
	if(p)
		return p->adjvex;
	else 
		return -1;
}


int nextvex(graph G,int i)
{
	arclink p;
	p=G.xlist[i].first;
	while(p) 
	{ 
		if(visited[p->adjvex]) 
			p=p->nex; 
		else 
			return p->adjvex; 
	} 
	return -1; 
	
}

void print(int v)
{
	cout<<G.xlist[v].data<<endl;
}

void DFS(graph G,int v)
{
	
	visited[v]=1;
	visitfunc(v);
	for(w=firstvex(G,v);w>=0;w=nextvex(G,v))
		if(!visited[w])
			DFS(G,w);
}


void DFStraverse(graph G,void (*visit)(int v))
{
	cout<<"深度优先搜索序列: "<<endl;
	visitfunc=visit;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v);
}

void BFStraverse(graph G, void (*visit)( int v ))
{
	
	
	int stack[30],u;
	int *base,*top;
	cout<<"广度优先搜索序列: "<<endl;

	base=top=stack;
	for (v=0; v<G.vexnum; ++v)
		visited[v] =0;                
	for (v=0;  v<G.vexnum;  ++v)
		if (!visited[v])
		{             
			visited[v] = 1;  visit(v); 
			*top++=v;               
			while (top-base) 
			{
				u=*base++;         
				for (w=firstvex(G, u);  w>=0;  w=nextvex(G, u))
					if (!visited[w]) 
					{        
						visited[w] = 1;  visit(w);
						
					}
			}                      
		}
} 


void findindegree(graph G,int indegree[])
{
	int i;
	arclink p;

	for(i=0;i<G.vexnum;i++)
		indegree[i]=0;
	
	for(i=0;i<G.vexnum;i++)
		for(p=G.xlist[i].first;p;p=p->nex)
			indegree[p->adjvex]++;
}



int tuopu(graph G) 
{ 
	
	arclink p; 
	int count,k,i,j=0;
	int indegree[30],stack[30];
	
	
	findindegree(G,indegree);   	
	for (i=0; i<G.vexnum; ++i)      
		if (!indegree[i]) 
			stack[j++]=i; 
		count = 0; 
		
		while (j) 
		{
			i=stack[--j];
			cout<<i<<"\t"<<(char)45<<(char)16<<G.xlist[i].data<<endl;
			count++;  
			for (p=G.xlist[i].first; p;  p=p->nex)
			{
				k = p->adjvex;              
				if (!(--indegree[k]))
					stack[j++]=k;  
			}
		}
		if (count<G.vexnum) 
			return 0;      
		else
			return 1;
} 


void tuopupaixu()
{
	int s=tuopu(G);
	if(s)
		cout<<"排序成功"<<endl;
	else cout<<"排序不成功"<<endl;
}


int selecttu()
{
	int n;
	cout<<"   *********************************************************************** "<<endl;   
	cout<<"   *                         1.创建有向无环图                            * "<<endl;   
	cout<<"   *                         2.深度优先遍历                              * "<<endl;    
	cout<<"   *                         3.广度优先遍历                              * "<<endl; 
	cout<<"   *                         4.拓扑排序                                  * "<<endl;
	cout<<"   *                         5.                                          * "<<endl;
	cout<<"   *                         6.                                          * "<<endl;
	cout<<"   *                         7.                                          * "<<endl;
	cout<<"   *                         8.                                          * "<<endl;
	cout<<"   *                         9.返回上一层                                * "<<endl;
	cout<<"   *                         0.退出                                      * "<<endl;
	cout<<"   *********************************************************************** "<<endl;       
	cout<<"                            选择你想进行的操作:                            "<<endl;   
	cout<<"请选择0~9!"<<endl;
	cin>>n;
	for(;;)
	{
		if(n<0||n>9)
		{
			cout<<"重选"<<endl;
			cin>>n;
		}
		else
			break;
	}
	return n;	
}