欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构学习之图的深度优先遍历和广度优先遍历

程序员文章站 2022-05-20 19:06:15
...

图的遍历的关键是确定每个顶点的邻接顶点,也即是确定由顶点组成的邻接矩阵。

这里参考网上的一篇基于C++的邻接矩阵的实现过程

图类的实现:

#include<iostream>
#include<iomanip>
using namespace std;
//最大权值
#define MAXWEIGHT 100
//用邻接矩阵实现图
class Graph
{
private:
	//是否带权
	bool isWeighted;
	//是否有向
	bool isDirected;
	//顶点数
	int numV;
	//边数
	int numE;
	//邻接矩阵
	int **matrix;
public:
	/*
	构造方法
	numV是顶点数,isWeighted是否带权值,isDirected是否有方向
	*/
	Graph(int numV, bool isWeighted = false, bool isDirected = false);
	//建图
	void createGraph();
	//析构方法
	~Graph();
	//获取顶点数
	int getVerNums()
	{return numV;}
	//获取边数
	int getEdgeNums()
	{return numE;}
	//设置指定边的权值
	void setEdgeWeight(int tail, int head, int weight);
	//打印邻接矩阵
	void printAdjacentMatrix();
	//检查输入
	bool check(int i, int j, int w = 1);
};
图类的定义:

/*
构造方法
numV是顶点数,isWeighted是否带权值,isDirected是否有方向
*/
Graph::Graph(int numV, bool isWeighted, bool isDirected)
{
	while (numV <= 0)
	{
		cout << "输入的顶点数不正确!,重新输入 ";
		cin >> numV;
	}
	this->numV = numV;
	this->isWeighted = isWeighted;
	this->isDirected = isDirected;
	matrix = new int*[numV];  //指针数组
	int i, j;
	for (i = 0; i < numV; i++)
		matrix[i] = new int[numV];
	//对图进行初始化
	if (!isWeighted)  //无权图
	{
		//所有权值初始化为0
		for (i = 0; i < numV; i++)
		for (j = 0; j < numV; j++)
			matrix[i][j] = 0;
	}
	else  //有权图
	{
		//所有权值初始化为最大权值
		for (i = 0; i < numV; i++)
		for (j = 0; j < numV; j++)
			matrix[i][j] = MAXWEIGHT;
	}
}
//建图
void Graph::createGraph()
{
	cout << "输入边数 ";
	while (cin >> numE && numE < 0)
		cout << "输入有误!,重新输入 ";

	int i, j, w;
	if (!isWeighted)  //无权图
	{
		if (!isDirected)  //无向图
		{
			cout << "输入每条边的起点和终点:\n";
			for (int k = 0; k < numE; k++)
			{
				cin >> i >> j;
				while (!check(i, j))
				{
					cout << "输入的边不对!重新输入\n";
					cin >> i >> j;
				}
				matrix[i][j] = matrix[j][i] = 1;
			}
		}
		else  //有向图
		{
			cout << "输入每条边的起点和终点:\n";
			for (int k = 0; k < numE; k++)
			{
				cin >> i >> j;
				while (!check(i, j))
				{
					cout << "输入的边不对!重新输入\n";
					cin >> i >> j;
				}
				matrix[i][j] = 1;
			}
		}
	}
	else  //有权图
	{
		if (!isDirected)   //无向图
		{
			cout << "输入每条边的起点、终点和权值:\n";
			for (int k = 0; k < numE; k++)
			{
				cin >> i >> j >> w;
				while (!check(i, j, w))
				{
					cout << "输入的边不对!重新输入\n";
					cin >> i >> j >> w;
				}
				matrix[i][j] = matrix[j][i] = w;
			}
		}
		else  //有向图
		{
			cout << "输入每条边的起点、终点和权值:\n";
			for (int k = 0; k < numE; k++)
			{
				cin >> i >> j >> w;
				while (!check(i, j, w))
				{
					cout << "输入的边不对!重新输入\n";
					cin >> i >> j >> w;
				}
				matrix[i][j] = w;
			}
		}
	}
}
//析构方法
Graph::~Graph()
{
	int i = 0;
	for (i = 0; i < numV; i++)
		delete[] matrix[i];
	delete[]matrix;
}
//设置指定边的权值
void Graph::setEdgeWeight(int tail, int head, int weight)
{
	if (isWeighted)
	{
		while (!check(tail, head, weight))
		{
			cout << "输入不正确,重新输入边的起点、终点和权值 ";
			cin >> tail >> head >> weight;
		}
		if (isDirected)
			matrix[tail][head] = weight;
		else
			matrix[tail][head] = matrix[head][tail] = weight;
	}
	else
	{
		while (!check(tail, head, 1))
		{
			cout << "输入不正确,重新输入边的起点、终点 ";
			cin >> tail >> head;
		}
		if (isDirected)
			matrix[tail][head] = 1-matrix[tail][head];
		else
			matrix[tail][head] = matrix[head][tail] = 1 - matrix[tail][head];
	}
}
//输入检查
bool Graph::check(int i, int j, int w)
{
	if (i >= 0 && i < numV && j >= 0 && j < numV && w > 0 && w <= MAXWEIGHT)
		return true;
	else
		return false;
}
//打印邻接矩阵
void Graph::printAdjacentMatrix()
{
	int i, j;
	cout.setf(ios::left);
	cout << setw(4) << " ";
	for (i = 0; i < numV; i++)
		cout << setw(4) << i;
	cout << endl;
	for (i = 0; i < numV; i++)
	{
		cout << setw(4) << i;
		for (j = 0; j < numV; j++)
			cout << setw(4) << matrix[i][j];
		cout << endl;
	}
}

