链式向前星 + dfs遍历

利用普通链表构建的邻接表

核心代码

bool visted[MaxV];

void dfs(AdjGraph* G, int v) { // v 为起点 
	ArcNode* p;
	visted[v] = true;	// 标记为已遍历
	cout << v << " -> ";
	p = G->adjlist[v].firstarc;
	while (p != NULL) {
		if (!visted[p->adjvex]) {
			dfs(G, p->adjvex);
		} 
		p = p->nextarc;
	} 
}

完整代码

#include <iostream>
#define MaxV 100010 
#define INF INT_MAX

using namespace std;

typedef string infoType; 	 // 存储信息的类型

typedef struct ANode {		 // 边节点 
	int adjvex;				// 该边的邻接点编号
	struct ANode* nextarc;	 // 指向下一条边的指针
	int weight;				// 该边的权重 
} ArcNode;					// 边节点的类型 

typedef struct {			// 头节点 
	infoType info;			// 顶点的其他信息 
	ArcNode* firstarc;		// 指向第一个边的指针 
} VNode; 				   // 邻接表头节点类型 

typedef struct {
	VNode adjlist[MaxV];    // 邻接表头结点数组
	int n, e;			   // 图中的顶点数n, 边数e 
} AdjGraph;				   // 完整的图邻接表类型 

bool visted[MaxV];

// 图的创建
void CreateAdj(AdjGraph*& G,int A[MaxV][MaxV], int n, int e) {
	ArcNode *p;
	G = (AdjGraph*)malloc(sizeof(AdjGraph));
	for (int i = 0; i < n; ++i)
		G->adjlist[i].firstarc = NULL;
	for (int i = 0; i < n; ++i) {
		for (int j = n-1; j >= 0; --j) {
			if (A[i][j] != 0 && A[i][j] != INF) {	// 存在一条边 
				// 申请内存 
				p = (ArcNode*)malloc(sizeof(ArcNode));
				// 存储信息 
				p->adjvex = j;
				p->weight = A[i][j];
				// 头插法插入节点 
				p->nextarc = G->adjlist[i].firstarc;
				G->adjlist[i].firstarc = p;
			}
		}
	}
	G->n = n;
	G->e = e; 
} 

// 图的遍历输出
void DispAdj(AdjGraph* G) {
	ArcNode* p;
	for (int i = 0; i < G->n; ++i) {
		p = G->adjlist[i].firstarc;
		cout << i << " :";
		// 遍历链表 
		while (p != NULL) {
			cout << p->adjvex << "[" << p->weight << "]->";
			p = p->nextarc; 
		} 
		cout << endl;
	}
} 

// 销毁图
void DestroyAdj(AdjGraph*& G) {
	ArcNode* pre, *p;
	for (int i = 0; i < G->n; ++i) {
		pre = G->adjlist[i].firstarc;
		if (pre != NULL) {
			p = pre->nextarc;
			while (p != NULL) {
				free(pre);
				pre = p;
				p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);
} 

// dfs遍历图
void dfs(AdjGraph* G, int v) { // v 为起点 
	ArcNode* p;
	visted[v] = true;	// 标记为已遍历
	cout << v << " -> ";
	p = G->adjlist[v].firstarc;
	while (p != NULL) {
		if (!visted[p->adjvex]) {
			dfs(G, p->adjvex);
		} 
		p = p->nextarc;
	} 
}

int main () {
	int A[][MaxV] = {
		{0,2,1},		// <0,1>[2]  <0,2>[1]
		{2,0,3},		// <1,0>[2]  <1,2>[3]
		{1,3,0}			// <2,0>[1]  <2,1>[3]
	};
	AdjGraph* G;
	CreateAdj(G, A, 3, 3);
	DispAdj(G);
	dfs(G, 1);
	DestroyAdj(G);
} 

利用链式向前星

核心代码

链式向前星的代码没有普通链表实现简单。可利用普通链表实现作参考：

bool visted[MaxV];

void dfs(AdjGraph* G, int v) { // v 为起点 
	ArcNode* p;
	visted[v] = true;	// 标记为已遍历
	cout << v << " -> ";
	p = G->adjlist[v].firstarc;
	while (p != NULL) {
		if (!visted[p->adjvex]) {
			dfs(G, p->adjvex);
		} 
		p = p->nextarc;
	} 
}

所以，得出链式向前星遍历代码为：

bool st[N];									// 对应上面 visted[MaxV]

void dfs(int i) {							// 竞赛里一般一个图,不需要参数 G ，i 表示遍历的节点的编号对应 v
	st[i] = true;							// 对应visted[v] = true
	cout << i << " -> ";					 // 对应 cout << v << " -> " 
	for (int j = h[i]; j != -1; j = ne[j]) {   // 遍历链表的每一个节点，和while循环类似
		if (!st[e[j]]) {					 // 如果下一个节点没有没访问过
			dfs(e[j]);						// 访问下一个节点
		}
	}
} 

整体代码

#include <iostream>

using namespace std;

const int N = 1000, M = N * 2;

int h[N], e[M], ne[M], idx;
bool st[N];

void init() {
	idx = 0;
	memset(h, -1, sizeof(h));
}

void add(int a, int b) { // 添加边 ： a -> b 
	// 就是对 h[a] 的链表添加一个节点，新节点值为 b 
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 遍历
void disp() {
	for (int i = 0; i < N; ++i) {
		if (h[i] != -1){
			cout << i << "：";						// 输出当前节点的编号 
			for(int j = h[i]; j != -1; j = ne[j])	// 遍历顶点指向的边 
				cout << e[j] << " idx:(" << j << ")-> ";	// 输出对应顶点的编号，和下标索引 
			cout << endl;
		}
	}
}

// dfs遍历图
void dfs(int i) {
	st[i] = true;
	cout << i << " -> ";
	for (int j = h[i]; j != -1; j = ne[j]) {
		if (!st[e[j]]) {
			dfs(e[j]);
		}
	}
} 

int main () {
	init();
	add(1,2);
	add(3,4);
	add(2,3);
	add(2,1);
	add(4,6);
	add(6,1);
	add(6,2);
	disp(); 
	dfs(2);
}