本课程设计主要完成邻接矩阵和邻接表两种不同存储方式的图的建立和遍历，其中遍历部分分别进行了DFS和BFS两种不同形式的遍历。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stack>
#include<queue>
using namespace std;
/********************************图的存储结构定义***********************/
#define MaxVerNum 30
#define Vextype char
#define EdgeInfoType int
#define INF 999 //无穷大
#define MAXSIZE 100
typedef struct
{
Vextype vexs[MaxVerNum];
EdgeInfoType edges[MaxVerNum][MaxVerNum];
int n, e;
}MGragh;
typedef struct node
{
int adjvex;
EdgeInfoType Info;
struct node * next;
}EdgeNode;
typedef struct vnode
{
Vextype vertex;
EdgeNode *firstedge;
}VertexNode;
typedef struct
{
VertexNode adjlist[MaxVerNum];
int n, e;
}ALGraph;
int visited[MaxVerNum]; //顶点访问标记
/*建立图G的邻接矩阵 */
int returnId(MGragh *g, char c){
//返回c在数组中的下标
for (int i = 0; i<MaxVerNum; ++i)
{
if (g->vexs[i] == c) return i;
}
return -1;
}
void CreateGraph(MGragh *g)
{
scanf("%d %d\n", &(g->n), &(g->e));
char c;
int i = 0;
while (1)
{
while ((c = getchar()) == ' ');
if (c == '\n') break;
g->vexs[i++] = c;
}
Vextype s, e;
EdgeInfoType cost;
for (i = 0; i<g->n; i++)
{
for (int j = 0; j<g->n; j++)
{
g->edges[i][j] = 0;
}
}
for (int i = 0; i<g->e; ++i)
{
scanf("%c %c %d\n", &s, &e, &cost);
g->edges[returnId(g, s)][returnId(g, e)] = cost;
}
}
/* 根据图的邻接矩阵建立图的邻接表 */
void CreateALGraph(MGragh *mg, ALGraph *alg)
{
alg->n = mg->n; alg->e = mg->e;
for (int i = 0; i<alg->n; ++i)
{
alg->adjlist[i].vertex = mg->vexs[i];
}
int i, j;
EdgeNode *s;
for (int i = 0; i < alg->n; ++i)
{
for (int j = 0; j < alg->n; ++j)
{
if (mg->edges[i][j] != 0)
{
s = (EdgeNode*)malloc(sizeof(EdgeNode));
s->adjvex = j;
s->Info = mg->edges[i][j];
s->next = NULL;
EdgeNode*p = alg->adjlist[i].firstedge;
s->next = p;
alg->adjlist[i].firstedge = s;
}
}
}
}
//打印图(邻接矩阵)
void printGragh(MGragh *g)
{
printf("\n图G的邻接矩阵\n");
printf("顶点：\n");
for (int i = 0; i<g->n; i++)
{
printf("%c\t", g->vexs[i]);
}
printf("\n邻接矩阵：\n");
for (int i = 0; i<g->n; i++)
{
for (int j = 0; j<g->n; j++)
{
printf("%d\t", g->edges[i][j]);
}
printf("\n");
}
}
//打印图(邻接表)
void printALGragh(ALGraph *g)
{
printf("\n图G的邻接表\n");
for (int i = 0; i<g->n; i++)
{
printf("%c:", g->adjlist[i].vertex);
EdgeNode* edge = g->adjlist[i].firstedge;
while (edge)
{
printf("-->");
printf("%d:%d\t", edge->adjvex, edge->Info);
edge = edge->next;
}
printf("%\n");
}
}
/**********************DFS*********************/
//从顶点v开始图(邻接矩阵)的深度遍历
void DFS_MG(MGragh *g, int v)
{
int j;
visited[v] = 1;
printf("%c ", g->vexs[v]);
for (j = 0; j<g->n; ++j)
{
if (g->edges[v][j] != 0 && !visited[j])
DFS_MG(g, j);
}
}
//图的(邻接矩阵)的深度遍历
void DFSTranverse_MG(MGragh *g)
{
int i;
for (i = 0; i<g->n; ++i){
visited[i] = 0; //初始化访问数组visited的元素值为false
}
for (i = 0; i<g->n; ++i){
if (!visited[i]){ //节点尚未访问
DFS_MG(g, i);
}
}
}
//从顶点v开始图(邻接表)的深度遍历
void DFS_ALG(ALGraph *g, int v)
{
visited[v] = 1;
printf("%c ", g->adjlist[v].vertex);
EdgeNode *p =g->adjlist[v].firstedge;
while (p){
if (!visited[p->adjvex]){
DFS_ALG(g, p->adjvex); //递归深度遍历
}
p = p->next;
}
}
//图(邻接表)的深度遍历
void DFSTranverse_ALG(ALGraph *g)
{
int i;
for (i = 0; i<g->n; ++i){
visited[i] = 0; //初始化访问数组visited的元素值为false
}
for (i = 0; i<g->n; ++i){
if (!visited[i]){ //节点尚未访问
DFS_ALG(g, i);
}
}
}
/**************************BFS****************************/
//从顶点v开始图(邻接矩阵)的广度遍历
void BFS_MG(MGragh *g, int v)
{
int j;
queue<int> Q;
visited[v] = 1;
printf("%c ", g->vexs[v]);
Q.push(v);
while (!Q.empty())
{
v = Q.front();
Q.pop();
for (j = 0; j<g->n; ++j)
{
if (!visited[j] && g->edges[v][j] !=0)// INFINITY)
{
visited[j] = 1;
printf("%c ", g->vexs[j]);
Q.push(j);
}
}
}
}
//图(邻接矩阵)的广度遍历
void BFSTranverse_MG(MGragh *g)
{
int i;
for (i = 0; i<g->n; ++i){
visited[i] = 0; //初始化访问数组visited的元素值为false
}
for (i = 0; i<g->n; ++i){
if (!visited[i]){ //节点尚未访问
BFS_MG(g, i);
}
}
}
//从顶点v开始图(邻接表)的广度遍历
void BFS_ALG(ALGraph *g, int v)
{
queue<int > Q;
visited[v] = 1;
printf("%c ", g->adjlist[v].vertex);
Q.push(v);
while (!Q.empty()){
v = Q.front();
Q.pop();
EdgeNode *p = g->adjlist[v].firstedge;
while (p){
if (!visited[p->adjvex]){
visited[p->adjvex] = 1;
printf("%c ", g->adjlist[p->adjvex].vertex);
Q.push(p->adjvex);
}
p = p->next;
}
}
}
//图(邻接表)的广度遍历
void BFSTranverse_ALG(ALGraph *g)
{
int i;
for (i = 0; i<g->n; ++i){
visited[i] = 0; //初始化访问数组visited的元素值为false
}
for (i = 0; i<g->n; ++i){
if (!visited[i]){ //节点尚未访问
BFS_ALG(g, i);
}
}
}
/************************初始化与销毁********************************/
MGragh *init_MGraph()
{
MGragh *mg = (MGragh *)malloc(sizeof(MGragh));
if (mg)
{
mg->n = 0;
mg->e = 0;
}
return mg;
}
ALGraph *init_ALGraph()
{
ALGraph *alg = (ALGraph *)malloc(sizeof(ALGraph));
if (alg)
{
alg->n = 0;
alg->e = 0;
for (int i = 0; i<MaxVerNum; i++)
alg->adjlist[i].firstedge = NULL;
}
return alg;
}
void destroy_MGraph(MGragh **g)
{
if (*g)
{
free(*g);
*g = NULL;
}
}
void destroy_ALGraph(ALGraph **g)
{
for (int i = 0; i < (*g)->n; ++i)
{
EdgeNode *p = (*g)->adjlist[i].firstedge;
while (p)
{
EdgeNode *q = p->next;
free(p);
p = q;
}
}
if (*g)
{
free(*g);
*g = NULL;
}
}
/****main函数*************/
int main()
{
freopen("数据.txt", "r", stdin);
//创建图（邻接矩阵）
MGragh *mG = init_MGraph();
CreateGraph(mG);
printGragh(mG);
//创建图（邻接表）
ALGraph *alG = init_ALGraph();
CreateALGraph(mG, alG);
printALGragh(alG);
//DFS遍历
printf("\nDFS遍历:\n");
printf("邻接矩阵:\n");
DFSTranverse_MG(mG);
printf("\n邻接表:\n");
DFSTranverse_ALG(alG);
//BFS遍历
printf("\n\nBFS遍历:\n");
printf("邻接矩阵:\n");
BFSTranverse_MG(mG);
printf("\n邻接表:\n");
BFSTranverse_ALG(alG);
//销毁图
destroy_MGraph(&mG);
destroy_ALGraph(&alG);
}
//运行成功 2019年5月14日0:19:36
程序利用freopen("数据.txt", "r", stdin)将标准输入定位到“数据.txt”中，从该文件读取数据，文件格式如下：
图数据格式
运行结果如下：
运行结果
