1145141919810

// 包含输入输出流库

#include

// 定义最大值为110

#define MAX 110

// 使用命名空间std

using namespace std;


// 定义图的结构体

typedef struct {

// 顶点表、列[0]存放顶点、[1]是广度遍历标志位、[2]是深度遍历标志位

int vex[MAX] = {0};

// 邻接矩阵、边表

int edge[MAX][MAX] = {0};

// 顶点数和边数/弧数

int vexnum = 0, arcnam = 0;

} Graph;


// 创建图的函数

void GreateGraph(Graph &G) {

// 定义变量

int x, n, m, vex1, vex2;

// 输入顶点数和边数/弧数

cin >> n >> m;

// 将顶点数和边数/弧数赋值给图的结构体

G.vexnum = n;

G.arcnam = m;

// 循环输入边的起点和终点

for (int i = 1; i <= m; i++) {

cin >> vex1 >> vex2;

// 将边的起点和终点存入顶点表

G.vex[i] = i;

// 在邻接矩阵中标记边的存在

G.edge[vex1][vex2] = 1;

}

}


// 打印顶点表的函数

void PrintVex(Graph G) {

cout << “顶点数组：” << endl;

// 循环打印顶点表

for (int i = 1; i <= G.vexnum ; i++) {

cout << i << " " << G.vex[i] << endl;

}

}


// 打印邻接矩阵的函数

void PrintArc(Graph G) {

cout << “弧边数组：” << endl;

cout << " ";

// 打印列标号

for (int i = 1; i <= G.vexnum; i++) {

cout << i << “_”;

}

cout << endl;

// 打印邻接矩阵

for (int i = 1; i <= G.vexnum ; i++) {

cout << i << "| ";

for (int j = 1; j <= G.vexnum; j++)

cout << G.edge[i][j] << " ";

cout << endl;

}

cout << endl;

}


// 队列的结构体

typedef struct LinkNode {

int data;

LinkNode *next;

} LNode;


typedef struct {

LinkNode *front, *rear;

} Queue;


// 初始化队列的函数

void InitQueue(Queue &Q) {

Q.front = Q.rear = new LNode ;

Q.front->next = NULL;

}


// 入队的函数

void EnQueue(Queue &Q, int x) {

LNode *s = new LNode;

s->data = x;

s->next = NULL;

Q.rear->next = s;

Q.rear = s;

}


// 出队的函数

bool DeQueue(Queue &Q, int &x) {

if (Q.front == Q.rear)

return false;

LNode *p = Q.front->next;

x = p->data;

Q.front->next = p->next;

if (Q.rear == p)

Q.rear = Q.front;

free(p);

return true;

}


// 判断队列是否为空的函数

bool IsEmpty(Queue Q) {

if (Q.front == Q.rear) {

return true;

} else {

return false;

}

}


// 打印队列的函数

void PrintQueue(Queue Q) {

if (Q.front == Q.rear)

cout << “空” << endl;

LNode *p = Q.front->next;

int x ;

while (p != NULL) {

x = p->data;

cout << x << " ";

p = p->next;

}

cout << endl;

}


// 深度优先遍历的函数

void DFSPrint(Graph G, int *visited1, int v) {

int w;

// 打印当前顶点

cout << v << " ";

// 将当前顶点标记为已访问

visited1[v] = 1;

// 遍历当前顶点的邻接点

for ( int i = 1; i <= G.vexnum ; i++) {

if (G.edge[v][i] == 1) {

w = i;

// 如果邻接点未被访问，则递归调用深度优先遍历函数

if (visited1[w] == 0) {

DFSPrint(G, visited1, w);

}

}

}

}


// 广度优先遍历的函数

void BFSPrint(Graph G, Queue &Q, int *visited2, int v) {

for (int i = 1; i <= G.vexnum; i++) {

if (G.edge[v][i] == 1 && visited2[i] == 0) {

// 打印当前顶点

cout << v << " ";

// 将当前顶点标记为已访问

visited2[v] = 1;

// 入队

EnQueue(Q, v);

break;

}

}

while (!IsEmpty(Q)) {

// 出队

DeQueue(Q, v);

for (int i = 1; i <= G.vexnum; i++) {

if (G.edge[v][i] == 1 && visited2[i] == 0) {

// 打印当前顶点

cout << i << " ";

// 将当前顶点标记为已访问

visited2[i] = 1;

// 入队

EnQueue(Q, i);

}

}

}

}


// 主函数

int main() {

Graph G;

// 创建图

GreateGraph (G);

// 打印顶点表

PrintVex(G);

// 打印邻接矩阵

PrintArc(G);

Queue Q;

// 初始化队列

InitQueue(Q);


// 定义并初始化深度优先遍历的标记数组
int visited1[G.vexnum + 5] = {0};
// 深度优先遍历
DFSPrint(G, visited1, 1);
cout << endl;

// 定义并初始化广度优先遍历的标记数组
int visited2[G.vexnum + 5] = {0};
// 广度优先遍历
BFSPrint(G, Q, visited2, 1);

return 0;

}