图的邻接矩阵

#include <stdio.h>
#include <stdlib.h>
#define N 20
#define TRUE 1
#define FALSE 0
//访问标志数组
int visited[N];

//采用数组定义的队列，用于广度搜索
typedef struct {
	int data[N];
	int front, rear;
} SqQueue;

//图的邻接矩阵表示
typedef struct {
	int vexnum, arcnum;
	char vexs[N];
	int arcs[N][N];
} MGraph;

void createGraph(MGraph *g);
void dfs(int i, MGraph *g);
void tdfs(MGraph *g, int v0);
void bfs(int k, MGraph *g);
void tbfs(MGraph *g, int v0);
void init_visit();

//读入数据，创建无向图的邻接矩阵
void createGraph(MGraph *g) {
	char s;
	int i = 0, v1, v2;
	g->arcnum = 0;
	g->vexnum = 0;
	s = getchar();
	while (s != '#') {
		g->vexs[i] = s;
		g->vexnum++;
		s = getchar();
		i++;
	}
	getchar();
	for (int a = 0; a < i; a++)
		for (int b = 0; b < i; b++)
			g->arcs[a][b] = 0;
	scanf("%d,%d", &v1, &v2);
	while (v1 != -1 && v2 != -1) {
		g->arcs[v1][v2] = 1;
		g->arcs[v2][v1] = 1;
		scanf("%d,%d", &v1, &v2);
		g->arcnum++;
	}
}

//深度优先搜索-从顶点i出发深度搜索
void dfs(int i, MGraph *g) {
	int j;
	printf("%c", g->vexs[i]);
	visited[i] = 1;
	for (j = 0; j < g->vexnum; j++) {
		if (g->arcs[i][j] == 1 && !visited[j])
			dfs(j, g);
	}
}

//深度优先搜索-全图搜索
void tdfs(MGraph *g, int v0) {
	int i;
	for (i = 0; i < g->vexnum; i++)
		if (visited[i] != TRUE)
			dfs(v0, g);


}

//广度优先搜索-从顶点k广度搜索
void bfs(int k, MGraph *g) {
	int i, j;
	SqQueue qlist, *q;
	q = &qlist;
	q->rear = 0;
	q->front = 0;
	printf("%c", g->vexs[k]);
	visited[k] = TRUE;
	q->data[q->rear] = k;
	q->rear = (q->rear + 1) % N;
	while (q->rear != q->front) {
		i = q->data[q->front];
		q->front = (q->front + 1) % N;
		for (j = 0; j < g->vexnum; j++)
			if ((g->arcs[i][j] == 1) && (!visited[j])) {
				printf("%c", g->vexs[j]);
				visited[j] = TRUE;
				q->data[q->rear] = j;
				q->rear = (q->rear + 1) % N;
			}
	}


}

//广度优先搜素-全图搜索
void tbfs(MGraph *g, int v0) {
	int i;
	for (i = 0; i < g->vexnum; i++)
		if (visited[i] != TRUE)
			bfs(v0, g);







}

//初始化访问标志数组
void init_visit() {
	int i;
	for (i = 0; i < N; i++)
		visited[i] = FALSE;
}

int main() {
	MGraph g;
	int i, j, v0;
	createGraph(&g);
	scanf("%d", &v0);
	printf("graph:\n");
	for (i = 0; i < g.vexnum; i++) {
		for (j = 0; j < g.vexnum; j++)
			printf("%d ", g.arcs[i][j]);
		printf("\n");
	}
	printf("dfs:");
	init_visit();
	tdfs(&g, v0);
	printf("bfs:");
	init_visit();
	tbfs(&g, v0);

	return 0;
}