DFS和BFS的实现(邻接矩阵、邻接表)
程序员文章站
2023-12-25 18:22:57
...
DFS和BFS的实现(邻接矩阵)
#include<iostream>
#include<queue>
using namespace std;
#define OK 1
#define Maxint 0
typedef int status ;
bool visited[10];
typedef struct
{
char vexs[100];
int arcs[100][100];
int vexnum,arcnum;
}AMGraphy;
status LocateVex(AMGraphy G,int u)
{
int i;
for(i=1;i<=G.vexnum;i++)
if(u==G.vexs[i]) return i;
return -1;
}
status CreateUDN(AMGraphy &G)
{//采用邻接矩阵表示法,创建无向网G
cin>>G.vexnum>>G.arcnum; //输入总顶点数,总边数
for(int i=1;i<=G.vexnum;i++)
cin>>G.vexs[i]; //依次输入点的信息
for(int i=1;i<=G.vexnum;i++) //初始化邻接矩阵,边的权值均为Maxint
for(int j=1;j<=G.vexnum;j++)
G.arcs[i][j]=Maxint;
for(int k=1;k<=G.arcnum;k++) //构造邻接矩阵
{
char v1,v2;
int w;
cin>>v1>>v2>>w; //输入一条边依附的顶点及权值
int i=LocateVex(G,v1);
int j=LocateVex(G,v2); //确定v1,v1在G中的位置,即顶点数组的下标
G.arcs[i][j]=w; //边<v1,v2>的权值置为w
G.arcs[j][i]=G.arcs[i][j]; //置<v1,v2>的对称边<v2,v1>的权值为w
}
return OK;
}
DFS(AMGraphy G,int v)
{
cout<<v<<" ";visited[v]=true;
for(int w=1;w<=G.vexnum;w++)
if((G.arcs[v][w]!=0)&&(!visited[w]))
DFS(G,w);
}
BFS(AMGraphy G,int v)
{
for(int i=1;i<=G.vexnum;i++)
visited[i]=false;
cout<<v<<" ";
visited[v]=true;
queue<int> Q;
Q.push(v);
while(!Q.empty())
{
int t=Q.front();
Q.pop();
for(int w=1;w<=G.vexnum;w++)
{
if(G.arcs[t][w]==1 && visited[w]==false)
{
visited[w]=true;
cout<<w<<" ";
Q.push(w);
}
}
}
}
int main()
{
AMGraphy G;
CreateUDN(G);
cout<<"邻接矩阵为:"<<endl;
for(int i=1;i<=G.vexnum;i++)
{
for(int j=1;j<=G.vexnum;j++)
cout<<G.arcs[i][j]<<" ";
cout<<endl;
}
cout<<"DFS遍历结果为:"<<endl;
DFS(G,2);
cout<<endl;
cout<<"BFS遍历结果为:"<<endl;
BFS(G,1);
return 0;
}
以这个图为例运行:
DFS和BFS的实现(邻接表)
#include<iostream>
#include<queue>
using namespace std;
#define MVNum 100 //最大顶点数
#define OK 1
typedef int status;
bool visited[10];
typedef struct ArcNode //边结点
{
int adjvex; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
}ArcNode;
typedef struct VNode
{
char data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct
{
AdjList vertices; //vertics--vertex的负数
int vexnum,arcnum; //图的当前顶点数和弧数
}ALGraph;
status LocateVex(ALGraph &G,char u)
{
int i;
for(i=1;i<=G.vexnum;i++)
if(u==G.vertices[i].data) return i;
return -1;
}
status CreateUDG(ALGraph &G)
{
cin>>G.vexnum>>G.arcnum; //输入总顶点数,总边数
for(int i=1;i<=G.vexnum;i++)//输入各点,构造表头结点表
{
cin>>G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc=NULL; //初始化表头结点的指针域
}
getchar();
for(int k=1;k<=G.arcnum;k++) //输入各边构造邻接表
{
char v1,v2;
cin>>v1>>v2; //输入一条边依附的两个顶点
getchar();
int i=LocateVex(G,v1);
int j=LocateVex(G,v2);
ArcNode *p1,*p2;
p1=new ArcNode;
p1->adjvex=j; //邻接点序号为j
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1; //将新结点*p1插入顶点vi的边表头部
p2=new ArcNode;
p2->adjvex=i; //邻接点序号为i
p2->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p2; //将新结点*p2插入顶点vj的边表表头
}
return OK;
}
DFS(ALGraph G,int v)
{
ArcNode *p;
p=new ArcNode;
cout<<v<<" ";visited[v]=true;
p=G.vertices[v].firstarc;
while(p!=NULL)
{
int w=p->adjvex;
if(!visited[w]) DFS(G,w);
p=p->nextarc;
}
}
BFS(ALGraph G,int v)
{
int i=0;
for(i=1;i<=G.vexnum;i++)
visited[i]=false;
cout<<v<<" ";
visited[v]=true;
queue<int> Q;
Q.push(v);
ArcNode *p;
p=new ArcNode;
while(!Q.empty())
{
int t=Q.front();
Q.pop();
for(p=G.vertices[t].firstarc;p!=NULL;p=p->nextarc)
{
if(!visited[p->adjvex])
{
cout<<p->adjvex<<" ";
visited[p->adjvex]=true;
Q.push(p->adjvex);
}
}
}
}
int main()
{
ALGraph G;
ArcNode *p;
CreateUDG(G);
cout<<"输出邻接表:"<<endl;
for(int i=1;i<=G.vexnum;i++)
{
cout<<G.vertices[i].data;
for(p=G.vertices[i].firstarc;p!=NULL;p=p->nextarc)
printf("->%d",p->adjvex);
cout<<endl;
}
cout<<endl;
cout<<"DFS遍历结果为:"<<endl;
DFS(G,2);
cout<<endl;
cout<<"BFS遍历结果为:"<<endl;
BFS(G,1);
return 0;
}
以这个图为例运行:
推荐阅读
-
【图的建立】邻接矩阵/邻接表C语言实现
-
DFS和BFS的实现(邻接矩阵、邻接表)
-
数据结构-图的创建(邻接矩阵,邻接表)C语言实现
-
数据结构【完整代码】之(C语言实现【图的存储创建遍历】邻接矩阵与邻接表)
-
无向图的邻接矩阵和邻接表实现各种操作 -- C++语言描述
-
[PHP] 算法-邻接矩阵图的广度和深度优先遍历的PHP实现
-
python实现图的深度优先搜索(DFS)和广度优先搜索(BFS)算法及Dijkstra最短路径应用
-
数据结构-图的深度遍历和广度遍历-邻接矩阵-邻接表
-
图的深度优先搜索(DFS)和广度优先搜索(BFS)及其Java实现
-
实现树的深度优先搜索(DFS)和广度优先搜索(BFS)