数据结构C 图的深度优先遍历、广度优先遍历

数据结构C 图的深度优先遍历、广度优先遍历

数据结构C 图的深度优先遍历、广度优先遍历

注：本程序由Visual Studio 2015编写，与VC++6.0稍有区别，复制到VC++6.0注释掉“#include “stdafx.h””即可运行，复制到VS可直接运行。存在错误，尽请谅解 ，仅供参考。
// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
//

#include “stdafx.h”
#include
#include <stdio.h>
#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
using namespace std;
typedef int Status;

typedef int ElemType;
#define MAXQSIZE 80 //最大队列长度
typedef struct {
ElemType *base; // 存储空间基址
int front; //队头下标，若队列不空则标识队头元素
int rear; //队尾下标，若队列不空则标识队尾元素的下一个位置
}Queue;
Queue Q;

#define MAX_VERTEX_NUM 20
typedef char GElemType;
typedef struct ArcNode {
int adjvex; //邻接点域，存储该邻接点的下标
int weight; //边上的权值
struct ArcNode *nextarc; //指向下一个邻接点
}ArcNode; //边表结点。可为网增加权值域

typedef struct VNode {
GElemType data; //顶点信息
ArcNode *firstarc; //边表头指针
}VNode, AdjList[MAX_VERTEX_NUM]; //顶点表结点
typedef struct {
AdjList vertices; //顶点表
int vexnum, arcnum; //图的顶点数和弧(边)数
}Graph; //图的邻接表
Graph G;
int visited[MAX_VERTEX_NUM];
//队列

// 构造一个空队列Q
void InitQueue(Queue &Q) {
// 构造一个空队列Q
Q.base = new int[MAXQSIZE];
Q.front = Q.rear = 0;
}

// 插入元素e为Q的新的队尾元素
Status EnQueue(Queue &Q, ElemType e) {
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return ERROR; //队列满
Q.ar] = e;//(Q.base + Q.rear)=e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return OK;
}
Status DeQueue(Queue &Q, ElemType &e) {
if (Q.front == Q.rear) return ERROR;//队空
e = Q.base[Q.front];//e=(Q.base+Q.front);
Q.front = (Q.front + 1) % MAXQSIZE;
return OK;
}

Status QueueEmpty(Queue Q) {//是否为空队

ar == Q.front;

}

//图的基本操作的实现
//返回v的“第一个邻接点”，若该节点在G中没有邻接点，返回-1
int FirstAdjVex(Graph G, int v) {
if (v >= 0 && G.vexnum)
if (G.vertices[v].firstarc)
return G.vertices[v].firstarc->adjvex;
return -1;
}

//返回v的（相对于w的）“下一个邻接点”。若w是v的最后一个邻接点，则返回-1
int NextAdjVex(Graph G, int v, int w) {
ArcNode *p;
if (v>0 && G.vexnum&&w >= 0 && G.vexnum) {
p = G.vertices[v].firstarc;
while (p->adjvex)
if (p->adjvex == w)
return p->nextarc->adjvex;
else
p = p->nextarc;
}
return -1;
}

//创建图的邻接表存储结构
void GreatDG(Graph &G) {
int i, v1, v2;
ArcNode *p, *q;
cout << “输入图的顶点数和边数，以空格隔开：”;
//freopen(“”, “r”, stdin);//输入数据将从文件中读取
cin >> G.vexnum >> G.arcnum;//输入图的顶点数和边数
cout << endl;
for (i = 0; i <= G.vexnum - 1; i++) {//顶点编号从0开始
cout << “输入第” << i + 1 << “个顶点的值(字符)：”;
cin >> G.vertices[i].data;
G.vertices[i].firstarc = NULL;
}
cout << endl;
for (i = 0; i < G.vexnum; i++) {
cout << “顶点” << G.vertices[i].data << “的编号是” << i << endl << endl;
}
for (i = 0; i < G.arcnum; i++) {//边结点编号从0开始
cout << “输入第” << i + 1 << “条边的两个顶点的编号，以空格隔开：”;
cin >> v1 >> v2;
p = new ArcNode;
p->adjvex = v2;
p->nextarc = NULL;
//从链表尾插入
if (G.vertices[v1].firstarc == NULL)
G.vertices[v1].firstarc = p;
else
{
for (q = G.vertices[v1].firstarc; q->nextarc != NULL; q = q->nextarc);
q->nextarc = p;
}
//一下创建另一个边表结点。无向图的一条边要创建两个结点。
p = new ArcNode;
p->adjvex = v1;
p->nextarc = NULL;
//从表尾插入
if (G.vertices[v2].firstarc == NULL)
G.vertices[v2].firstarc = p;
else
{
for (q = G.vertices[v2].firstarc; q->nextarc != NULL; q = q->nextarc);
q->nextarc = p;
}
}
cout << endl;
//fclose(stdin);//关闭文件
}

