再書き込み_隣接テーブルと隣接マトリクス記憶図

前に书いたあちらを遍歴するのにちょっと问题がある非连通図の时非再帰の深さの优先と広さの优先遍歴は间违いがあって修正しました以下はコードです

#include<iostream>
#include<string>
#include<time.h>
#include<stack>
using namespace std;

//         
template<class T>
class My_queue;

template<class T>
class Node
{
private:
	T data;
	Node<T> *next;
public:
	Node()
	{
		next=0;
	}
	Node(T d)
	{
		data=d;
		next=0;
	}
	friend My_queue<T>;
};

template<class T>
class My_queue
{
private:
	Node<T> *tail;
public:
	My_queue()
	{
		tail=new Node<T>();
		tail->next=tail;
	}

	~My_queue()
	{
		clean();
		delete tail;
	}

	bool empty()
	{
		return (tail->next==tail);
	}

	void push(T d)
	{
		Node<T> *p=new Node<T>(d);
		p->next=tail->next;
		tail->next=p;
		tail=p;
	}

	T front()
	{
		if(empty())
		{
			cout<<"queue is empty!"<<endl;
			exit(0);
		}
		Node<T> *p=tail->next;
		T data=p->next->data;
		return data;
	}

	T back()
	{
		if(empty())
		{
			cout<<"queue is empty!"<<endl;
			exit(0);
		}
		T data=tail->data;
		return data;
	}

	void pop()
	{
		Node<T> *p=tail->next;
		Node<T> *q=p->next;
		p->next=q->next;
		if(q==tail)
			tail=p;
		delete q;
	}

	void clean()
	{
		Node<T> *p=tail->next;
		Node<T> *q=p->next;
		while(q!=p)
		{
			p->next=q->next;
			delete q;
			p->next=q;
		}
	}
};

const int MAX_VERTEX_NUM=20;

bool visited[20];//    ，      

struct MGraph
{
	string vexs[MAX_VERTEX_NUM];//    
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //    
	int vexnum;//    
	int arcnum;//   
};

int Locate_Vex(MGraph G,string x)  //               
{
	for(int k=0;k<G.vexnum;k++)
	{	
		if(G.vexs[k]==x)
			return k;
	}
	return -1;
}

void CreateUDN_MG(MGraph &G)
{
	//         ，     
	int i,j,k;
	cout<<"          ：";
	cin>>G.vexnum>>G.arcnum;
	cout<<"         ：";
	for(i=0;i<G.vexnum;i++)
		cin>>G.vexs[i];
	
	for(i=0;i<G.vexnum;i++)
		for(int j=0;j<G.vexnum;j++)
			G.arcs[i][j]=0;
	//          
	
	for(k=0;k<G.arcnum;k++)
	{
		cout<<"            ：";
		string v1,v2;
		cin>>v1>>v2;
		i=Locate_Vex(G,v1);
		j=Locate_Vex(G,v2);
		while(i == -1 || j == -1)
		{
			cout<<"        ,    : ";
			cin>>v1>>v2;
			i=Locate_Vex(G,v1);
			j=Locate_Vex(G,v2);	
		}
		G.arcs[i][j]=1;
		G.arcs[j][i]=G.arcs[i][j]; //    
	}
	cout<<"     "<<endl;
}

void DFS(MGraph G,int v)
{
	visited[v]=true;
	cout<<G.vexs[v]<<"  ";
	for(int j=0;j<G.vexnum;j++)
		if(G.arcs[v][j] && !visited[j])
			DFS(G,j);
}

void DFS_2(MGraph G,int v)
{
	//          
	stack<int> s;
	cout<<G.vexs[v]<<"  ";
	s.push(v);
	visited[v]=true;
	while(!s.empty())
	{
		int c=0;
		int w=s.top();
		while(!G.arcs[w][c] || visited[c]==true )
			c++;
		if(c==G.vexnum)
			s.pop();
		else
		{	
			cout<<G.vexs[c]<<"  ";
			visited[c]=true;
			s.push(c);
		}
	}
}

