图的广度和深度优先遍历(邻接矩阵)

 

typedef struct
{
	int edges[MAX_Size][MAX_Size];//存放边的关系
	char  vex[MAX_Size];//存放顶点的值
	int n ,e;//分别为顶点数目和边的数目
}MGrap;

/建立有向图的邻接矩阵表示
void createGrap(MGrap *g)
{
	
	cout <<"请输入顶点数和边的数"<<endl;
	cin>>g->n>>g->e;
	cout<<"请输入顶点信息"<<endl;
	for (int i =0;i<g->n;i++)
	{
		cin>>g->vex[i];
	}
	//初始化矩阵
	for (int i =0;i<g->n;i++)
	{
		for (int j =0;j<g->n;j++)
		{
			g->edges[i][j] = 0;
		}
	}
	cout<<"请输入边的信息:起始边和终止边"<<endl;
	for (int i =0;i<g->e;i++)
	{
		int start, end;
		cin>>start>>end;
		g->edges[start][end] = 1;
	}
}

 

//邻接矩阵的深度遍历 非递归形式

//深度优先遍历
int visit[MAX_Size] = {0};
void  DFS(MGrap g,int v)
{
	
	visit[v] = 1;
	cout<<g.vex[v]<<endl;
	for (int i =0;i<g.n;i++)
	{
		if (g.edges[v][i]==1&&visit[i]==0)
					DFS(g,i);
		{
		}
		
	}

}

 

void DFSWithRecursion(MGrap *g,int v)
{
	stack<int> s;
	if (visit[v]== 0)
	{
		visit[v] =1;
		cout<<g->vex[v]<<endl;
		s.push(v);
		
		while(!s.empty())
		{
			int m = s.top();
			int i ;
			for  (i=0;i<g->n;i++)
			{
				if (g->edges[m][i]==1&& visit[i]==0)
				{
					cout<<g->vex[i]<<endl;
					visit[i] =1;
					s.push(i);//每次找到一个没有访问的节点就好
					break;
				}//有疑问
				
			}
			if (i == g->n)
			{
				s.pop();
			}
			

		}
		
	}
}

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
#include<map>
#include<stack>
#include <queue>
#define MAX_Size 100
using namespace std;
//
//  BinaryTreeNode.h
//  BinaryTreeNode
//
//  Created by 吴珝君 on 2018/12/25.
//  Copyright  ©   2018年 闲着也是贤者. All rights reserved.
//
//邻接矩阵
typedef struct
{
	int no;//顶点信息
	char info;
}VertexType;
typedef struct
{
	int edges[MAX_Size][MAX_Size];//存放边的关系
	char  vex[MAX_Size];//存放顶点的值
	int n ,e;//分别为顶点数目和边的数目
}MGrap;


//建立有向图的邻接矩阵表示
void createGrap(MGrap *g)
{
	
	cout <<"请输入顶点数和边的数"<<endl;
	cin>>g->n>>g->e;
	cout<<"请输入顶点信息"<<endl;
	for (int i =0;i<g->n;i++)
	{
		cin>>g->vex[i];
	}
	//初始化矩阵
	for (int i =0;i<g->n;i++)
	{
		for (int j =0;j<g->n;j++)
		{
			g->edges[i][j] = 0;
		}
	}
	cout<<"请输入边的信息:起始边和终止边"<<endl;
	for (int i =0;i<g->e;i++)
	{
		int start, end;
		cin>>start>>end;
		g->edges[start][end] = 1;
	}
}
//邻接矩阵的深度遍历 非递归形式

//深度优先遍历
int visit[MAX_Size] = {0};
void  DFS(MGrap g,int v)
{
	
	visit[v] = 1;
	cout<<g.vex[v]<<endl;
	for (int i =0;i<g.n;i++)
	{
		if (g.edges[v][i]==1&&visit[i]==0)
					DFS(g,i);
		{
		}
		
	}

}
void DFSWithRecursion(MGrap *g,int v)
{
	stack<int> s;
	if (visit[v]== 0)
	{
		visit[v] =1;
		cout<<g->vex[v]<<endl;
		s.push(v);
		
		while(!s.empty())
		{
			int m = s.top();
			int i ;
			for  (i=0;i<g->n;i++)
			{
				if (g->edges[m][i]==1&& visit[i]==0)
				{
					cout<<g->vex[i]<<endl;
					visit[i] =1;
					s.push(i);//每次找到一个没有访问的节点就好
					break;
				}//有疑问
				
			}
			if (i == g->n)
			{
				s.pop();
			}
			

		}
		
	}
}
void DFSTraverse(MGrap g)
{
	for (int i =0; i<g.n;i++)
	{
		if (visit[i] ==0)
		{
			DFS(g,i);
		}
	}

}

//广度优先遍历
void BFSTraverse(MGrap g)
{
	queue<int> q;
	
	for (int i= 0;i<g.n;i++)
	{
		if (visit[i]==0)
		{
			visit[i] = 1;
			cout<<g.vex[i]<<endl;
			q.push(i);
		}
		while(!q.empty())
		{
			int m = q.front();
			q.pop();
		for (int j =0;j<g.n;j++)
		{
			if (g.edges[m][j]==1&& visit[j]==0)
			{
				visit[j] =1;
				cout <<g.vex[j]<<endl;
				q.push(j);
			}
			
		}

		}
	}
	
}
int main()
{
	MGrap g;
	createGrap(&g);
	//DFSTraverse(g);
	//BFSTraverse(g);
	for (int i=0;i<4;i++)
	{
		DFSWithRecursion(&g,i);
	}
	
	system("pause");
}