数据结构与算法实验3——图的应用

一、实验目的

１．掌握图的存储策略及其存储实现。

２．掌握图的深度、广度优先遍历的算法策略及其程序实现。

３．掌握图的常见算法策略及其程序实现。

二、实验任务

１．键入或随机生成数据，建立一个有向图的邻接表。

２．输出该邻接表。

３．以有向图邻接表为基础上，计算各顶点的度并输出。

４．以有向图邻接表为基础，输出其拓扑排序序列。

5．采用邻接表存储，实现无向图的非递归 DFS 遍历。

6．采用邻接表存储，实现无向图的 BFS 优先遍历。

7．判断无向图任意两个顶点间是否有路径，若有则输出路径上的顶点序列。

8．在主函数中设计一个简单的菜单，调用上述算法。

三、源代码 源文件

/*
    源文件
*/
/*
实验名称：图的应用
实验目的：
	１．掌握图的存储策略及其存储实现。
	２．掌握图的深度、广度优先遍历的算法策略及其程序实现。
	３．掌握图的常见算法策略及其程序实现。
实验内容：
	１．键入或随机生成数据，建立一个有向图的邻接表。
	２．输出该邻接表。
	３．以有向图邻接表为基础上，计算各顶点的度并输出。
	４．以有向图邻接表为基础，输出其拓扑排序序列。
	5．采用邻接表存储，实现无向图的非递归 DFS 遍历。
	6．采用邻接表存储，实现无向图的 BFS 优先遍历。
	7．判断无向图任意两个顶点间是否有路径，若有则输出路径上的顶点序列。
	8．在主函数中设计一个简单的菜单，调用上述算法。
实验日期：2020/12/26
开发者：每天八杯水
*/
#include"graph.h"
int Out();
GraphList* InitGraph(int);
void ShowGraph(GraphList*，int);
int InDegree(GraphList*，int);
int OutDegree(GraphList* ，int);
int ShowDegree(GraphList* ，int);
int Topologicalsort(GraphList*);
void DFS(GraphList*, int*, int);
void DFSGraphList(GraphList*);
void BFS(GraphList*, int*, int);
void BFSGraphList(GraphList*);
void JudgePath(GraphList*，int, int);
void SF();//释放资源

