链式向前星 + bfs遍历

复习队列

存储结构

int queue[MaxV]
int rear = -1, front = -1;

运算操作

• 队空的条件：front = rear
• 队满的条件：rear = MaxSize - 1（data数组的最大下标）
• 元素 e 入队：
  • rear++;
  • data[rear] = e;
• 出队操作：
  • front++;
  • 取出data数组中front位置的元素（一般不用管，要管时可以赋特别值）

所以一般使用：

while (front != rear) {  // 不队空
    if (rear < MaxSize - 1)	 //	判断是否队满，（一般竞赛中，空间提前开够，不需要判断这步）
    	qu[++rear] = e;		// 入队
    ......
    ElemType t = qu[++front]; // 出队并取得队首元素
    ......
}

普通链表实现

核心代码

int qu[MaxV]; 	// 队列 
bool visted[MaxV];	// 判断是否遍历过 

void bfs(AdjGraph* G, int v) {
	ArcNode* p;
	memset(qu, -1, sizeof(qu)); 
	int rear = -1, front = -1;
	// 当前节点入队 
	rear++;
	qu[rear] = v;
    // 当前节点访问过
	visted[v] = true;
	while (front != rear) {
		// 先将元素出队
		int i = qu[front+1];	 // 获取队首元素
		front++;				// 移除队首元素
		// 输出元素
		cout << i << " -> "; 
		p = G->adjlist[i].firstarc;
		while (p != NULL) {
			if (!visted[p->adjvex]) {
				// 入队，之后准备遍历
				rear++;
				qu[rear] = p->adjvex;
				visted[p->adjvex] = true; 
			}
			p = p->nextarc;
		} 
	}
	cout << endl;
} 

完整代码

#include <iostream>
#define MaxV 10010 
#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;					// 完整的图邻接表类型 

int qu[MaxV]; 	        	// 队列 
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);
} 

void bfs(AdjGraph* G, int v) {
	ArcNode* p;
	memset(qu, -1, sizeof(qu)); 
	int rear = -1, front = -1;
	// 当前节点入队 
	rear++;
	qu[rear] = v;
	visted[v] = true;
	while (front != rear) {
		// 先将元素出队
		int i = qu[front+1];
		front++;
		// 输出元素
		cout << i << " -> "; 
		p = G->adjlist[i].firstarc;
		while (p != NULL) {
			if (!visted[p->adjvex]) {
				// 入队，之后准备遍历
				rear++;
				qu[rear] = p->adjvex;
				visted[p->adjvex] = true; 
			}
			p = p->nextarc;
		} 
	}
	cout << endl;
} 

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);
	bfs(G, 1);
	DestroyAdj(G);
} 

链式向前星

核心代码

int qu[N], rear = -1, front = -1;	// 队列相关 

// bfs遍历
void bfs(int i) {
	// 入队
	qu[++rear] = i;
	st[i] = true;
	while (front != rear) {
		int t = qu[++front];
		cout << t << " -> ";
		for (int j = h[t]; j != -1; j = ne[j]) {
			if (!st[e[j]]) {
				qu[++rear] = e[j];
				st[e[j]] = true;
			}
		}
	}
} 

整体代码

#include <iostream>

using namespace std;

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

int h[N], e[M], ne[M], idx;			// 图 
bool st[N];						   // 判断是否遍历过 
int qu[N], rear = -1, front = -1;	 // 队列相关 

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

// 添加边 ： a -> b 
void add(int a, int 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]);
		}
	}
} 

// bfs遍历
void bfs(int i) {
	// 入队
	qu[++rear] = i;
	st[i] = true;
	while (front != rear) {
		int t = qu[++front];
		cout << t << " -> ";
		for (int j = h[t]; j != -1; j = ne[j]) {
			if (!st[e[j]]) {
				qu[++rear] = e[j];
				st[e[j]] = true;
			}
		}
	}
} 

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);
	memset(st, false, sizeof(st));
	cout << endl;
	bfs(2);
}