图的搜索.cpp

树的遍历等数据结构程序代码实现

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

#define MAX 100

typedef struct node{
	int adjvex;
	struct node* next;
}edgenode;//边表结点

typedef struct vnode{
	int vertex;
	edgenode* link;
}adj_list[MAX];//顶点表结点

typedef struct adjlist_graph{
	int nodes, edges;//图中顶点数和边数
	adj_list adjlist;//邻接表
}algraph;

struct Queue
{
	int q[MAX];
	int f,r;
};
template<class T>//栈模板
class stack
{ 
	T S[MAX];
	int top;
public:    
	stack(){ top=-1;}
	void push(T& item);
	T pop();
	int empty();
};
template<class T>
void stack<T>::push(T& item)//进栈
{ 
	if (top==MAX-1)
	{ 
		cout<<"栈满"<<endl;
		exit(1);
	}
	top++;
	S[top]=item;
}
template<class T>
T stack<T>::pop()//出栈
{ 
	T temp;
	if(top==-1)
	{
		cout<<"栈空"<<endl;
		exit(1);
	}
	temp=S[top];
	top--;
	return temp;
}
template<class T>
int stack<T>::empty(){return top==-1;}


void build_algraph(algraph *g)//建邻接表
{
	edgenode* p;
	int i, j, k;
	
	for(i = 1; i <= g->nodes; i++){
		g->adjlist[i].vertex = i;
		g->adjlist[i].link = NULL;
	}
	
	for(k = 1; k <= g->edges; k++){
		printf("请输入第%d条边,即顶点对: ",k);
		cin>>i>>j;
		cout<<endl;
		
		p = new edgenode;
		p->adjvex = j;
		p->next = g->adjlist[i].link;
		g->adjlist[i].link = p;
		
		p = new edgenode;;
		p->adjvex = i;
		p->next = g->adjlist[j].link;
		g->adjlist[j].link = p;
	}
}

void print_algraph(algraph* g)//打印邻接表
{
	edgenode* node;
	int i;
	
	for(i = 1; i <= g->nodes; i++){
		node = g->adjlist[i].link;
		printf("g->adjlist[%d] = %d: ", i, g->adjlist[i].vertex);
		while(node != NULL){
			printf("%d\t", node->adjvex);
			node = node->next;
		}
		cout<<endl;
	}
} 

void dfs(algraph *g,int vo,int *visited)//深度搜索
{
	stack<edgenode*>pa;
	cout<<vo;
	visited[vo]=1;
    edgenode *p;
    p=new edgenode;
	p=g->adjlist[vo].link;
	while((p!=NULL)||(!pa.empty()))
	{
		while(p!=NULL)
		{
			if(visited[p->adjvex]==1)
				p=p->next;
			else
			{
				cout<<"->"<<p->adjvex;
				visited[p->adjvex]=1;
				pa.push(p);
				p=g->adjlist[p->adjvex].link;
			}
		}
		if(!pa.empty())
		{
			p=pa.pop();
			p=p->next;
		}
	}
}

void bfs(algraph *g,int vo,int *visited)//广度搜索
{
	visited[vo]=1;
	cout<<vo;
    Queue queue;
	queue.f=0; queue.r=0;
	edgenode *p;
    p=new edgenode;
	p=g->adjlist[vo].link;
	int v;
	do
	{
		while(p!=NULL)
		{
			v=p->adjvex;
			if(visited[v]==0)
			{
				queue.q[queue.r]=v;
				queue.r++;
				cout<<"->"<<v;
				visited[v]=1;
			}
			p=p->next;
		}
		if(queue.f!=queue.r)
		{
			v=queue.q[queue.f];
			queue.f++;
			p=g->adjlist[v].link;
		}
	}while((p!=NULL)||(queue.f!=queue.r));
}          
void main()
{   
    algraph *g;
	g=new algraph;
	cout<<"请输入图的顶点数和边数:\n";
	cout<<"顶点数:";cin>>g->nodes;
    cout<<"边数:";cin>>g->edges;
    printf("顶点数 = %d, 边数 = %d\n", g->nodes, g->edges);
    cout<<"开始建立邻接表!"<<endl;
	cout<<endl;
    build_algraph(g);
    cout<<"建立邻接表完毕!"<<endl;
	cout<<endl;
	cout<<"邻接表打印如下:"<<endl;
    print_algraph(g);
	cout<<endl;
	
    int mm;
    
loop:	cout<<"请选择你要进行遍历的方式(1.深度优先搜索;2.广度优先搜索;其他数字.退出!):";
		cin>>mm;
		switch(mm)
		{ 
		case 1:
			{
				int n=g->nodes,vo;
				int *visited;
				visited=new int[n+1];
				for(int i=1;i<=n;i++) visited[i]=0;
				cout<<"请输入遍历的起点标号vo:";
				cin>>vo;
				cout<<endl;
				cout<<"深度优先搜索序列为:";
				dfs(g,vo,visited);
				cout<<endl;
				cout<<"遍历完毕!"<<endl;
                cout<<endl;cout<<endl;
				goto loop;
			}
		case 2:
			{  
				int n=g->nodes,vo;
				int *visited;
				visited=new int[n+1];
				for(int i=1;i<=n;i++) visited[i]=0;
				cout<<"请输入遍历的起点标号vo:";
				cin>>vo;
				cout<<endl;
				cout<<"广度优先搜索序列为:";
				bfs(g,vo,visited);
				cout<<endl;
				cout<<"遍历完毕!"<<endl;
				cout<<endl;cout<<endl;
				goto loop;
			}
		default:cout<<"欢迎使用!"<<endl;
		}
		
		
}