int main()
{
    GraphList* graphList;//该指针代表创建的有向图
    cout << "\n";
    cout << "***您正在进行的操作是建立图的邻接表***" << endl;
    cout << "请输入顶点的个数：" ;
    int num;
    cin >> num;
    graphList= InitGraph(num);
    bool opt = true;  //是否循环的一个标志
    while (opt == true) {
        //菜单列表
        cout << "\n\t\t*********************************************\n";
        cout << "\t\t*      WELCOM TO MY WORLD                   *\n";
        cout << "\t\t*   1.    输出图的邻接表                    *\n";
        cout << "\t\t*   2.    计算有向图顶点的度                *\n";
        cout << "\t\t*   3.    输出有向图拓扑排序                *\n";
        cout << "\t\t*   4.    无向图DFS遍历                     *\n";
        cout << "\t\t*   5.    无向图BFS遍历                     *\n";
        cout << "\t\t*   6. 判断无向图两个顶点是否有路径并输出   *\n";
        cout << "\t\t*   7.      释放资源                        *\n";
        cout << "\t\t*   8.      退出程序                        *\n";
        cout << "\t\t*********************************************\n";
        //接收输入选择
        cout << "\t\t请选择：";
        int x;
        cin >> x;
        //判断用户的选择
        switch (x) {
        case 1:
            ShowGraph(graphList);//输出邻接表
            opt = Out();        //小目录选择1返回true到循环条件时再次执行主菜单；选择2返回false退出循环
            break;
        case 2:
        {
            cout << "请输入你要计算哪个顶点的度：";      
            int vex;      
            cin >> vex;
           // cout << OutDegree(graphList, vex);
           // cout << InDegree(graphList, vex);
            cout << "该顶点的出度为：" << OutDegree(graphList, vex)<> vex1 >> vex2;
            JudgePath(graphList, vex1, vex2);
            opt = Out();        //小目录
            break;
        case 7:
            SF(graphList);
            opt = Out();        //小目录
            break;

        case 8:
            cout << "\n\t\t你选择了7-退出程序\n";
            opt = false;        //把标志位为假，就退出了循环
            break;
        default:
            cout << "\n\t\t输入非法，请重新选择!\n";
            break;
        }
    }
    cout << "\n\t\t菜单已退出!\n";
}

头文件

/*
    头文件
*/
#pragma once
#include
#include
#include
using namespace std;

/*
    定义小目录-进入算法后如何退出的实现
*/
int Out() {
    cout << "\n";
    cout << "\t\t************\n";
    cout << "\t\t*1.返回菜单*\n";
    cout << "\t\t*2.退出程序*\n";//退出，程序结束
    cout << "\t\t************\n";
    cout << "\t\t选择：";
    char y;
    cin >> y;      //接受输入
    switch (y) {
    case '1':
        return true;
    case '2':
        return false;
    default:
        cout << "\t\t非法输入，已返回主目录!\n";//输入其他数字无效
        return true;
        break;
    }
}

/*
    结构体类型定义
*/
const int MAX_VERTEX_NUM = 8; // 顶点的最大个数
typedef struct GRAPHLISTNODE_STRU//结点类型
{
	int nodeno;//结点的编号
	struct GRAPHLISTNODE_STRU* next;//指向下一个结点的指针
	//int weight; // 边的权
} GraphListNode; // 结点
typedef struct GRAPHLIST_STRU
{
    int size;//图的结点实际个数
    GraphListNode* graphListArray;//图所有顶点表，用二维数组表示
} GraphList;//顶点

/*
    创建有向图
*/
GraphList* InitGraph(int num)
{
    int i;
    GraphList* graphList = (GraphList*)malloc(sizeof(GraphList));//申请GraphList结构体类型
    graphList->size = num;//用户定义顶点个数
    graphList->graphListArray = (GraphListNode*)malloc(sizeof(GraphListNode) * num);//申请GraphListNode结构体类型，分配有num个结点的连续空间来形成顶点表
    for (int i = 0; i < num; i++) //初始化顶点表
    {
        graphList->graphListArray[i].nodeno = i;//顶点表赋予初值
        graphList->graphListArray[i].next = NULL;//顶点表的指针赋予空指针
    }
    int vex1, vex2;//数字编号代表不同的顶点
    GraphListNode* PNode = NULL;//新结点，代表与各个顶点相连的那个顶点
    cout << "请输入两个顶点编号，输入方式为顶点1 顶点2，以两次输入为-1结束" << endl;
    cin >> vex1 >> vex2;
    while (vex1>=0 && vex2>=0)
    {
        PNode = (GraphListNode*)malloc(sizeof(GraphListNode));//新结点
        PNode->nodeno = vex2;//给结点赋予编号，代表后继指向
        PNode->next = NULL;
        PNode->next = graphList->graphListArray[vex1].next;//链表头插法，
        graphList->graphListArray[vex1].next = PNode;//顶点表的指针指向新结点
        cin >> vex1 >> vex2;
    }
    return graphList;
}

/*
    输出邻接表：把顶点表打印出来即可
*/
void ShowGraph(GraphList* graphList)
{
    cout << "您创建的邻接表为："<size; i++)//大循环每一个顶点表
    {
        cout << graphList->graphListArray[i].nodeno ;//输出顶点表
        GraphListNode* p;//声明一个临时结点
        p = graphList->graphListArray[i].next;//p为每一个链接表的第一个结点
        for (int i = 0; i < MAX_VERTEX_NUM; i++)//小循环输出链接表的结点
        {
            if (p== NULL) break;//这里是判断链接表的第一个结点的         
            cout << "->" << p->nodeno ;//输出邻接表
            if (p->next== NULL) break;//边界条件：如果链接表为空就退出循环           
            p = p->next;
            //cout << "->" << p->nodeno << "->";//输出邻接表
           // cout << "->";
        }
        cout << endl;
    }
}

/*
    计算顶点的度
*/
int InDegree(GraphList* graphList ,int vex)//vex代表顶点，计算入度->判断哪些顶点是指向要找的顶点的,那么该顶点就是入度，若有就+1
{
    int count = 0;
    for (int i = 0; i < graphList->size; i++)//顶点循环
    {
        GraphListNode* p;
        p = graphList->graphListArray[i].next;//链接表的第一个结点
        for (int j = 0; j < MAX_VERTEX_NUM; j++)//链接表循环
        {
            if (i == vex)break;//如果j为要找的顶点就退出循环到下一个顶点
            if (p == NULL)break;
            if (p->nodeno == vex)//如果某个顶点链接表有要找的顶点那么就是要找的顶点的入度，+1
            {
                count++;
            }
            p = p->next;
        }
    }
    return count;

}
int OutDegree(GraphList* graphList, int vex)//vex代表顶点，计算出度->链接表的结点个数即为各个顶点的出度
{
    int count=0;//统计出度的个数
    GraphListNode* p;
    p = graphList->graphListArray[vex].next;//p为链接表的结点
    for (int i = 0; i < MAX_VERTEX_NUM; i++)
    {
        if(p==NULL) break;      //只要链接表下一个结点不为空就+1
        count++; 
        p = p->next;
    }
    return count;
}

int ShowDegree(GraphList* graphList,int vex)
{
    int count;
    count = InDegree(graphList, vex) + OutDegree(graphList, vex);
    return count;
}

