图的邻接矩阵实现(深度优先遍历,广度优先遍历)

图可以由非常多的形式构成,但是一定有两个要素,就是顶点(Vertex)和变(Edge/Arc)

下面给出图的邻接矩阵实现的代码示例

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

typedef char VertexType;    //顶点的类型,由用户定义
typedef int EdgeType;     //边的权值类型,由用户定义

#define MAXVEX 9    //邻接矩阵的最大顶点数
#define MAXSIZE 9
//定义图:顶点集合+边集合
typedef struct {
    VertexType vexs[MAXVEX];    //顶点表
    EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵,相当于边表
    int numVertexes;
    int numEdges;
}MGraph;

/********定义一个队列************/
typedef struct {
    int data[MAXSIZE];
    int front;
    int rear;
}Queue;

Status InitQueue(Queue* Q) {
    Q->front = 0;
    Q->rear = 0;
    return OK;
}

Status QueueEmpty(Queue Q) {
    if (Q.front == Q.rear) {
        return TRUE;
    } else {
        return FALSE;
    }
}

Status EnQueue(Queue *Q,int e) {
    if ((Q->rear + 1)%MAXSIZE == Q->rear) {
        printf("EnQueue fail:full!
");
        return FALSE;
    }
    Q->data[Q->rear] = e;
    Q->rear++;
    return OK;
}

Status DeQueue(Queue *Q,int *e) {
    if (Q->front == Q->rear) {
        printf("DeQueue fail:empty!
");
        return FALSE;
    }
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return OK;
}

void CreateMGraph(MGraph* G)
{
	int i, j;

	G->numEdges = 15;
	G->numVertexes = 9;

	/* 读入顶点信息，建立顶点表 */
	G->vexs[0] = A;
	G->vexs[1] = B;
	G->vexs[2] = C;
	G->vexs[3] = D;
	G->vexs[4] = E;
	G->vexs[5] = F;
	G->vexs[6] = G;
	G->vexs[7] = H;
	G->vexs[8] = I;


	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for (j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j] = 0;
		}
	}

	G->arc[0][1] = 1;
	G->arc[0][5] = 1;

	G->arc[1][2] = 1;
	G->arc[1][8] = 1;
	G->arc[1][6] = 1;

	G->arc[2][3] = 1;
	G->arc[2][8] = 1;

	G->arc[3][4] = 1;
	G->arc[3][7] = 1;
	G->arc[3][6] = 1;
	G->arc[3][8] = 1;

	G->arc[4][5] = 1;
	G->arc[4][7] = 1;

	G->arc[5][6] = 1;

	G->arc[6][7] = 1;


	for (i = 0; i < G->numVertexes; i++)
	{
		for (j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] = G->arc[i][j];
		}
	}

}

bool visited[MAXVEX];	//顶点的访问标志数组

//邻接矩阵的深度优先递归算法
void DFS(MGraph G, int i) {
	visited[i] = TRUE;
	printf("%c
",G.vexs[i]);
	for (int j = 0; j < G.numVertexes; j++){
		if (G.arc[i][i] == 1 && !visited[j]) {
			DFS(G,j);
		}
	}
}

//邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G) {
	for (int i = 0; i < MAXVEX; i++) {
		visited[i] = FALSE;
	}
	for (int j = 0; j < G.numVertexes; j++) {
		if (!visited[j]) {
			DFS(G, j);
		}
	}
}

//邻接矩阵的广度遍历算法
void BFSTraverse(MGraph G) {
	int i, j;
	for (i = 0; i < MAXVEX; i++) {
		visited[i] = FALSE;
	}
	Queue Q;
	InitQueue(&Q);
	for (i = 0; i < G.numVertexes; i++) {
		if (!visited[i]) {
			int temp;
			//未被处理
			visited[i] = TRUE;
			printf("%c
", G.vexs[i]);
			temp = i;
			EnQueue(&Q,temp);
			while (!QueueEmpty(Q)) {
				DeQueue(&Q, &temp);
				for (j = 0; j < G.numVertexes; j++){
					//判断其它顶点若与当前顶点存在边且未访问过
					if (G.arc[temp][j] == 1 && !visited[j]) {
						visited[j] = TRUE;
						printf("%c
", G.vexs[j]);
						EnQueue(&Q, j);
					}
				}
			}
		}
	}
}

/********队列定义结束************/
int main()
{
	MGraph G;
	CreateMGraph(&G);
	printf("
深度遍历：");
	DFSTraverse(G);
	printf("
广度遍历：");
	BFSTraverse(G);
    return 0;
}