一、以邻接矩阵的存储方式，进行广度优先搜索遍历，

图以邻接矩阵存储的存储结构

//邻接矩阵的存储结构
const int maxvnum= 10//{图的最大顶点数，它要大于等于具体图的顶点数n}
const int maxenum =10;//图的最大变数，它要大于等于具体图的变数e；
typedef int weightType;//定义边的权值类型
const weightType maxvalue=999999999;//特定权值，要大于等于所有权值之和
typedef int adjmatrix [maxvnum][maxvnum];//定义adjmatrix为存储邻接矩阵的数组类型

邻接矩阵的初始化

void InitMatrix(adjmatrix GA,int k)//邻边矩阵初始化
{
//假定k等于0为无权图，k =0，为有权图
int j,i;
for(i=0;i<maxvnum;i++)
{
for( j=0;j<maxvnum;j++)
{
if(i==j) GA[i][j]=0;
else if(k) GA[i][j] =maxvalue;
else GA[i][j]=0;
}
}
}

根据一个图的边集生成邻接矩阵的算法

void CreatMatrix(adjmatrix GA,int n,char*s,int k1,int k2)
{
//k1为0，则为无向图，否则为有向图；k2为0则为无权图，否则为有权图；
//s字符串用来保存一个图的边集，n为图的顶点数
istrstream sin(s);
char c1,c2,c3;
int i,j;
weightType w;//保存权值
sin>>c1;//将字符串‘{’吃掉；
if(k1==0&&k2==0)
//建立无向无权图
do{
sin>>c1>>i>>c2>>j>>c3;//从sin流读入和处理一条边（即字符串s）
GA[i][j]=GA[j][i]=1;
sin>>c1;
if(c1=='}')break;
}while(1);
if(k1!=0&&k2==0) //建立有向无权图
do{
sin>>c1>>i>>c2>>j>>c3;
GA[i][j]=1;
sin>>c1;
if(c1=='}')break;
}while(1);
if(k1==0&&k2!=0)//建立无向有权图
do{
sin>>c1>>i>>c2>>j>>c3>>w;//w为权值
GA[i][j]=GA[j][i]=w;
sin>>c1;
if(c1=='}')break;
}while(1);
if(k1!=0&&k2!=0)//有向有权图
do{
sin>>c1>>i>>c2>>j>>c3>>w;
GA[i][j]=w;
sin>>c1;
if(c1=='}')break;
}while(1);
}

根据图的邻接矩阵输出图的二元组表示（顶点集和边集）

void PrintMatrix(adjmatrix GA,int n,int k1,int k2)
{//
int i,j;
cout<<"V={";
//输出顶点集开始
for(i=0;i<n-1;i++) cout<<i<<',';
cout<<n-1<<"}"<<endl;
//输出顶点集结束
cout<<"E={";
//输出边集开始
if(k2==0){
//对无权图的处理情况
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(GA[i][j]==1)
if(k1==0){
//对无向无权图处理
if(i<j) cout<<"("<<i<<","<<j<<')'<<',';
}
else
cout<<'<'<<i<<','<<j<<'>'<<',';
}
else{
//对有权图的处理情况
for(i=0;i<n;j++)
for(j=0;j<n;j++)
if(GA[i][j]!=0&&GA[i][j]!=maxvalue)
if(k1==0){
//对无向有权图
if(i<j)
cout<<'('<<','<<j<<'>'<<GA[i][j]<<',';
}
else
cout<<'<'<<i<<','<<j<<'>'<<GA[i][j]<<',';
}
cout<<'}'<<endl;
}

以邻接矩阵的存储方式深度优先搜索遍历

void dfsMatrix(adjmatrix GA,int i,int n,bool*visited)
{//从初始点i开始出发进行深度优先搜索邻接矩阵GA表示的图
cout<<i<<" ";
visited[i]=true;//标记i点已经被访问过
for(int j=0;j<n;j++)//依次搜索i点的每个邻接点
if(GA[i][j]!=0 &&GA[i][j]!=maxvalue &&!visited[i])
{
dfsMatrix(GA,j,n,visited);//若i的某个有效邻接点j未被访问过，则从j进行递归调用
}
}