调用主函数main:

int main()
{
	cout << "******使用邻接矩阵实现图结构***by David***" << endl;
	bool isDirected, isWeighted;
	int numV;
	cout << "建图" << endl;
	cout << "输入顶点数 ";
	cin >> numV;
	cout << "边是否带权值,0(不带) or 1(带) ";
	cin >> isWeighted;
	cout << "是否是有向图,0(无向) or 1(有向) ";
	cin >> isDirected;
	Graph graph(numV, isWeighted, isDirected);
	cout << "这是一个";
	isDirected ? cout << "有向、" : cout << "无向、";
	isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;
	graph.createGraph();
	cout << "打印邻接矩阵" << endl;
	graph.printAdjacentMatrix();
	cout << endl;
	int tail, head, weight;
	cout << "修改指定边的权值" << endl;
	if (isWeighted)  //针对有权图
	{
		cout << "输入边的起点、终点和权值 ";
		cin >> tail >> head >> weight;
		graph.setEdgeWeight(tail, head, weight);
	}
	else  //针对无权图
	{
		cout << "输入边的起点、终点 ";
		cin >> tail >> head;
		graph.setEdgeWeight(tail, head, 1);
	}
	cout << "修改成功!" << endl;
	cout << "打印邻接矩阵" << endl;
	graph.printAdjacentMatrix();
	system("pause");
	return 0;
}
以上是计算有向/无向和有权/无权图的顶点邻接矩阵。

参考博文:http://blog.csdn.net/zhangxiangdavaid/article/details/38321327

下面是一个图的深度优先遍历和广度优先遍历的实例:

深度优先遍历:

/*
深度优先搜索
从vertex开始遍历,visit是遍历顶点的函数指针
*/
void Graph::dfs(int vertex, void (*visit)(int))
{
	stack<int> s;
	//visited[i]用于标记顶点i是否被访问过
	bool *visited = new bool[numV];
	//count用于统计已遍历过的顶点数
	int i, count;
	for (i = 0; i < numV; i++)
		visited[i] = false;
	count = 0;
	while (count < numV)
	{
		visit(vertex);
		visited[vertex] = true;
		s.push(vertex);
		count++;
		if (count == numV)
			break;
		while (visited[vertex])
		{
			for (i = 0; i < numV
				&& (visited[i] 
				|| matrix[vertex][i] == 0 || matrix[vertex][i] == MAXWEIGHT); i++);
			if (i == numV)  //当前顶点vertex的所有邻接点都已访问完了
			{
				if (!s.empty())
				{
					s.pop();   //此时vertex正是栈顶,应先出栈
					if (!s.empty())
					{
						vertex = s.top();
						s.pop();
					}
					else  //若栈已空,则需从头开始寻找新的、未访问过的顶点
					{
						for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
					}
				}
				else  //若栈已空,则需从头开始寻找新的、未访问过的顶点
				{
					for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
				}
			}
			else  //找到新的顶点应更新当前访问的顶点vertex
				vertex = i;
		}
	}
	delete[]visited;
}
广度优先遍历:

/*
广度优先搜索
从vertex开始遍历,visit是遍历顶点的函数指针
*/
void Graph::bfs(int vertex, void(*visit)(int))
{
	//使用队列
	queue<int> q;
	//visited[i]用于标记顶点i是否被访问过
	bool *visited = new bool[numV];
	//count用于统计已遍历过的顶点数
	int i, count;
	for (i = 0; i < numV; i++)
		visited[i] = false;
	q.push(vertex);
	visit(vertex);
	visited[vertex] = true;
	count = 1;
	while (count < numV)
	{
		if (!q.empty())
		{
			vertex = q.front();
			q.pop();
		}
		else
		{
			for (vertex = 0; vertex < numV && visited[vertex]; vertex++);
			visit(vertex);
			visited[vertex] = true;
			count++;
			if (count == numV)
				return;
			q.push(vertex);
		}
		//代码走到这里,vertex是已经访问过的顶点
		for (int i = 0; i < numV; i++)
		{
			if (!visited[i] && matrix[vertex][i] > 0 && matrix[vertex][i] < MAXWEIGHT)
			{
				visit(i);
				visited[i] = true;
				count ++;
				if (count == numV)
					return;
				q.push(i);
			}
		}
	}
	delete[]visited;
}
主调用函数:

void visit(int vertex)
{
	cout << setw(4) << vertex;
}
int main()
{
	cout << "******图的遍历:深度优先、广度优先***by David***" << endl;
	bool isDirected, isWeighted;
	int numV;
	cout << "建图" << endl;
	cout << "输入顶点数 ";
	cin >> numV;
	cout << "边是否带权值,0(不带) or 1(带) ";
	cin >> isWeighted;
	cout << "是否是有向图,0(无向) or 1(有向) ";
	cin >> isDirected;
	Graph graph(numV, isWeighted, isDirected);
	cout << "这是一个";
	isDirected ? cout << "有向、" : cout << "无向、";
	isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;
	graph.createGraph();
	cout << "打印邻接矩阵" << endl;
	graph.printAdjacentMatrix();
	cout << endl;
	cout << "深度遍历" << endl;
	for (int i = 0; i < numV; i++)
	{
		graph.dfs(i, visit);
		cout << endl;
	}
	cout << endl;
	cout << "广度遍历" << endl;
	for (int i = 0; i < numV; i++)
	{
		graph.bfs(i, visit);
		cout << endl;
	}
	system("pause");
	return 0;
}
参考自博文:http://blog.csdn.net/zhangxiangdavaid/article/details/38323633

下面是参考《大话数据结构》上的C语言实现的图的深度遍历和广度遍历:

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

#define MAXVEX 100
#define MAX 100
#define INFINITY 65535
#define MAXSIZE 100

typedef int VertexType;
typedef int EdgeType;
typedef int Boolean;
Boolean visited[MAX];
typedef int QElemType;

typedef struct{
    QElemType data[MAXSIZE];
    int front;
    int rear;
}Queue;