/*
    拓扑排序算法
*/
int Topologicalsort(GraphList* graphList)
{
    int i;
    int count = 0;//表示已经输出的顶点个数
    int nodeNum;//表示要输出的顶点
    int success = 1;
    stacknodeStack;//用来存放要输出的顶点的栈
    GraphListNode* tempNode = NULL;
    int* inPoint = (int*)malloc(sizeof(int) * graphList->size);//一维数组用来存放每一个顶点的入度
    for (int i = 0; i < graphList->size; i++)
    {
        inPoint[i] = 0;//数组初始化为0    
    }
    for (int i = 0; i < graphList->size; i++)
    {
        tempNode = graphList->graphListArray[i].next;//链接表的第一个结点
        while (tempNode!=NULL)//计算顶点的入度，非常巧妙
        {
            inPoint[tempNode->nodeno]++;
            tempNode = tempNode->next;
        }
    }
    for (int i = 0; i < graphList->size; i++)
    {
        if (inPoint[i] == 0)//如果哪一个顶点入度为0就入栈
            nodeStack.push(i);
    }
    cout << "拓扑排序为：";
    while (!nodeStack.empty())
    {
        nodeNum = nodeStack.top();//取出入度为0的顶点并输出成为拓扑排序
        cout << nodeNum<<"  ";
        nodeStack.pop();//删除已经输出的顶点，接下来减少该顶点指向的顶点的入度
        count++;//每输出一个顶点+1
   
        tempNode = graphList->graphListArray[nodeNum].next;//回到输出顶点的链接表 *** 作与之相邻的顶点的入度
        while (tempNode!=NULL)
        {
            inPoint[tempNode->nodeno]--;
            if (inPoint[tempNode->nodeno] == 0)
                nodeStack.push(tempNode->nodeno);
            tempNode = tempNode->next;
        }
    }
    if (count != graphList->size) success = 0;
    return success;
}

/*
    DFS遍历图
*/
void DFS(GraphList* graphList, int* visited,int source)
{
    int j;
    GraphListNode* tempNode = NULL;
    visited[source] = 1;//1表示已经访问
    cout << source;
    tempNode = graphList->graphListArray[source].next;//输出上面的顶点后，开始访问与之相邻的其他顶点，也就是链接表里面的顶点
    while (tempNode!=NULL)
    {
        if (!visited[tempNode->nodeno])//若果与之相邻的顶点未被访问过，则访问并输出
            DFS(graphList, visited, tempNode->nodeno);
        tempNode = tempNode->next;
    }
}
void DFSGraphList(GraphList* graphList)
{
    int i;
    int* visited = (int*)malloc(sizeof(int) * graphList->size);//visited数组为0表示该顶点未被访问，为1表示已经访问
    for (i = 0; i < graphList->size; i++)
    {
        visited[i] = 0;
    }
    for (i = 0; i < graphList->size; i++)
    {
        if (!visited[i])
            DFS(graphList, visited, i);
    }
}

/*
    BFS遍历图
*/
void BFS(GraphList* graphList, int* visited, int source)
{
    int tempVex;
    GraphListNode* tempNode = NULL;
    queuewaitingQueue;//与二叉树层次遍历一样使用队列
    visited[source] = 1;//1代表以及访问
    cout << source;
    waitingQueue.push(source);//顶点入队，接下来要把这里入队的顶点的所有相邻的顶点入队
    while (!waitingQueue.empty())
    {
        tempVex = waitingQueue.front();
        waitingQueue.pop();
        tempNode = graphList->graphListArray[tempVex].next;//要输出的顶点为上一次输出的相邻结点
        while (tempNode!=NULL)//循环把一层链接表全部入队
        {
            if (!visited[tempNode->nodeno])//若未被访问，则访问-入队-输出
            {
                visited[tempNode->nodeno] = 1;
                waitingQueue.push(tempNode->nodeno);
                cout << tempNode->nodeno;
            }
            tempNode = tempNode->next;
        }
    }
}

void BFSGraphList(GraphList* graphList)
{
    int i;
    int* visited = (int*)malloc(sizeof(int) * graphList->size);//visited数组为0表示该顶点未被访问，为1表示已经访问
    for (i = 0; i < graphList->size; i++)
    {
        visited[i] = 0;
    }
    for (i = 0; i < graphList->size; i++)
    {
        if (!visited[i])
            BFS(graphList, visited, i);
    }
}

/*
    判断两个顶点是否有路径
    思想：随机输入两个顶点，以其中一个顶点用BFS遍历算法遍历，如果第二个顶点未被访问则说明不存在路径
*/
void JudgePath(GraphList* graphList,int vex1, int vex2)
{ 
    int* visited = (int*)malloc(sizeof(int) * graphList->size);//visited数组为0表示该顶点未被访问，为1表示已经访问
    for (int i = 0; i < graphList->size; i++)
    {
        visited[i] = 0;
    }
    cout << "从"<graphListArray[i].next;//p为链接表第一个结点
        for (int j = 0; j < 2; j ++ )
        { 
            q = p;
            if (p == NULL)break;
            p = p->next;           
            free(q);
            
        } 
    }
    free(graphList->graphListArray);
    free(graphList);
    cout << "释放资源成功" << endl;
}

四、运行结果