//       
void DFS_Traverse(MGraph G)
{
	//visited              
	for(int i=0;i<G.vexnum;i++)
		visited[i]=false;
	for(int v=0;v<G.vexnum;v++)
		if(!visited[v])
		{
			//DFS(G,v);
			DFS_2(G,v);
		}
}

void BFS(MGraph G,int v)
{
	My_queue<int> q;
	cout<<G.vexs[v]<<"  ";
	visited[v]=true;
	q.push(v);
	while(!q.empty())
	{
		int w=q.front();
		q.pop();
		for(int i=0;i<G.vexnum;i++)
		{
			if(G.arcs[w][i] && !visited[i])
			{
				cout<<G.vexs[i]<<"  ";
				visited[i]=true;
				q.push(i);
			}
		}
	}
}

//      
void BFS_Traverse(MGraph G)
{
	for(int i=0;i<G.vexnum;i++)
		visited[i]=false;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
			BFS(G,i);
}

	
int main()
{
	MGraph G;
	CreateUDN_MG(G);
	cout<<"        ：";
	DFS_Traverse(G);
	cout<<endl;
	cout<<"        ：";
	BFS_Traverse(G);
	cout<<endl;

	return 0;
}

#include<iostream>
#include<string>
#include<time.h>
#include<stack>
using namespace std;

//         
template<class T>
class My_queue;

template<class T>
class Node
{
private:
	T data;
	Node<T> *next;
public:
	Node()
	{
		next=0;
	}
	Node(T d)
	{
		data=d;
		next=0;
	}
	friend My_queue<T>;
};

template<class T>
class My_queue
{
private:
	Node<T> *tail;
public:
	My_queue()
	{
		tail=new Node<T>();
		tail->next=tail;
	}

	~My_queue()
	{
		clean();
		delete tail;
	}

	bool empty()
	{
		return (tail->next==tail);
	}

	void push(T d)
	{
		Node<T> *p=new Node<T>(d);
		p->next=tail->next;
		tail->next=p;
		tail=p;
	}

	T front()
	{
		if(empty())
		{
			cout<<"queue is empty!"<<endl;
			exit(0);
		}
		Node<T> *p=tail->next;
		T data=p->next->data;
		return data;
	}

	T back()
	{
		if(empty())
		{
			cout<<"queue is empty!"<<endl;
			exit(0);
		}
		T data=tail->data;
		return data;
	}

	void pop()
	{
		Node<T> *p=tail->next;
		Node<T> *q=p->next;
		p->next=q->next;
		if(q==tail)
			tail=p;
		delete q;
	}

	void clean()
	{
		Node<T> *p=tail->next;
		Node<T> *q=p->next;
		while(q!=p)
		{
			p->next=q->next;
			delete q;
			p->next=q;
		}
	}
};

#define MAX_VERTEX_NUM 20
bool visited[20];//         
int Vex_Num;//        

//   
struct ArcNode
{
	int adjvex; //         
	ArcNode *nextarc;//       
};

//   
typedef struct VNode
{
	string data;//   
	ArcNode *firstarc;//           
}AdjList[MAX_VERTEX_NUM];

struct ALGraph
{
	AdjList vertices;//     
	int vexnum;//   
	int arcnum;//  
};

int Locate_Vex(ALGraph G,string x) //      
{
	for(int v=0;v<G.vexnum;v++)
	{
		if(G.vertices[v].data==x)
			return v;
	}
	return -1;
}

