《数据结构》图存储遍历示例

??? 大家好，图是一种复杂的结构，存储结构较复杂，下面是一个具体图的邻接矩阵存储方法示例，并实现了深度优先和广度优先遍历输出。

#include<iostream>
using namespace std;
const int MaxSize=10;

template <class DataType>
class MGraph
{
public:
   MGraph(DataType a[ ],int n,int e);    //构造函数，建立具有n个顶点e条边的图
   ~MGraph( ) { }                     //析构函数为空
   void DFSTraverse(int v);              //深度优先遍历图
   void BFSTraverse(int v);               //广度优先遍历图
private:
    DataType vertex[MaxSize];          //存放图中顶点的数组
    int arc[MaxSize][MaxSize];          //存放图中边的数组
    int vertexNum,arcNum;             //图的顶点数和边数
};

template <class DataType>
MGraph<DataType>::MGraph(DataType a[ ],int e)
{	int i,j;
	vertexNum=n; arcNum=e;
	for (i=0; i<vertexNum; i++)
		vertex[i]=a[i];
	for (i=0; i<vertexNum; i++)
        for (j=0; j<vertexNum; j++)
			arc[i][j]=0;
	for (int k=0; k<arcNum; k++)
	{	cout<<"请输入边的两个顶点的序号：";
		cin>>i;
		cin>>j;
		arc[i][j]=1; arc[j][i]=1;	
	}
}

template <class DataType>
void MGraph<DataType>::DFSTraverse(int v)
{	cout << vertex[v]; visited[v] = 1;
	for (int j = 0; j < vertexNum; j++)
		if (arc[v][j] == 1 && visited[j]==0) 
			DFSTraverse(j);
}

template <class DataType>
void MGraph<DataType>::BFSTraverse(int v)
{	int Q[MaxSize];
	int front = -1,rear = -1;   //初始化队列,假设队列采用顺序存储且不会发生溢出
	cout << vertex[v]; visited[v] = 1;  Q[++rear] = v;   //被访问顶点入队
	while (front != rear)                   //当队列非空时
	{	v = Q[++front];                   //将队头元素出队并送到v中
		for (int j = 0; j < vertexNum; j++)
			if (arc[v][j] == 1 && visited[j] == 0 ) 
			{ cout << vertex[j]; 
			  visited[j] = 1; 
			  Q[++rear] = j;
			}
	}
}
 int visited[MaxSize];
 
int main( )
{   int n,e;
    char ch[MaxSize];
	for(int i=0;i<MaxSize;i++)
		visited[i]=0;
        cout<<"请输入顶点数和边数：";
	    cin>>n>>e;
        cout<<endl<<"请输入顶点：";
    for(int i=0;i<n;i++)
        cin>>ch[i];
	MGraph<char> MG(ch,n,e);
	cout<<"深度优先遍历序列是：";
	MG.DFSTraverse(0);
	cout<<endl;
	for (int i=0; i<MaxSize; i++)
		visited[i]=0;
    cout<<"广度优先遍历序列是：";
	MG.BFSTraverse(0);
	cout<<endl;
	system("pause");
    return 0;
}

运行时界面和输入如下：

请输入顶点数和边数：7? ?11

请输入顶点：A? B? C? D? E? F? G

请输入边顶点：0? 1

请输入边顶点：0 ?3

请输入边顶点：1? 3

请输入边顶点：1 ?2

请输入边顶点：1? 4

请输入边顶点：2? 4

请输入边顶点：3? 4

请输入边顶点：3? 5

请输入边顶点：4 ?5

请输入边顶点：5? 6

深度优先遍历顺序为：A B C E D F G

广度优先遍历顺序为：A B D C E F G

大家可以尝试存储其它图，也可以使用邻接表来存放。祝大家成功！

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!