实验六  图的综合应用 邻接表

一、实验目的

1.掌握图的基本操作—遍历；

2.掌握图的应用。

二、实验内容

对给定的输入内容，完成实验任务。

输入顶点集：

​​​​​​​1 2 3 4 5 6 7 8

输入边的集合：

1  2
1  3
2  4
2  5
4  8
5  8
3  6
3  7
6  7

（1）创建一个图（可用邻接矩阵或邻接表的方式进行存储）；

（2）输入选项：0或1，0为DFS，1为BFS；

（3）分别输出DFS和BFS两种遍历序列。

---

头文件及宏定义：

#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef char ElemType;
typedef int Bool;
typedef struct EdgeNode//边表结点
{
    int vex;//存下标
    struct EdgeNode *next;
}EdgeNode;

typedef struct VNode
{
    ElemType data;
    EdgeNode *HeadEdgeNode;
}VNode,AdjList[MAXSIZE];

typedef struct
{
    AdjList adjList;
    int Vertexes,Edges;
}Graph;

typedef struct
{
    int *base;
    int front;
    int rear;
}cycleQueue;

Bool visited[MAXSIZE];

子函数声明：

void CreateGraph(Graph *);//创建邻接表
void PrintGraph(Graph);//输出邻接表
void DFSTravels(Graph);//深度优先遍历 （递归）
void DFS(Graph,int);//深度优先遍历过程
void InitQueue(cycleQueue *);//初始化队列
void InsertQueue(cycleQueue *,int);//邻接表结点中序号入队
void DeleteQueue(cycleQueue *,int *);//邻接表结点中序号出队
Status QueueEmpty(cycleQueue);//队列判空 空返回TRUE 非空返回FALSE
void BFSTravels(Graph);//广度优先遍历（队列循环操作）

子函数主体：

void CreateGraph(Graph *G)
{
    int i,j,k;
    EdgeNode *temp;
    printf("请输入顶点个数及边个数：n");
    scanf("%d %d",&G->Vertexes,&G->Edges);

    printf("请输入顶点：n");
    for(k=0;kVertexes;k++)
    {
        getchar();
        scanf("%c",&G->adjList[k].data);
        G->adjList[k].HeadEdgeNode=NULL;//初始化各顶点首元结点指针
    }

    printf("请输入边Vi Vj：n");
    for (k=0;kEdges;k++)
    {
        scanf("%d %d",&i,&j);
        temp=(EdgeNode *) malloc(sizeof (EdgeNode));
        temp->vex=j;
        temp->next=G->adjList[i-1].HeadEdgeNode;
        G->adjList[i-1].HeadEdgeNode=temp;
    }
}

void PrintGraph(Graph G)
{
	printf("n您生成的邻接表为:nn");
    int i;
    EdgeNode *e;
    for(i=0;i",G.adjList[i].data);
            while (e)
            {
                printf("%c->",G.adjList[e->vex-1].data);
                e=e->next;
            }
            printf("NULLn");
        }
    }
}

void DFSTravels(Graph G)
{
    printf("n深度优先遍历结果：n");
    int i;
    for(i=0;ivex-1]==FALSE)
        {
            DFS(G,temp->vex-1);
        }
        temp=temp->next;
    }

}

void InitQueue(cycleQueue *q)
{
    q->base=(int *)malloc(MAXSIZE*sizeof(int));
    if(!q->base)
    {
        printf("内存分配失败！n");
        exit(0);
    }
    q->front=q->rear=0;
}

void InsertQueue(cycleQueue *q,int e)
{
    //队列不可能满！
    q->base[q->rear]=e;
    q->rear=(q->rear+1)%MAXSIZE;
}

void DeleteQueue(cycleQueue *q,int *e)
{
    *e=q->base[q->front];
    q->front=(q->front+1)%MAXSIZE;
}

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

void BFSTravels(Graph G)
{
    printf("n广度优先遍历结果：n");
    int i;
    EdgeNode *temp;
    cycleQueue Q;
    InitQueue(&Q);

    for(i=0;ivex-1]==FALSE)
                    {
                        printf("%c ",G.adjList[temp->vex-1].data);
                        visited[temp->vex-1]=TRUE;
                        InsertQueue(&Q,temp->vex-1);
                    }
                    temp=temp->next;
                }
            }
        }
    }
    putchar('n');
}

主函数：

int main(void ) 
{
    int choice;
    Graph *G = (Graph *) malloc(sizeof(Graph));
    printf("|———————★———————|n");
    printf("|      ☆☆☆欢迎使用☆☆☆    |n");
    printf("|   该程序以邻接表创建有向图   |n");
    printf("|     现在来创建一张有向图     |n");
    printf("|  Powered by CaptainUniverse_ |n");
    printf("|———————————————|n");
    CreateGraph(G);
    PrintGraph(*G);

    while (1) 
	{
        putchar('n');
        printf("|———————★———————|n");
        printf("|      ☆☆☆继续操作☆☆☆    |n");
        printf("|------0.深度优先遍历该图------|n");
        printf("|------1.广度优先遍历该图------|n");
        printf("|------2.退出------------------|n");
        printf("|            请选择            |n");
        printf("|  Powered by CaptainUniverse_ |n");
        printf("|———————————————|n");
        scanf("%d", &choice);
        if (!choice) 
		{
            DFSTravels(*G);
        } 
        else if (choice == 1) 
		{
            BFSTravels(*G);
        } 
        else if (choice == 2) 
		{
            printf("n听我说谢谢你，因为有你，温暖了四季！n");
            printf("n感谢您的使用！n");
            return 0;
        }
    }
}