# 数据结构(12) -- 图的邻接矩阵的DFS和BFS

```////////////////////////////////////////////////////////
//图的邻接矩阵的DFS和BFS
////////////////////////////////////////////////////////
#include <iostream>
#include <stdlib.h>
#include <queue>
#define MaxVertexNum 100 //最大顶点数
//#define INFINITY 0  //无穷大设为无符号整数的最大值
typedef char VertexType;  //顶点类型设为字符类型
typedef int EdgeType; ///边的权值设为整形
enum GraphType{DG, UG, DN, UN}; //有向图，无向图，有向网图，无向网图
using namespace std;

typedef struct
{
VertexType Vertices[MaxVertexNum]; //顶点表
EdgeType Edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，即边表
int n, e; //顶点数n和边数e
enum GraphType GType;
}MGraph;

void CreateMGraph(MGraph *G)
{
int  i, j, k, w;
G->GType = UN;    /* Undirected Network  无向网图  */
cout << "请输入顶点数和边数(输入格式为:顶点数, 边数):" << endl;
cin >> G->n >> G->e; /* 输入顶点数和边数 */
cout << "请输入顶点信息(输入格式为:顶点号<CR>):" << endl;
for (i = 0; i < G->n; i++)
cin >> &(G->Vertices[i]); /*  输入顶点信息，建立顶点表  */
for (i = 0; i < G->n; i++)
for (j = 0; j < G->n; j++)
G->Edges[i][j] = 0; /* 初始化邻接矩阵 */
cout << "请输入每条边对应的两个顶点的序号和权值，输入格式为:i, j, w:" << endl;
for (k = 0; k < G->e; k++) {
cin >> i >> j >> w; /* 输入e条边上的权，建立邻接矩阵 */
G->Edges[i][j] = w;
G->Edges[j][i] = w; /* 因为无向网图的邻接矩阵是对称的 */
}
}

void Print(MGraph *G)
{
cout << "   ";
for (int i = 0; i < G->n; i++)
cout << G->Vertices[i] << "  ";
cout << endl;
for (int i = 0; i < G->n; i++)
{
cout << G->Vertices[i] << "  ";
for (int j = 0; j < G->n; j++)
{
cout << G->Edges[i][j] << "  ";
}
cout << endl;
}
}

//邻接矩阵存储的图 - DFS
bool Visited[100] = { false };
void DFS(MGraph *G, int k)
{
cout << G->Vertices[k] << " ";
Visited[k] = true;
for (int i = 0; i < G->n; i++)
{
if (G->Edges[k][i] == 1 && Visited[i] == false)
{
DFS(G, i);
}
}
}

//邻接矩阵存储的图 - BFS
void BFS(MGraph *G, int k)
{
bool Visited[100] = { false };
queue<int> q;
for (int i = 0; i < G->n; i++)
Visited[i] = false;

if (Visited[k] == false) //如果节点未访问
{
Visited[k] = true;
cout << " visit vertex: " << G->Vertices[k] << endl;
q.push(k); //u入队列
}
while (!q.empty())
{
int t = q.front();
q.pop();
for (int w = 0; w < G->n; w++)
{
if (G->Edges[t][w] != 0 && Visited[w] == false)
{
Visited[w] = true;
cout << " visited vertex: " << G->Vertices[w] << endl;
q.push(w);
}
}
}
}
int main()
{
MGraph *G = new MGraph;
CreateMGraph(G);
Print(G);
cout << endl;
DFS(G, 0);
//BFS(G, 0);
system("pause");
return 0;
}```

## 数据结构(11) -- 邻接表存储图的DFS和BFS

/////////////////////////////////////////////////////////////// //图的邻接表表示法以及DFS和BFS /////////////////////////////////////////////////////////////// #include <iostream> #include <stdlib.h> #include <queue> using namespace std; //图的邻接表表示法

## 学习笔记：图的DFS和BFS的两种搜索办法

在学习图结构的过程中,DFS和BFS是两种不同的遍历方式,其寻找元素具有不同的优点和缺陷. BFS被称作广度优先算法, 在遍历整个图的过程中,BFS将采用入队的方式进行,值得一提的是,这和树结构中的层序遍历有很大的相似之处. 在层序遍历中,将父亲节点入队后,在父亲节点出队后,将其儿子节点入队. 同理在图的BFS遍历中,先让BFS的首元素入队,在收元素入队后将他的儿子节点入队,放能够实现BFS搜索,他们的整体思想是一样的. 1 void TraversalGraph_BFS(LGraph Gr

## 数据结构之图的邻接表

1.邻接表的简介: 图的邻接矩阵存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构.邻接表由表头结点和表结点两部分组成,其中图中每个顶点均对应一个存储在数组中的表头结点.如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中.如词条概念图所示,表结点存放的是邻接顶点在数组中的索引.对于无向图来说,使用邻接表进行存储也会出现数据冗余,表头结点A所指链表中存在一个指向C的表结点的同时,表头结点C所指链表也会存在一个指向A的表结点.[1] 邻接