数据结构之图的常用存储结构，及其典型应用，递归算法

た入场券 2022-11-25 11:49 151阅读 0赞

## 数据结构之图的常用存储结构，及其典型应用，递归算法 ##

**一、实验目的**

1.  熟悉图的两种常用的存储结构，即邻接矩阵和邻接表，以及在这两种存储结构上的遍历图的方法，即深度优先遍历和广度优先遍历。
2.  进一步掌握递归算法的设计方法。
3.  了解图的典型应用的算法程序。

**二、实验内容：**

1.  建立图的邻接矩阵存储结构（数组表示），并将邻接矩阵输出。
2.  建立图的邻接表存储结构，并将邻接表输出。
3.  图的深度优先遍历。
4.  图的广度优先遍历。

**三、实验要求**

在本题下面提交源程序和实验运行结果截图。

**1. 建立图的邻接矩阵存储结构（数组表示），并将邻接矩阵输出。**

#include<stdio.h>
    #define max 100
    int creatcost(int cost[][max])
    {
           int vexnum,arcnum,i,j,k,v1,v2;
        printf("\ninput the vexnum,arcnum:");
        scanf("%d,%d",&vexnum,&arcnum);
        for(i=1;i<=vexnum;i++)
    for(j=1;j<=vexnum;j++)
        {
        
            cost[i][j]=0;
         } 
         for(k=0;k<arcnum;k++)
         {
          printf("v1,v2=");
            scanf("%d,%d",&v1,&v2);
            cost[v1][v2]=1;
         }
         return vexnum;
    }
    int main()
    {
        
        int i,j,vexnum;
        int cost[max][max];
        vexnum=creatcost(cost);
        printf("the Adjacency Matrix is:\n");
        for(i=1;i<=vexnum;i++)
        {
        
            for(j=1;j<=vexnum;j++)
            printf("%3d",cost[i][j]);
            printf("\n");
        }
        return 0;
    }

**四、实验结果。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]

1.  建立图的邻接表存储结构，并将邻接表输出。

#include<stdio.h>
    #include<malloc.h>
    #define max 100 
    typedef struct node
    {
        
        int adjvex;
        struct node*next;
    }arcnode;
    typedef struct 
    {
        
        int vertex;
        arcnode*firstarc;
    }vexnode;
    vexnode adjlist[max];
    int creatadjlist()
    {
        
        arcnode*ptr;
        int arcnum,vexnum,k,v1,v2;
        printf("input the vexnum,arcnum:");
        scanf("%d,%d",&vexnum,&arcnum);
        for(k=1;k<=vexnum;k++)
        adjlist[k].firstarc=0;
        for(k=0;k<arcnum;k++)
        {
        
            printf("v1,v2=");
            scanf("%d,%d",&v1,&v2);
            ptr=(arcnode*)malloc(sizeof(arcnode));
            ptr->adjvex=v2;
            ptr->next=adjlist[v1].firstarc;
            adjlist[v1].firstarc=ptr;   
            ptr=(arcnode*)malloc(sizeof(arcnode));
            ptr->adjvex=v1;
            ptr->next=adjlist[v2].firstarc;
            adjlist[v2].firstarc=ptr;         
         }
        return vexnum;   
    }
    int main()
    {
        
        int i,n;
        arcnode*p;
        n=creatadjlist();
        printf("the Adjacency List:\n");
        for(i=1;i<=n;i++)
        {
        
            printf("%d=>",i);
            p=adjlist[i].firstarc;
            while(p!=NULL)
            {
        
                printf("---->%d",p->adjvex);
                p=p->next;
            }
            putchar('\n');
        }
        return 0;
    }

四、实验结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]

1.  图的深度优先遍历。

