【数据结构】图的创建与遍历

仅供参考，请勿抄袭

#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20  //最大顶点个数

/*         ALGraph：
 *
 * AdjList[]
 *    ↓         ArcNode
 * ╔════╗         ↓
 * ║  A ║→▢→▢→▢→▢
 * ╠════╣
 * ║  B ║→▢→▢→▢
 * ╠════╣
 * ║ ...║
 * ╠════╣
 * ║  C ║→▢→▢→▢→▢→▢→▢
 * ╚════╝
 *   ↑
 *  VNode：AdjList[]的一个节点
 */

typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;
    int *info;
}ArcNode;//邻接表的一个节点

typedef struct VNode
{
    char data;
    ArcNode *firstarc=nullptr;//nullptr意为空指针，注意这里一定要设初值，否则默认初始化为0xcccccccccc，这个值不是空值，不等于NULL，遍历时就无法停止。
}VNode,AdjList[MAX_VERTEX_NUM];//邻接表数组的一个节点

typedef struct
{
    AdjList vertices;//数组
    int vexnum=0, arcnum=0;//节点数和边数
    int kind;//图的种类（好像暂时用不着）
}ALGraph;//用邻接表表示图

//====================下面是定义队列的代码，会的可以不看========================
typedef struct QNode
{
    int data;
    struct QNode *next;
}QNode,*QueuePtr;//邻接表节点

typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;//邻接表表头

void InitQueue(LinkQueue &Q)
{
    Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
    if(!Q.front)return;
    Q.front->next = NULL;
}//建立队列

void EnQueue(LinkQueue &Q,int e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if(!p)return;
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
}//入队

void DeQueue(LinkQueue &Q,int &e)
{
    if(Q.front==Q.rear)return;
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)Q.rear = Q.front;
    free(p);
}//出队

bool QueueEmpty(LinkQueue Q)
{
    return Q.front->next == nullptr;
}//检测队列是否为空

//===========================================

//temp1与temp2为邻接表节点（边）的两端节点
void BuildNode(ALGraph &G,int temp1,int temp2)
{
    ArcNode *node = (ArcNode*)malloc(sizeof(ArcNode));//申请一个ArcNode大小的连续内存
    node->adjvex = temp2;//把temp2的值赋给该节点的内容中
    node->nextarc = G.vertices[temp1].firstarc;//将该节点插入要替换的节点前
    G.vertices[temp1].firstarc = node;//将该节点挂载到数组上
    G.arcnum++;//边数加一
}//建立邻接表节点ArcNode

//建立图
void CreateGraph(ALGraph &G)
{
    //下面建立数组：
    printf("请输入节点信息：");
    for(int i=0;i<MAX_VERTEX_NUM;i++)
    {
        char temp=getchar();//不断地获得用户输入的值，每次一个字符，进入以下方法检验
        if (temp=='n')break;//如果用户按下回车，立刻停止输入
        else
        {
            if (temp != ' ')//如果这个值不是空格，将该值输入数组中，且标记增加一个节点
            {
                G.vertices[G.vexnum].data = temp;
                G.vexnum++;
            }
        }
    }
    //下面建立邻接表各个节点
    printf("请输入边数据：");
    for(;;)
    {
        int temp1, temp2;
        scanf("%d,%d", &temp1, &temp2);//不断地获得两个值（scanf可以忽略空格）
        BuildNode(G, temp1, temp2);//用这两个值建立节点
        if(temp1!=temp2)BuildNode(G, temp2, temp1);//如果这两个值不相等，则建立反向的节点（无向图）
        if (getchar() == '\n')break;//如果用户键入的是Enter，立刻停止输入
    }//存储边数据
}

//以下是遍历体，详见课本
bool visited[MAX_VERTEX_NUM];//用于记录节点是否被访问的数组

//深度优先遍历递归体
void DFS(ALGraph G,int v)
{
    ArcNode *p;
    printf("%c,", G.vertices[v].data);
    visited[v] = true;
    p = G.vertices[v].firstarc;
    while(p)
    {
        if (!visited[p->adjvex])DFS(G, p->adjvex);
        p = p->nextarc;
    }
}

//广度优先遍历递归体
void BFS(ALGraph G,int v)
{
    LinkQueue Q;
    InitQueue(Q);
    printf("%c,", G.vertices[v].data);
    visited[v] = true;
    EnQueue(Q, v);
    while (!QueueEmpty(Q))
    {
        int u;
        DeQueue(Q, u);
        ArcNode *p = G.vertices[u].firstarc;
        while (p)
        {
            if(!visited[p->adjvex])
            {
                printf("%c,", G.vertices[p->adjvex].data);
                visited[p->adjvex] = true;
                EnQueue(Q, p->adjvex);
                p = p->nextarc;
            }
            else break;
        }
    }
}

//深度优先遍历
void DFSTraverse(ALGraph G)
{
    for (int v = 0; v < G.vexnum; v++)visited[v] = false;//初始化数组
    for (int v = 0; v < G.vexnum; v++)
        if(!visited[v])DFS(G, v);
}

//广度优先遍历
void BFSTraverse(ALGraph G)
{
    for (int v = 0; v < G.vexnum; v++)visited[v] = false;
    for (int v = 0; v < G.vexnum; v++)
        if (!visited[v])BFS(G, v);
}

//画邻接矩阵
//邻接矩阵的横向边与纵向边都是节点数，其中交叉位置即这两个节点间的权值，
//在无权图中，用1表示这两点相邻接，用0表示这两点不邻接
void DrawGraph(ALGraph G)
{
    for(int i=0;i<G.vexnum;i++)//纵向边输出
    {
        for(int j=0;j<G.vexnum;j++)//横向边输出
        {
            if (!G.vertices[i].firstarc)printf("0 ");//某个节点的数组没有邻接节点，那么它就不与任何节点都邻接，也就是整行为0
            else
            {
                ArcNode *p=G.vertices[i].firstarc;//得到数组后的一个节点地址，依次检测有没有与这个数组代表的节点邻接的节点
                bool setone = false;//设置一个变量，保存这个节点与数组节点是否邻接
                while(p)//由于邻接表没有索引，只能通过遍历得到j代表的节点
                {
                    if (p->adjvex == j)//找到了j代表的节点，就说明这两个节点邻接，输出1
                    {
                        printf("1 ");
                        setone = true;
                    }
                    p = p->nextarc;
                }
                if(!setone)printf("0 ");//没找到j代表的节点，说明这两个节点（i和j）不邻接
            }
        }
        putchar('\n');//一行输出完毕，换行
    }
}

int main()
{
    ALGraph G;
    CreateGraph(G);
    printf("深度优先遍历：");
    DFSTraverse(G);
    printf("\n广度优先遍历：");
    BFSTraverse(G);
    printf("\n图的邻接矩阵为：\n");
    DrawGraph(G);
    return 0;
}