数据结构-图的遍历

一.深度优先搜素

遍历：把图中的每一个顶点访问一遍

把自己所能看见灯任意点亮然后依次进行点亮操作,当自己所能看见的灯全都被点亮，也不能直接从节点退出，而是回退然后继续进行上述操作

当所有的灯都被点亮了,一定要原路返回直到返回到出口再出去

二.广度优先搜索

BFS与二叉树的层次遍历相似,需要先指定一个起点，然后将起始点压入队列然后进入队列循环,弹出来的时候就顺序的把直接跟它有边相连的这些点一一的压入队列,然后以此类推

三. 为什么需要两种遍历

因为只有一种遍历方式并不能很好解决所有的问题

四.图不连通的情况

从V到v1到v2到W之间有一条路径,有回环路的路径称为副复杂路径

邻接表存储的图-遍历

#include<iostream>
using namespace std;
#define MaxVertenNum 100/*最大顶点数设为100*/
typedef int Vertex;/*用顶点下标表示顶点为整形*/
typedef int WeightType;/*顶点存放的数据类型设为字符型*/
typedef char DataType;/*顶点存放的数据类型设为字符型*/
#include<queue>
bool Visited[MaxVertenNum] = { false };/*用来表示这个顶点是否被访问过了*/
/*定义边*/
typedef struct ENode* PtrToENode;
struct ENode
{Vertex V1, V2;/*有向图<v1,v2>*/WeightType Weight;/*权重*/
};
typedef  PtrToENode Edge;
/*邻接点的顶点*/
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode
{Vertex Adjx;/*邻接点下标*/WeightType Weight;/*边权重*/PtrToAdjVNode Next;/*指向下一个邻接点*/
};
typedef struct Vnode {PtrToAdjVNode FirstEdge;/*边表头指针*/DataType Data;/*存储结点的数据*/
}AdjList[MaxVertenNum];/*是*//*图结点的定义*/
typedef struct GNode* PtrToGNode;
typedef struct GNode {int Nv;/*顶点数*/int Ne;/*边数*/AdjList G;/*邻接表*/
};
typedef PtrToGNode LGraph;/*邻接表方式存储*/
LGraph CreateGraph(int VertexNum) {/*初始化一个有VN个顶点没有边的图*/Vertex V;LGraph Graph;Graph = new GNode();Graph->Nv = VertexNum;Graph->Ne = 0;for (V = 0; V < Graph->Nv; V++) {Graph->G[V].FirstEdge = NULL;}return Graph;
}
void InsertEdge(LGraph Graph, Edge E) {PtrToAdjVNode NewNode;/* 插入边 <V1, V2> *//* 为V2建立新的邻接点 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->Adjx = E->V2;/* 将V2插入V1的表头 */NewNode->Next = Graph->G[E->V1].FirstEdge;Graph->G[E->V1].FirstEdge = NewNode;/* 若是无向图，还要插入边 <V2, V1> *//* 为V1建立新的邻接点 */NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));NewNode->Adjx = E->V1;/* 将V1插入V2的表头 */NewNode->Next = Graph->G[E->V2].FirstEdge;Graph->G[E->V2].FirstEdge = NewNode;}
LGraph BuildGraph() {LGraph Graph;Edge E;Vertex V;int Nv, i;cin >> Nv;Graph = CreateGraph(Nv);cin >> Graph->Ne;if (Graph->Ne != 0) {E = new ENode();for (int i = 0; i < Graph->Ne; i++) {cin >> E->V1 >> E->V2;InsertEdge(Graph, E);}}return Graph;
}
void BFS(LGraph Graph ,Vertex V) {PtrToAdjVNode W;cout << V << endl;Visited[V] = true;queue<Vertex>q;q.push(V);while (!q.empty()) {V = q.front();q.pop();for (W = Graph->G[V].FirstEdge; W; W = W->Next) {if (!Visited[W->Adjx] ) {cout << W->Adjx << endl;;Visited[W->Adjx] = true;q.push(W->Adjx);}}}}
void DFS(LGraph Graph, Vertex V) {cout << V << endl;PtrToAdjVNode W;Visited[V] = true;for (W = Graph->G[V].FirstEdge; W; W = W->Next) {if (Visited[W->Adjx] == false){DFS(Graph,W->Adjx);}}
}
void ListComponents(LGraph G) {for (int V = 0; V< G->Nv; V++) {//for (V = G->G[i].FirstEdge; V; V = V->Next)if (!Visited[V])DFS(G,V);}}
int main()
{//LGraph Graph = BuildGraph();LGraph Graph = CreateGraph(6);Graph->Ne = 8;Vertex a[8] = { 0,0,0,1,1,3,2,3 };Vertex b[8] = { 1,2,4,3,4,4,5,5 };/* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */for (int i = 0; i < Graph->Ne; i++) {Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */E->V1 = a[i]; E->V2 = b[i];/* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge(Graph, E);}for (int i = 0; i < MaxVertenNum; i++) { Visited[i] = false; }cout << "BFS:" << endl;BFS(Graph, 0);for (int i = 0; i < MaxVertenNum; i++) { Visited[i] = false; }cout << "_________________________" << endl;cout << "DFS:" << endl;DFS(Graph, 0);for (int i = 0; i < MaxVertenNum; i++) { Visited[i] = false; }cout << "_________________________" << endl;LGraph G = CreateGraph(8);G->Ne = 8;Vertex d[8] = { 0,0,0,1,1,5,6,5 };Vertex e[8] = { 1,2,4,3,4,6,7,7 };for (int i = 0; i < Graph->Ne; i++) {Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */E->V1 = d[i]; E->V2 = e[i];/* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge(G, E);}ListComponents(G);return 0;
}

邻接矩阵存储的图-遍历

#include<iostream>
#include<queue>
using namespace std;
#define INFINITY 65535;/*表示无穷大*/
typedef int Vertex;/*用顶点下标表示顶点*/
typedef int WeightType;/*边的权值设为整形*/
typedef char DataType;/*ing的存储的数据类型设为字符型*/
#define MaxVertexNum 1000
bool Visited[MaxVertexNum] = { false };
/*边的定义*/
typedef struct ENode* PtrToENode;
struct ENode
{Vertex V1, V2;WeightType Weight;//权重
};
typedef PtrToENode Edge;
/*图节点的定义*/
typedef struct GNode* PtrToGNode;
struct GNode
{int Nv;//顶点个数int Ne;//边数WeightType G[MaxVertexNum][MaxVertexNum];//邻接矩阵
};
typedef PtrToGNode MGraph;/*以邻接矩阵存储图*/
MGraph CreateCraph(int VertexNum) {/*初始化一个有VN个顶点但没有边的图*/Vertex V, W;MGraph G = new GNode();G->Nv = VertexNum;G->Ne = 0;for (V = 0; V < G->Nv; V++)for (W = 0; W < G->Nv; W++)G->G[V][W] = INFINITY;return G;
}
void InsertEdge(MGraph Graph, Edge E) {Graph->G[E->V1][E->V2] = 1;/*若是无向图还行要插入<V2,V1>*/Graph->G[E->V2][E->V1] = 1;
}
MGraph BuildGraph() {MGraph Graph;Edge E;Vertex V;int Nv;cin >> Nv;Graph = CreateCraph(Nv + 1);cin >> Graph->Ne;if (Graph->Ne != 0) {E = new ENode();for (int i = 0; i < Graph->Ne; i++) {cin >> E->V1 >> E->V2;InsertEdge(Graph, E);}}return Graph;
}
void DFS(MGraph Graph, Vertex V) {Vertex W;cout << V << endl;Visited[V] = true;for (W = 0; W < Graph->Nv; W++)if ((!Visited[W]) && (Graph->G[V][W] == 1))DFS(Graph, W);
}
void BFS(MGraph Graph, Vertex S) {Vertex V, W;cout << S << endl;queue<Vertex>q;Visited[S] = true;q.push(S);while (!q.empty()) {V = q.front();q.pop();for(W=0;W<Graph->Nv;W++)if (!Visited[W] && Graph->G[V][W] == 1) {cout << W << endl;Visited[W] = true;q.push(W);}}
}
void ListComponents(MGraph G) {//for (int V = 0; V < G->Nv; V++) {for (int W = 0; W < G->Nv; W++) {if (!Visited[W] )//DFS(G,W);BFS(G, W);}//}
}
int main()
{MGraph Graph = CreateCraph(6);Graph->Ne = 8;Vertex a[8] = { 0,0,0,1,1,3,2,3 };Vertex b[8] = { 1,2,4,3,4,4,5,5 };/* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */for (int i = 0; i < Graph->Ne; i++) {Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */E->V1 = a[i]; E->V2 = b[i];/* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge(Graph, E);}for (int i = 0; i < MaxVertexNum; i++) { Visited[i] = false; }cout << "DFS" << endl;DFS(Graph, 0);cout << "________________" << endl;for (int i = 0; i < MaxVertexNum; i++) { Visited[i] = false; }cout << "BFS" << endl;BFS(Graph, 0);cout << "________________" << endl;for (int i = 0; i < MaxVertexNum; i++) { Visited[i] = false; }MGraph G = CreateCraph(8);G->Ne = 8;Vertex d[8] = { 0,0,0,1,1,5,6,5 };Vertex e[8] = { 1,2,4,3,4,6,7,7 };for (int i = 0; i < Graph->Ne; i++) {Edge E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */E->V1 = d[i]; E->V2 = e[i];/* 注意：如果权重不是整型，Weight的读入格式要改 */InsertEdge(G, E);}ListComponents(G);}