图的遍历(DFS)
程序员文章站
2022-03-03 11:34:30
...
邻接矩阵储存的图
#include <iostream> //DFS访问无向图(邻接矩阵)
#include <algorithm>
#include <cstdlib>
using namespace std;
const int MaxV = 100;
typedef struct GNode{
int Nv, Ne;
int F[MaxV][MaxV]; //只要求访问, 边权重为0 1
char Data[MaxV]; //顶点数据
bool tag[MaxV]; //标记结点是否被访问
} * MGraph;
typedef struct ENode{
int v1, v2;
} * Edge;
MGraph CreateGraph(int Nv)
{
MGraph G = (MGraph)calloc(1, sizeof(GNode));
G->Nv = Nv;
return G;
}
void InsertEdge(MGraph G, Edge E)
{
G->F[E->v1][E->v2] = 1;
G->F[E->v2][E->v1] = 1;
}
MGraph BuildGraph()
{
int Nv;
cin >> Nv;
MGraph G = CreateGraph(Nv);
Edge E = (Edge)malloc(sizeof(ENode));
cin >> G->Ne;
for (int i = 0; i < G->Ne; i++)
{
cin >> E->v1 >> E->v2;
InsertEdge(G, E);
}
free(E);
return G;
}
void Visit(MGraph G, int v) //访问顶点v的操作
{
cout << "正在访问结点:" << v << endl; //如果有需要, 对G->Data[v]访问
}
void DFS(MGraph G, int v) //访问起点编号为v
{
G->tag[v] = true;
Visit(G, v); //访问顶点v
for (int i = 0; i < G->Nv; i++)
if (G->tag[i] == false && G->F[v][i] == 1) //没访问过并且有路访问
DFS(G, i);
}
int main()
{
MGraph G = BuildGraph();
DFS(G, 0);
free(G);
system("pause");
return 0;
}
运行数据
8 10
4 7
0 2
2 6
0 7
1 7
0 5
3 5
3 4
4 5
4 6
运行结果(这里是无向图)
邻接表储存的图
#include <iostream> //DFS访问有向图(邻接表)
#include <algorithm>
#include <cstdlib>
using namespace std;
const int MaxV = 100;
typedef struct ENode{
int v1, v2;
//int Weight;
} * Edge;
struct AdjVNode{
int AdjV;
//int Weight;
AdjVNode *Next;
};
typedef struct VNode{
AdjVNode *EdgeFirst;
bool tag; //标记是否访问
//int Data; //不一定需要
} AdjList[MaxV];
typedef struct Graph{
int Nv, Ne;
AdjList L;
} * LGraph;
LGraph CreateGraph(int Nv)
{
LGraph G = (LGraph)calloc(1, sizeof(Graph));
G->Nv = Nv;
return G;
}
void InsertEdge(LGraph G, Edge E)
{
AdjVNode *A = (AdjVNode *)malloc(sizeof(AdjVNode));
A->AdjV = E->v2;
A->Next = G->L[E->v1].EdgeFirst;
G->L[E->v1].EdgeFirst = A;
/*若为无向图, 再在下面添加另一条边*/
}
LGraph BuildGraph()
{
int Nv;
cin >> Nv;
LGraph G = CreateGraph(Nv);
Edge E = (Edge)malloc(sizeof(ENode));
cin >> G->Ne;
for (int i = 0; i < G->Ne; i++)
{
cin >> E->v1 >> E->v2;
InsertEdge(G, E);
}
free(E);
return G;
}
void Visit(LGraph G, int v)
{
cout << "正在访问结点:" << v << endl; //如果有需要, 对G->L[v]访问
}
void DFS(LGraph G, int v)
{
G->L[v].tag = true;
Visit(G, v);
AdjVNode *A = G->L[v].EdgeFirst;
while (A)
{
if(G->L[A->AdjV].tag == false)
DFS(G, A->AdjV);
A = A->Next;
}
}
void DeleteGraph(LGraph G)
{
AdjVNode *A;
for (int i = 0; i < G->Nv; i++)
{
while (G->L[i].EdgeFirst)
{
A = G->L[i].EdgeFirst;
G->L[i].EdgeFirst = A->Next;
free(A);
}
}
free(G);
}
int main()
{
LGraph G = BuildGraph();
DFS(G, 0);
DeleteGraph(G);
system("pause");
return 0;
}
运行结果(这里是有向图, 有些顶点没有被访问)