图.cpp

图函数

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<stdio.h>
struct node
{
   bool mark;
   char letter;
   struct edge *out;
};
struct edge
{
	bool mark;
	int no;
	struct edge *link;
};
#define size 10
void graphinput(struct node nodelist[size],int n);
void showgraph(struct node nodelist[size],int n);
void DFS(struct node nodelist[size],int n);
void BFS(struct node nodelist[size],int v,int n);
int pop(int stack[size],int &i,int top);
int push(int stack[size],int i,int top);
void main()
{
	struct node nodelist[size];
	int i,j,n;
	cout<<"请新建一个图表，输入结点个数"<<endl;
	cin>>n;
	graphinput(nodelist,n);
	showgraph(nodelist,n);
	cout<<"输入您的选择：0、退出 1、深度遍历  2、宽度遍历 3、重新建立图表 "<<endl;
	cin>>i;
	while(i)
	{
	switch(i)
	{
	case 0:
		break;
	case 1:
		DFS(nodelist,n);
		for(i=1;i<=n;i++)
		{
			nodelist[i].mark=false;
		}
		cout<<endl;
		break;
	case 2:
		BFS(nodelist,1,n);
		for(j=1;j<=n;j++)
		{
			if(nodelist[j].mark==true) cout<<"";
			else BFS(nodelist,j,n);
		}
		cout<<endl;
		for(i=1;i<=n;i++)
		{
			nodelist[i].mark=false;
		}
		break;
    case 3:
		cout<<"输入结点个数"<<endl;
		cin>>n;
		graphinput(nodelist,n);
		showgraph(nodelist,n);
		break;
	default:
		break;
	}
	cout<<"输入您的选择：0、退出 1、深度遍历  2、宽度遍历  3、重新建立图表"<<endl;
	cin>>i;
	}
}

void graphinput(struct node nodelist[size],int n)     //新建图
{
	int i,j,m;
	struct edge *q,*p;
	for(i=1;i<=n;i++)
	{
		cout<<"输入第"<<i<<"个顶点数据"<<endl;
		cin>>nodelist[i].letter;
		nodelist[i].mark=false;
		nodelist[i].out=NULL;
	}
	for(i=1;i<=n;i++)
	{
		cout<<"输入第"<<i<<"个顶点的关联边数"<<endl;
		cin>>m;
		if(m)
		{
			nodelist[i].out=(struct edge *)malloc(sizeof(struct edge));
			cout<<"输入第"<<i<<"个顶点的第1条边(输入顶点编号)"<<endl;
			cin>>nodelist[i].out->no;
			nodelist[i].out->mark=false;
			nodelist[i].out->link=NULL;
			p=nodelist[i].out;
			for(j=1;j<m;j++)
			{
				q=(struct edge *)malloc(sizeof(struct edge));
				cout<<"输入第"<<i<<"个顶点的第"<<j+1<<"条边(输入顶点编号)"<<endl;
				cin>>q->no;
				q->mark=false;
				q->link=NULL;
				p->link=q;
				p=q;
			}
		}
	}
}

void showgraph(struct node nodelist[size],int n)      //图的邻接表示
{
	int i;
	struct edge *p;
	cout<<"图的邻接表示"<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<"("<<i<<","<<nodelist[i].letter<<")";
		p=nodelist[i].out;
        while(p!=NULL)
		{
			cout<<"-->("<<p->no<<","<<nodelist[p->no].letter<<")";
			p=p->link;
		}
		cout<<endl;
	}
}

void DFS(struct node nodelist[size],int n)   //深度遍历
{
	int i,k,top=-1,p;
	bool notfinished;
	int stack[size];
	struct edge *next[size];
	for(i=1;i<=n;i++) next[i]=nodelist[i].out;     //next[i]是每个顶点边表要检查的下一条边
	for(k=1;k<=n;k++)
	{
		if(nodelist[k].mark==false)
		{
			i=k;
			cout<<nodelist[i].letter<<"  ";
			nodelist[i].mark=true;
			notfinished=true;
			while(notfinished)              //从此出发遍历该顶点的生成树
			{
				while(next[i]==NULL)       //如果边表空则回溯顶点
				{
					if(top==-1)          //若栈空则该顶点生成子树遍历结束跳出循环
					{
						notfinished=false;
						break;
					}
					top=pop(stack,i,top);  //否则深度搜索路径上的一个顶点出栈
				}
				if(notfinished)          //检查与第i个顶点关联的一条尚未搜索的边
				{
					p=next[i]->no;        //指向边的另一端邻接顶点p
					if(nodelist[p].mark==false)   //顺此顶点的深度方向遍历
					{
						top=push(stack,i,top);    //当前顶点的前趋入栈
						next[i]->mark=true;       //前趋边访问过标记
						cout<<nodelist[p].letter<<"  "; //访问此顶点
						nodelist[p].mark=true;          //访问过标记
						next[i]=next[i]->link;          //指向顶点i边表的下一节点（边）
						i=p;                     //更换到邻接顶点的边表
					}
					else next[i]=next[i]->link;  //此顶点已经标记过，更换边
				}
			}
		}
	}
	}

int pop(int stack[size],int &i,int top)
{
    i=stack[top];
	top--;
	return top;
}
int push(int stack[size],int i,int top)
{
	top++;
	stack[top]=i;
	return top;
}

void BFS(struct node nodelist[size],int v,int n)    //宽度遍历
{
	
	int queue[size];
	int front=0,rear=1,t;
	struct edge *p;
	nodelist[v].mark=true;
	cout<<nodelist[v].letter<<"  ";
	queue[rear]=v;          //入队
	while(front!=rear)
	{
		front=(front+1)%size; 
		t=queue[front];         //出队
		p=nodelist[t].out;
		while(p!=NULL)
		{
			if(nodelist[p->no].mark==false)
			{
				nodelist[p->no].mark=true;
				cout<<nodelist[p->no].letter<<"  ";
				rear=(rear+1)%size;
				queue[rear]=p->no;
			}
			p=p->link;
		}
	}
}