Adjacency Matrix
邻接矩阵是表示一个图的常用存储表示。它用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。阶为n的图G的邻接矩阵A是n*n的。将G的顶点标签为v_1,v_2,...,v_n。若(v_i,v_j)
\in E(G),A_{ij}=1,否则A_{ij}=0。
Depth-First-Search
是沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
搜索结果:1 2 3 4 5 6 7 8 9 10 11 12
Breadth-First-Search
简称BFS,是一种图形搜索算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。
搜索结果:1 2 3 4 5 6 7 8 9 10 11 12
Implementation
#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define MAXN 100
struct Graph
{
string vertex[MAXN];
int matrix[MAXN][MAXN];
int vertexNum;
int arcNum;
};
int Locate(Graph g,string str)
{
for(int i =0;i<g.vertexNum;i++)
{
if(str == g.vertex[i])
return i;
}
return -1;
}
void CreateDUG(Graph &g) //构造无向图
{
string start,end;
cout << "请输入顶点和边数:"<<endl;
cin>>g.vertexNum>>g.arcNum;
for(int i = 0;i<g.vertexNum;i++)
{
cout<<"请输入第"<<i<<"个顶点:"<<endl;
cin>>g.vertex[i];
}
for(int i = 0;i<g.vertexNum;i++)
{
for(int j = 0;j<g.vertexNum;j++)
{
g.matrix[i][j] = 0;
}
}
for(int i = 0;i <g.arcNum;i++)
{
cout<<"请输入第"<<i<<"条边的起始和结束顶点"<<endl;
cin>>start>>end;
int m = Locate(g,start);
int n = Locate(g,end);
g.matrix[m][n] = 1;
g.matrix[n][m] = 1;
}
}
void CreateUDN(Graph &g) //构造无网
{
string start,end;
int w;
cout << "请输入顶点和边数:"<<endl;
cin>>g.vertexNum>>g.arcNum;
for(int i = 0;i<g.vertexNum;i++)
{
cout<<"请输入第"<<i<<"个顶点:"<<endl;
cin>>g.vertex[i];
}
for(int i = 0;i<g.vertexNum;i++)
{
for(int j = 0;j<g.vertexNum;j++)
{
g.matrix[i][j] = 0;
}
}
for(int i = 0;i <g.arcNum;i++)
{
cout<<"请输入第"<<i<<"条边的起始和结束顶点和权"<<endl;
cin>>start>>end>>w;
int m = Locate(g,start);
int n = Locate(g,end);
g.matrix[m][n] = w;
g.matrix[n][m] = w;
}
}
void CreateDG(Graph &g) //构造有向图
{
string start,end;
cout << "请输入顶点和边数:"<<endl;
cin>>g.vertexNum>>g.arcNum;
for(int i = 0;i<g.vertexNum;i++)
{
cout<<"请输入第"<<i<<"个顶点:"<<endl;
cin>>g.vertex[i];
}
for(int i = 0;i<g.vertexNum;i++)
{
for(int j = 0;j<g.vertexNum;j++)
{
g.matrix[i][j] = 0;
}
}
for(int i = 0;i <g.arcNum;i++)
{
cout<<"请输入第"<<i<<"条边的起始和结束顶点"<<endl;
cin>>start>>end;
int m = Locate(g,start);
int n = Locate(g,end);
g.matrix[m][n] = 1;
}
}
void CreateDN(Graph &g) //构造有向网
{
string start,end;
int w;
cout << "请输入顶点和边数:"<<endl;
cin>>g.vertexNum>>g.arcNum;
for(int i = 0;i<g.vertexNum;i++)
{
cout<<"请输入第"<<i<<"个顶点:"<<endl;
cin>>g.vertex[i];
}
for(int i = 0;i<g.vertexNum;i++)
{
for(int j = 0;j<g.vertexNum;j++)
{
g.matrix[i][j] = 0;
}
}
for(int i = 0;i <g.arcNum;i++)
{
cout<<"请输入第"<<i<<"条边的起始和结束顶点和权"<<endl;
cin>>start>>end>>w;
int m = Locate(g,start);
int n = Locate(g,end);
g.matrix[m][n] = w;
}
}
int FirstAdjVex(Graph g,int v)//返回v的第一个邻接顶点序号
{
for(int i = 0;i<g.vertexNum;i++)
{
if(g.matrix[v][i] == 1)
return i;
}
return -1;
}
int NextAdjVex(Graph g,int v,int w)//返回顶点v相对于w的下一个邻接点序号
{
for(int i = w+1;i<g.vertexNum;i++)
{
if(g.matrix[v][i] == 1)
return i;
}
return -1;
}
bool visted[MAXN];
void DFS(Graph g,int i)
{
cout <<g.vertex[i]<<" ";
visted[i] = true;
for(int w = FirstAdjVex(g,i);w>=0;w = NextAdjVex(g,i,w))
{
if(!visted[i])
DFS(g,w);
}
}
void DFSTransfer(Graph g)
{
for(int i =0;i<g.vertexNum;i++)
{
visted[i] = false;
}
for(int i = 0;i<g.vertexNum;i++)
{
if(!visted[i])
DFS(g,i);
}
cout << endl;
}
void BFS(Graph g,int v)
{
}
void BFSTransfer(Graph g)
{
for(int i =0;i<g.vertexNum;i++)
{
visted[i] = false;
}
std::queue<int> que;
for(int i = 0;i<g.vertexNum;i++)
{
if(!visted[i])
{
que.push(i);
visted[i] = true;
while(!que.empty())
{
int k = que.front();
que.pop();
cout <<g.vertex[k]<<" ";
for(int i = FirstAdjVex(g,k);i>=0;i = NextAdjVex(g,k,i))
{
if(!visted[i])
{
que.push(i);
visted[i] = true;
}
}
}
}
}
cout <<endl;
}
int main()
{
Graph g;
CreateDUG(g);
DFSTransfer(g);
BFSTransfer(g);
return 0;
}
Reference
- 《算法导论》 第22章 图的基本算法P322
- http://en.wikipedia.org/wiki/Breadth-first_search
- http://en.wikipedia.org/wiki/Depth-first_search
分享到:
相关推荐
定义采用邻接矩阵存储的图结构封装DFS、BFS算法
程序用交互方式完成图的邻接矩阵和邻接表的构造,并提供了DFS和BFS算法。
03邻接矩阵深度和广度遍历DFS_BFS.c
设计一个有向图和一个无向图,使用邻接矩阵和邻接表存储结构,完成在这两种存储结构下有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 三、实验要求: 1. 根据实验内容编程,画出你所设计的图,...
分别以邻接矩阵和邻接表的方式实现图的深度优先搜索、广度优先搜索
数据结构图论中,实现邻接矩阵的深度遍历和邻接矩阵广度遍历.
图的邻接矩阵和邻接表存储形式,并实现深度优先遍历和广度优先遍历
基于ADT实现的图的邻接矩阵,包含了基本的图算法的实现,包括BFS,DFS,拓扑排序,Prim,Kruskal,Dijkstra,Floyd,有注释,有测试样例,检验过没问题。
封装DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法 上机作业: 定义采用邻接矩阵存储的图结构
这是用邻接矩阵作存储结构的图类源代码,有完整的注释(每个变量的作用、函数执行的过程的文字描述等)。下面是图类的声明部分: //用邻接矩阵表示的图的类的定义 template class Graph { private: static ...
与图相关的操作,采用邻接矩阵或邻接表作为存储结构,完成有向图和无向图的DFS和BFS操作
头歌数据结构图的邻接表存储及遍历操作 第1关图的邻接表存储及求邻接点操作 第2关图的深度遍历 第3关图的广度遍历 稳过
C++实现,数据结构,图的邻接矩阵表示,深度优先遍历,广度优先遍历,DFS,BFS,为什么要五十个字才能上传啊
C/C++实现 数据结构与算法视频教程 01交换算法 02冒泡排序 ...35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS 共42集,需要哪一块知识自己下,一集3积分
图的基本操作与实现 【问题描述】:自选存储结构,实现对图的...(7)如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图G的邻接表,即复制图G, 然后再执行操作(2);反之亦然。 (8)自选图的其它任一种操作实现之。
图的相关算法比较全面的总结,包括了图的深度和广度遍历算法,prim和kruskal两种最小生成树的算法,邻接矩阵和邻接表两种储存结构,做课程设计、实验报告或者数据结构学习者可以参考参考啊``源代码都是我亲手打的,...
题在压缩文件中,图是用邻接矩阵做的,刚刚接触图的同学可以看一看
可提取出二值图像中的连通区域,得到图像分割结果,为后期处理提供数据。
python实现图数据的遍历,需pip install networkx,采用邻接矩阵,邻接表,实现图数据深度遍历dfs,广度遍历bfs。