#include <stdio.h>
    #include <stdlib.h>
    #define GRAPH_MAX_VERTEX_SIZE 100                    // 最大顶点数
    #define TRUE 1
    #define FALSE 0
    typedef char VertexType;                             // 顶点类型
    typedef int Boolean;
    Boolean visited[GRAPH_MAX_VERTEX_SIZE];              // 顶点访问标志数组
    // 边表结点结构定义
    typedef struct EdgeNode
    {
        
    int adjvex;                                                                   // 邻接点域，存储该顶点在顶点表中对应的下标
    struct EdgeNode *next;                                                          // 链表指针域，指向下一个邻接点
    }EdgeNode;
    // 顶点表结点结构定义
    typedef struct VertexNode
    {
        
    	VertexType data;                                 // 顶点域，存储顶点信息
    	EdgeNode *firstEdge;                             // 边表头指针
    }VertexNode;
    // 图结构定义
    typedef struct Graph
    {
        
    	VertexNode adjList[GRAPH_MAX_VERTEX_SIZE];
    	int numVertexs, numEdges;                        // 图中当前顶点数和边数
    }Graph;
    /**
     * 建立无向图的邻接表表示
     * @param graph：指向图结构的指针
     */
    void CreateGraph(Graph *graph)
    {
        
        int i, j, k;
        EdgeNode *e;
    
        printf("输入无向图的顶点数和边数，分别用空格分隔：");
        scanf("%d %d", &(graph->numVertexs), &(graph->numEdges));                 // 接收输入的顶点数和边数，并赋值
        // 读入顶点信息，建立顶点表
        for(i = 0; i < graph->numVertexs; i++)
        {
        
            printf("输入第%d个顶点信息：", i + 1);
            fflush(stdin);             // 清空键盘输入缓冲区
            scanf("%c", &(graph->adjList[i].data));
            graph->adjList[i].firstEdge = NULL;                                   // 将该顶点指向第一个边表结点的指针置为空
        }
        // 建立边表
        for(k = 0; k < graph->numEdges; k++)
        {
        
            printf("输入边(vi, vj)的两个顶点在顶点数组中的下标i、下标j，分别用空格分隔：");
            fflush(stdin);           // 清空键盘输入缓冲区
            scanf("%d %d", &i, &j);
            e = (EdgeNode *)malloc(sizeof(EdgeNode));  // 生成边表结点
            if(!e)
            {
        
                exit(1);
            }
            e->adjvex = j;     // 邻接序号为j
            e->next = graph->adjList[i].firstEdge;   // 将边表结点e的next指针指向当前顶点上firstEdge指针指向的边表结点
            graph->adjList[i].firstEdge = e;         // 将当前顶点的firstEdge指针指向边表结点e，头插法
            // 因为是无向图，所以需要将(vi, vj)表示的边反过来再执行一遍，设置下标为j的顶点的边表
            e = (EdgeNode *)malloc(sizeof(EdgeNode));
            if(!e)
            {
        
                exit(1);
            }
            e->adjvex = i;
            e->next = graph->adjList[j].firstEdge;
            graph->adjList[j].firstEdge = e;
        }
    }
    /**
     * 邻接表的深度优先遍历递归算法
     * @param graph：图结构
     * @param i：遍历到第i个顶点
     */
    void DFS(Graph graph, int i)
    {
        
        EdgeNode *e;
        visited[i] = TRUE;                    // 标志该顶点已经被访问过了
        printf("%c ", graph.adjList[i].data);
    
        e = graph.adjList[i].firstEdge;
        while(e)
        {
        
            if(!visited[e->adjvex])
            {
        
                DFS(graph, e->adjvex);    // 对访问的邻接顶点进行递归调用
            }
            e = e->next;
        }
    }
    /**
     * 邻接表的深度优先遍历操作
     * @param graph：图结构
     */
    void DFSTraverse(Graph graph)
    {
        
        int i;
        // 初始化顶点访问标志数组，所有顶点都还没有被访问过
        for(i = 0; i < graph.numVertexs; i++)
        {
        
            visited[i] = FALSE;
        }
        for(i = 0; i < graph.numVertexs; i++)
        {
        
            // 对未访问过的顶点调用DFS，若是连通图，只会执行一次
            if(!visited[i])
            {
        
                DFS(graph, i);
            }
        }
    }
    int main()
    {
        
        Graph graph;
        CreateGraph(&graph);
        DFSTraverse(graph);
        return 0;
    }

四、实验结果。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70]: /images/20221124/09d9dadbc39a470b84acbaa6368425aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 1]: /images/20221124/7678b32fee0e42ca86a34d866338d956.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2VzY0ZBSg_size_16_color_FFFFFF_t_70 2]: /images/20221124/1c0643c11bfa4f85922f91ac3a4cc806.png