typedef struct{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
}MGraph;

void CreateMGraph(MGraph *g)
{
    int i,j,k,w;
    cout<<" 请输入顶点数和边数:"<<endl;
    //scanf("%d,%d",&g->numVertexes,&g->numEdges);
    cin>>g->numVertexes;
    cin>>g->numEdges;
    for(i=0;i<g->numVertexes;i++){
        //scanf(&g->vexs[i]);
        cin>>g->vexs[i];
    }
    for(i=0;i<g->numVertexes;i++){
        for(j=0;j<g->numVertexes;j++){
            g->arc[i][j]=INFINITY;
        }
    }
    for(k=0;k<g->numEdges;k++){
        cout<<"输入边(vi,vj)上的下标i,下标j和权w:"<<endl;
        //scanf("%d,%d,%d",&i,&j,&w);
        cin>>i;
        cin>>j;
        cin>>w;
        g->arc[i][j]=w;
        g->arc[j][i]=g->arc[i][j];
    }
}

void DFS(MGraph *g,int i)
{
    int j;
    visited[i]=1;
    cout<<" G.vexs[i]= "<<g->vexs[i]<<" i= "<<i<<endl;
    for(j=0;j<g->numVertexes;j++){
        if(g->arc[i][j]==1  && !visited[j]){
            cout<<"j= "<<j;
            DFS(g,j);
        }
    }
}
void DFSTraverse(MGraph *g)
{
    int i;
    for(i=0;i<g->numVertexes;i++){
        visited[i]=0;
    }
    for(i=0;i<g->numVertexes;i++){
        if(!visited[i]){
            cout<<"in Traverse i= "<<i<<endl;
            DFS(g,i);
        }
    }
}

int InitQueue(Queue *Q)
{
    Q->front=0;
    Q->rear=0;

    return 0;
}
int EnQueue(Queue *Q,QElemType e)
{
    if((Q->rear+1)%MAXSIZE == Q->front) ///判断队列是f否满
       return -1;
       Q->data[Q->rear]=e;
       Q->rear=(Q->rear+1)%MAXSIZE;

       return 0;
}
int DeQueue(Queue *Q,QElemType *e)
{
    if(Q->front == Q->rear)
        return -1;
    *e=Q->data[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;

    return 0;
}
int QueueEmpty(Queue *Q)
{
    if(Q->rear == Q->front)
        return -1;
    return 0;
}
///广度优先遍历
void BFSTraverse(MGraph *G)
{
    int i,j;
    Queue Q;
    for(i=0;i<G->numVertexes;i++)
        visited[i]=0;
        InitQueue(&Q); ///初始化辅助队列
        for(i=0;i<G->numVertexes;i++){   ///循环访问每一个顶点
            if(!visited[i]){   ///处理未访问过的
                visited[i]=1;
                cout<<"G->vexs[i]= "<<G->vexs[i];
                EnQueue(&Q,i);  ///此顶点入队列
                while(!QueueEmpty(&Q)){  ///判断当前队列是否为空
                    DeQueue(&Q,&i); ///队中元素出队列
                    for(j=0;j<G->numVertexes;j++){   ///判断其他与此顶点有共同边的顶点
                        if(G->arc[i][j]==1 &&!visited[j]){  ///判断是否访问过
                            visited[j]=1;  ///标记已经访问过
                            cout<<" g->vexs[j]= "<<G->vexs[j]<<endl;
                            EnQueue(&Q,j); ///将找到的顶点入队列
                        }
                    }
                }
             }
        }
}
int main()
{
   MGraph *g;
   g=(MGraph *)malloc(sizeof(MGraph));
   CreateMGraph(g);
   ///DFSTraverse(g);  ///深度优先遍历
   BFSTraverse(g);  ///广度优先遍历

    return 0;
}
上面的C版本实现用到了队列/栈的思想,但是从验证上看貌似有些问题,有细心看出来的同学可以留言指点出来