void CreateDG_ALG(ALGraph &G)
{
	//         ，     G
	string v1,v2;
	int i,j,k;
	cout<<"        ：";
	cin>>G.vexnum>>G.arcnum;
	
	//       
	cout<<"      ：";
	for(i=0;i<G.vexnum;i++)
	{
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;
	}

	//          
	for(k=0;k<G.arcnum;k++)
	{
		cout<<"  ->               ：";
		cin>>v1>>v2;
		i=Locate_Vex(G,v1);
		j=Locate_Vex(G,v2);
		while(i == -1 || j == -1)
		{
			cout<<"        ,    : ";
			cin>>v1>>v2;
			i=Locate_Vex(G,v1);
			j=Locate_Vex(G,v2);	
		}
	
		ArcNode *p=new ArcNode;
		p->adjvex=j;
		p->nextarc=G.vertices[i].firstarc;
		G.vertices[i].firstarc=p;
	}
}

//      
void DFS(ALGraph G,int v)
{
	visited[v]=true;
	cout<<G.vertices[v].data<<"  ";
	Vex_Num+=1;
	if(Vex_Num==G.vexnum)
		return;
	ArcNode *p;
	int w;
	for(p=G.vertices[v].firstarc;p;p=p->nextarc)
	{
		w=p->adjvex;
		if(!visited[w])
			DFS(G,w);
	}
}

void DFS_Traverse_1(ALGraph G)
{
	Vex_Num=0;
	int i,k;
	for(i=0;i<G.vexnum;i++)
		visited[i]=false;
	for(k=0;k<G.vexnum;k++)
		if(!visited[k])
			DFS(G,k);
}

void DFS_2(ALGraph G,int v)
{
	stack<int> s;
	cout<<G.vertices[v].data<<"  ";
	s.push(v);
	visited[v]=true;
	while(!s.empty())
	{
		int w=s.top();
		ArcNode *p=NULL;
		p=G.vertices[w].firstarc;
		while(p && visited[p->adjvex]==true)
			p=p->nextarc;
		if(!p)
			s.pop();
		else
		{
			visited[p->adjvex]=true;
			cout<<G.vertices[p->adjvex].data<<"  ";
			s.push(p->adjvex);
		}
	}
}

void DFS_Traverse_2(ALGraph G)
{
	int i,k;
	for(i=0;i<G.vexnum;i++)
		visited[i]=false;
	for(k=0;k<G.vexnum;k++)
		if(!visited[k])
			DFS_2(G,k);
}

//      
void BFS(ALGraph G,int v)
{
	int i,k,w;
	My_queue<int> q;
	ArcNode *p;
	visited[v]=true;
	cout<<G.vertices[v].data<<"  ";
	q.push(v);
	
	while(!q.empty())
	{
		w=q.front();
		q.pop();
		for(p=G.vertices[w].firstarc;p!=NULL;p=p->nextarc)
		{
			k=p->adjvex;
			if(!visited[k])
			{
				visited[k]=true;
				cout<<G.vertices[k].data<<"  ";
				q.push(k);
			}
		}
	}
}

void BFS_Traverse(ALGraph G)
{
	int i,k;
	for(i=0;i<G.vexnum;i++)
		visited[i]=false;
	for(k=0;k<G.vexnum;k++)
		if(!visited[k])
			BFS(G,k);
}


int Get_Connect_num(ALGraph G) //        
{
	int i,n=1;
	for(i=0;i<G.vexnum;i++)
		visited[i]=false;
	cout<<"            ："<<endl;
	DFS(G,0);
	cout<<endl;
	for(i=0;i<G.vexnum;i++)
		if(!visited[i])
		{
			n++;
			DFS(G,i);
			cout<<endl;
		}
	return n;
}

int main()
{
	clock_t begin=clock(),end(0);
	ALGraph G;
	CreateDG_ALG(G);
	cout<<"        ：";
	DFS_Traverse_1(G);
	cout<<endl;
	cout<<"          ：";
	DFS_Traverse_2(G);
	cout<<endl;
	cout<<"        ：";
	BFS_Traverse(G);
	cout<<endl;
	int n=Get_Connect_num(G);
	cout<<"         ：";
	cout<<n<<endl;
	end=clock();
	cout<<"         ："<<double(end-begin)<<"ms"<<endl;
	return 0;
}