欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的遍历(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

运行结果(这里是无向图)
图的遍历(DFS)
邻接表储存的图

#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;
}

运行结果(这里是有向图, 有些顶点没有被访问)
图的遍历(DFS)