【课程设计】图的创建和遍历

图
字数统计: 1.3k阅读时长: 7 min
 2021/08/13 
问题描述

本课程设计主要完成邻接矩阵和邻接表两种不同存储方式的图的建立和遍历，其中遍历部分分别进行了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