以邻接矩阵存储方式进行广度优先搜索遍历

void bfsMatrix(adjmatrix GA, int i,int n,bool *visited)
{
const int Maxsize = 30;
int front=0,rear=0;
int q[Maxsize]={0};
cout<<i<<' ';
visited[i]=true;
q[++rear]= i;
while(front!=rear)
{front=(front+1)%Maxsize;
int k = q[front];
for(int j=0; j<n; j++)
{
if(GA[k][j]!=0 &&GA[k][j]!=maxvalue &&!visited[j])
{
cout<<j<<' ';
visited[j]=true;
rear=(rear+1)%Maxsize;
q[rear]=j;
}
}
}

二）.以邻接表的存储方式进行的深度优先搜索遍历

1.邻接表的存储结构3.

typedef int weightType;//权值类型
const int MAX = 10;//最大顶点数，可任意定义
struct edgenode
{
int adjvex;//顶点
weightType weight;//权值
edgenode *next;
};
typedef edgenode *adjlist[MAX];

2.邻接表的初始化

void InitAdjoin(adjlist GL)
{
for(int i = 0;i<MAX;i++)
GL[i]=NULL;
}

3.根据一个图的边集生成邻接表

void CreateAdjoin(adjlist GL,int n, char*s,int k1,int k2)
{
istrstream sin(s);
char c1,c2,c3;
int i,j;
weightType w;
edgenode *p;
sin>>c1;
if(k2==0)
{
do{
sin>>c1>>i>>c2>>j>>c3;
p=new edgenode;
p->adjvex =j;
p->weight =1;
p->next = GL[i];
GL[i]=p;
if(k1==0)
{
p=new edgenode;
p->adjvex =i;
p->weight =1;
p->next = GL[j];
GL[j]=p;
}
sin>>c1;
}while(c1==',');
}
else
{
do{
sin>>c1>>i>>c2>>j>>c2>>w;
p=new edgenode;
p->adjvex =j;
p->weight =w;
p->next = GL[i];
GL[i]=p;
if(k1==0)
{p=new edgenode;
p->adjvex =i;
p->weight =w;
p->next = GL[j];
GL[j]=p;
}
sin>>c1;
}while(c1==',');
}
}

4.图以邻接表的存储结构深度优先搜索遍历

void dfsAdjoin(adjlist GL,int i,int n,bool*visited)
{
cout<<i<<' ';
visited[i]=true;
edgenode*p=GL[i];
while(p!=NULL)
{
int j = p->adjvex;
if(!visited[j])
dfsAdjoin(GL,j,n,visited);
p=p->next;
}
}

三、结果分析

深度优先遍历： 类似与树的前序遍历。从图中的某个顶点v出发，访问此顶点，然后从v的未被访问到的邻接点进行遍历，直到图中所有和v有路径相通的顶点都被访问到（注：优先访问外层节点，访问到无新顶点时，会进行回退，访问未被访问过的分支顶点）。

广度优先遍历： 类似于树的层序遍历。从图中的某个顶点w出发，让顶点w入队，然后顶点w再出队，并让所有和顶点w相连的顶点入队，然后再出队一个顶点t，并让所有和t相连但未被访问过的顶点入队……由此循环，指定图中所有元素都出队。

最后

以上就是鲜艳发卡为你收集整理的以邻接矩阵的存储方式，进行广度优先搜索遍历，以邻接表的存储方式，进行深度优先遍历 一、以邻接矩阵的存储方式，进行广度优先搜索遍历，二）.以邻接表的存储方式进行的深度优先搜索遍历三、结果分析的全部内容，希望文章能够帮你解决以邻接矩阵的存储方式，进行广度优先搜索遍历，以邻接表的存储方式，进行深度优先遍历 一、以邻接矩阵的存储方式，进行广度优先搜索遍历，二）.以邻接表的存储方式进行的深度优先搜索遍历三、结果分析所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。