//广度优先遍历
//void BFS(Graph G, int v) {
// Queue Q;
// InitQueue(Q);
// ElemType u, w;
// cout << " " << G.vertices[v].data;
// visited[v] = 1;
// EnQueue(Q, v);
// while (!QueueEmpty(Q)) {
// DeQueue(Q, u);
// for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, v, w)) {
// if (!visited[w]) {
// cout << " " << G.vertices[w].data;
// visited[w] = 1;
// EnQueue(Q, w);
// }
// }
// }
//
//
//}
//
//void BFSTraverse(Graph G) { //广度优先遍历
// int n = 0, v;
// for (v = 0; v<G.vexnum; v++) visited[v] = FALSE;
// for (v = 0; v<G.vexnum; ++v) {
// if (!visited[v]) {
// n++;
// cout << endl << “第” << n << “个连通分量遍历序列”;
// BFS(G, v);
// }
// if (n == 1)
// cout << “此图为连通图” << endl;
// else
// cout << endl << “此图有” << n << “个连通分量”;
// }
//}

void BFSTraverse(Graph G) {
Queue Q;
InitQueue(Q);
int v,w,u;
for (v = 0; v < G.vexnum; v++)
visited[v] = false;
for (v = 0; v < G.vexnum; v++)
cout << " " << G.vertices[v].data;
visited[v] = TRUE;
EnQueue(Q, v);
while (!QueueEmpty(Q))
{
DeQueue(Q, u);
for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) {
if (!visited[w]) {
cout << w;
visited[w] = true;
EnQueue(Q, w);
}
}
}
}
//输出邻接表
void DispAsj(Graph G) {
int i;
ArcNode *q;
for (int i = 0; i <= G.vexnum - 1; ++i) {
cout << " " << i << " " << G.vertices[i].data;
q = G.vertices[i].firstarc;
while (q)
{
cout << “->” << q->adjvex;
q = q->nextarc;
}
cout << endl;
}
}

void DFS(Graph G, int v) {
// 从顶点v出发，深度优先搜索连通图 G
ArcNode *p;
visited[v] = 1;
cout << " " << G.vertices[v].data;
for (p = G.vertices[v].firstarc, p->nextarc != NULL; p = p->nextarc;) {
if (!visited[p->adjvex])
DFS(G, p->adjvex);
}
}
//对每个连通分量分别进行DFS。
void DFSTraverse(Graph G) { //深度优先遍历
int n=0;
int i;
for (i = 0; i< G.vexnum; i++)
visited[i] = 0;
for (i = 0; i <= G.vexnum-1; i++)
if (!visited[i])
{
n++;
cout << “第” << n << “个连通分量的遍历序列：”;
DFS(G, i);
cout << endl;
}
if (n == 1)
cout << “此图是连通图” << endl;
else
cout << endl << “此图有” << n << “个连通分量” << endl;
}

int main() {
cout << “tttt*ttttt*”;
cout << endl << “tttt*t计科1512-02210151232-杨少通t*” << endl;
cout << “tttt*****************************************” << endl << endl;
InitQueue(Q);
GreatDG(G);
cout << “该图的邻接表如下：” << endl;
DispAsj(G);
cout << endl << “广度优先遍历：”;
BFSTraverse(G);
cout << endl << “深度优先遍历：”<<endl;
DFSTraverse(G);
cout << endl;
return 0;
}

如有转载请注明来源： www.dreamload/blog/?p=367&preview=true （洋葱先生）