一、实验目的

1、掌握图的邻接矩阵和邻接表表示

2、掌握图的深度优先和广度优先搜索方法

3、理解图的应用方法

二、实验预习 

说明以下概念

1、深度优先搜索遍历：

       一种图的遍历方式：从图中任意一个起始顶点 V 出发，接着访问它的任意一个邻接顶点 W1 ；再从 W1 出发，访问与 W1 邻接的、但还未被访问过的顶点 W2 ；然后再从 W2 出发，进行相同的的访问……直至到达一个所有的邻接顶点都已经被访问过的顶点 U 。

       接着，从顶点 U 往前退回一步，回到前一次访问过的顶点，判断该顶点是否有其它没有被访问过的邻接顶点：

       如果有，则访问此邻接顶点，并再次从此顶点出发，进行与之前相同的访问；

       如果没有，则继续往前退回一步，再次进行判断。

       重复以上过程，直到连通图中所有顶点都被访问过为止。（图的深度优先搜索遍历类似树的先序遍历）

2、广度优先搜索遍历：

       一种图的遍历方式：从图中任意一个起始顶点 V 出发，依次访问该顶点的所有邻接顶点 V1、V2……Vn。所有邻接顶点访问完成后，再按照这些邻接顶点被访问的先后次序 依次访问与其相邻接的所有未被访问过的顶点。重复此过程，直至所有顶点均被访问为止。（图的广度优先搜索遍历类似树的层序遍历）

3、拓扑排序：

       拓扑排序通常是针对一种特殊的图——有向无环图（DAG），拓扑排序可以将图中的所有顶点排列成一个线性序列，该线性序列满足以下要求：

       对于图 G 中任意一对顶点 u 和 v ，若弧 <u,v> ∈ E(G)，则 u 在该线性序列中一定会出现在 v 之前。

4、最小生成树：

       以无向网为例，在该网的所有生成树中，使得各边的权值之和最小的生成树即该网的最小生成树，也称为最小代价生成树。

       构造最小生成树的方法有：Prim算法、Kruskal算法。

5、最短路径：

       在网图中：从某一顶点A（源点）到另一个顶点B（终点）的所有路径中，各边权值之和最小的路径即为最短路径。

       在非网图中：从某一顶点A（源点）到另一个顶点B（终点）的所有路径中，边数之和最小的路径即为最短路径。

       找出最短路径的方法有：Dijkstra算法、Floyd算法。

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果。

#include<stdio.h>

#define N 20       /*图中顶点数目的最大值为N*/
#define TRUE 1
#define FALSE 0

int visited[N];    /*访问标识数组*/
typedef struct     /*队列的定义*/
{
    int data[N];
    int front,rear;
}queue;

typedef struct     /*定义图的邻接矩阵*/
{
    int vexnum,arcnum;        //图中顶点数目、边/弧的数目
    char vexs[N];             //一维数组：存储顶点信息
    int arcs[N][N];           //二维数组：存储顶点与顶点之间的关系
}graph;

void createGraph(graph *g);   /*建立一个无向图的邻接矩阵*/
void dfs(int i,graph *g);     /*从第i个顶点出发进行深度优先搜索*/
void tdfs(graph *g);          /*深度优先搜索整个图*/
void bfs(int k,graph *g);     /*从第k个顶点出发进行广度优先搜索*/
void tbfs(graph *g);          /*广度优先搜索整个图*/
void init_visit();            /*初始化访问标识数组*/

void createGraph(graph *g)    /*建立一个无向图的邻接矩阵*/
{
    int i,j;
    char v;
    g->vexnum = 0;
    g->arcnum = 0;
    i=0;
    printf("输入顶点序列(以#结束)：\n");
    while((v=getchar()) != '#')
    {
        g->vexs[i] = v;        /*读入顶点信息*/
        i++;
    }
    g->vexnum = i;             /*顶点数目*/

    for(i=0;i<g->vexnum;i++)   /*邻接矩阵初始化*/
        for(j=0;j<g->vexnum;j++)
            g->arcs[i][j] = 0;

    printf("输入边的信息(以-1,…结束)：\n");
    scanf("%d,%d",&i,&j);      /*读入边i,j*/
    while(i != -1)             /*读入i,j为-1时结束*/
    {
        g->arcs[i][j] = 1;
        g->arcs[j][i] = 1;
        scanf("%d,%d",&i,&j);
    }
}

void dfs(int i,graph *g)    /*从第i个顶点出发进行深度优先搜索*/
{
    int j;
    printf("%c",g->vexs[i]);
    visited[i] = TRUE;
    for(j=0;j<g->vexnum;j++)
        if((g->arcs[i][j]==1) && (!visited[j]))  //若第j个顶点与第i个顶点邻接且未被访问,则访问该顶点
            dfs(j,g);
}

void tdfs(graph *g)      /*深度优先搜索整个图*/
{
    int i;
    printf("\n从顶点%c开始深度优先搜索序列：",g->vexs[0]);
    for(i=0;i<g->vexnum;i++)
        if(visited[i] != TRUE)
            dfs(i,g);
}

void bfs(int k,graph *g)  /*从第k个顶点出发进行广度优先搜索*/
{
    int i,j;
    queue qlist;
    queue *q;
    q = &qlist;
    q->rear = 0;
    q->front = 0;
    printf("%c",g->vexs[k]);   //访问第k个顶点
    visited[k] = TRUE;
    q->data[q->rear] = k;      //第k个顶点入队(这里是将顶点下标k入队)
    q->rear = (q->rear+1)%N;
    while(q->rear != q->front) //队列非空时
    {
        i = q->data[q->front]; //队头元素出队
        q->front = (q->front+1)%N;

        //访问出队顶点所有相邻接、未被访问过的顶点。并在访问后将其入队
        for(j=0;j<g->vexnum;j++)
            if((g->arcs[i][j]==1) && (!visited[j]))
            {
                printf("%c",g->vexs[j]);
                visited[j] = TRUE;
                q->data[q->rear] = j;
                q->rear =( q->rear+1)%N;
            }
    }
}

void tbfs(graph *g) /*广度优先搜索整个图*/
{
    int i;
    printf("\n从顶点%c开始广度优先搜索序列：",g->vexs[0]);
    for(i=0;i<g->vexnum;i++)
        if(visited[i] != TRUE)
            bfs(i,g);
}

void init_visit()   /*初始化访问标识数组*/
{
    int i;
    for(i=0;i<N;i++)
        visited[i] = FALSE;
}

int main()
{
    graph ga;
    int i,j;
    createGraph(&ga);
    printf("无向图的邻接矩阵：\n");
    for(i=0;i<ga.vexnum;i++)
    {
        for(j=0;j<ga.vexnum;j++)
            printf("%3d",ga.arcs[i][j]);
        printf("\n");
    }
    init_visit();
    tdfs(&ga);
    init_visit();
    tbfs(&ga);
    return 0;
}

• 根据上图的结构验证实验，输入：

ABCDEFGH#

0,1

0,2

0,5

1,3

1,4

2,5

2,6

3,7

4,7

-1,-1

• 运行结果： 

• 这里我对 tdfs 函数做了一点修改：

void tdfs(graph *g)      /*从图中各个顶点开始深度优先搜索整个图*/
{
    int i;
    for(i=0;i<g->vexnum;i++)
    {
        if(visited[i] != TRUE)
        {
            printf("\n从顶点%c开始深度优先搜索序列：",g->vexs[i]);
            dfs(i,g);
            printf("\n");
        }
        init_visit();  //每一轮遍历完成后需要初始化访问标识数组
    }
}

• 同样的输入，运行结果：

可以得到从不同的顶点出发进行DFS产生的搜索序列，同样的也可以对 tbfs 函数进行修改。

2、阅读并运行下面程序，补充拓扑排序算法。

#include<stdio.h>
#include<malloc.h>

#define N 20               /*图中顶点数目的最大值为N*/

typedef struct edgenode{   /*图的邻接表：邻接链表结点*/
    int adjvex;            /*顶点序号*/
    struct edgenode *next; /*下一个结点的指针*/
}edgenode;

typedef struct vnode{       /*图的邻接表：邻接表*/
    char data;              /*顶点信息*/
    int ind;                /*顶点入度*/
    struct edgenode *link;  /*指向邻接链表指针*/
}vnode;

void createGraph_list(vnode adjlist[],int *p);  /*建立有向图的邻接表*/
void topSort(vnode g[],int n);                  /*拓扑排序*/

void createGraph_list(vnode adjlist[],int *p){  /*建立有向图的邻接表(其中指针p返回顶点个数)*/
    int i,j,n,e;
    char v;
    edgenode *s;
    i=0;
    n=0;
    e=0;
    printf("输入顶点序列(以#结束)：\n");
    while((v=getchar()) != '#')
    {
        adjlist[i].data = v;        /*读入顶点信息*/
        adjlist[i].link = NULL;     /*初始化邻接表指针*/
        adjlist[i].ind = 0;         /*初始化顶点入度*/
        i++;
    }
    n = i;   //图中顶点数目
    *p = n;  //通过p返回顶点个数

    /*建立邻接链表*/
    printf("\n请输入弧的信息(i=-1结束)：i,j:\n");
    scanf("%d,%d",&i,&j);
    while(i != -1)
    {
        s = (struct edgenode*)malloc(sizeof(edgenode));
        s->adjvex = j;
        //使用头插法插入邻接结点
        s->next = adjlist[i].link;
        adjlist[i].link = s;
        adjlist[j].ind++;  /*顶点j的入度加1*/
        e++;
        scanf("%d,%d",&i,&j);
    }

    /*输出邻接链表*/
    printf("邻接表:\n顶点,入度:->邻接顶点序号");
    for(i=0;i<n;i++)
    {
        printf("\n%c,%d:",adjlist[i].data,adjlist[i].ind);
        s = adjlist[i].link;  //s指向顶点i的邻接链表结点
        while(s != NULL)
        {
            printf("->%d",s->adjvex);  //输出邻接链表结点中的顶点序号
            s = s->next;
        }
    }
}

void topSort(vnode g[],int n)  /*拓扑排序*/
{
    
}

int main()
{
    vnode adjlist[N];
    int n,*p;
    p = &n;  //n为图中顶点数
    createGraph_list(adjlist,p);
    printf("\n\n");
    topSort(adjlist,n);
    return 0;
}

拓扑排序算法代码：

//g[]为图的邻接表,n为图中顶点数
void topSort(vnode g[],int n)   /*拓扑排序*/
{
    printf("拓扑排序顶点序列：\n");
    int i,j,k,m = 0;
    int top = -1;  //初始化栈为空,栈顶指针top置为-1
    struct edgenode *p;

    //遍历图中所有顶点,将度为0的顶点都入栈
    for(i=0;i<n;i++)
    {
        if(0 == g[i].ind)
        {
            g[i].ind = top;   
            top = i;
        }
    }

    //栈非空
    while(-1 != top)
    {
        j = top;                
        printf("%c",g[j].data);  //输出栈顶顶点
        m++;                     //m为拓扑排序序列中的顶点数(可判断图中是否有环)
        top = g[j].ind;        //出栈

        //顶点j输出后还需修改邻接自j的顶点的入度(即删除顶点j和所有以它为弧尾的弧)
        p = g[j].link;           //p指向顶点j的第一个邻接结点
        while( p )
        {
            k = p->adjvex;       //k为邻接顶点序号
            g[k].ind--;          //邻接顶点入度-1

            //将入度为0的顶点入栈
            if(0 == g[k].ind)
            {
                g[k].ind = top;
                top = k;
            }
            p = p->next;         //p继续指向下一个邻接结点
        }
    }

    //如果拓扑序列中不包含图中所有顶点,则图中一定存在环
    if(m < n)
        printf("图中存在环");
}

这里的拓扑排序利用了栈，但是代码中并没有明确定义栈结构，而是采用了一种比较巧妙的方法，只通过一个栈顶指针 top 指示栈顶元素，通过修改 top 的值进行入栈/出栈操作。

  

比如在遍历图中所有顶点，并将度为0的顶点都入栈时，入栈操作是将入栈顶点的入度修改为前一位入栈顶点的序号(即栈顶顶点的序号)，并将top置为入栈顶点的序号。(通过入度的指示构成了一个栈)

top = -1;

for(i=0;i<n;i++)
{
    if(0 == g[i].ind)     //度为0的顶点入栈
    {
        g[i].ind = top;   //将入栈顶点的入度置为栈顶顶点的序号(栈底顶点入度置为-1)
        top = i;             //将top置为入栈顶点的序号
    }
}

//循环结束时top=栈顶顶点的序号

而在出栈操作时将 top 置为栈顶顶点的入度，即指向下一位栈中元素。

top = g[j].ind;        //栈顶顶点出栈

• 根据输入，输出有向图的拓扑排序序列。并画出有向图。输入: 

ABCDEF#

0,1

1,2

2,3

4,1

4,5

-1,-1

• 该有向图应该如下图所示：

• 运行结果： 

3、阅读并运行下面程序。 

【注】

以下代码和网上提供的实验代码有区别，老师提供代码的以及网上的大部分代码都有一点问题：

在求最短路径时，输出的最短路径长度正确，但是最短路径经过的顶点有问题。以下代码是在这些问题代码的基础上修改得到的。

#include<stdio.h>

#define N 20
#define TRUE
#define INF 32766       /*邻接矩阵中的无穷大元素*/
#define INFIN 32767     /*比无穷大元素大的数*/

typedef struct
{
    int vexnum,arcnum;
    char vexs[N];
    int arcs[N][N];
}graph;                 /*图的邻接矩阵*/

void createGraph_w(graph *g,int flag);   /*建带权图的邻接矩阵*/
void prim(graph *g,int u);               /*Prim算法构造最小生成树*/
void dijkstra(graph g,int v);            /*dijkstra算法求单源最短路径*/
void showprim();                         /*prim算法演示*/
void showdij();                          /*dijkstra算法演示*/
void printPath(graph g,int startVex,int EndVex,int path[N][N]);
                                         /*输出两顶点间的最短路径*/

/*建带权图的邻接矩阵,若flag为1则为无向图,flag为0为有向图*/
void createGraph_w(graph *g,int flag)
{
    int i,j,w;
    char v;
    g->vexnum = 0;
    g->arcnum = 0;
    i = 0;
    printf("输入顶点序列(以#结束)：\n");
    while((v=getchar()) != '#')
    {
        g->vexs[i] = v;          /*读入顶点信息*/
        i++;
    }
    g->vexnum = i;
    for(i=0;i<g->vexnum;i++)     /*邻接矩阵初始化*/
        for(j=0;j<g->vexnum;j++)
            g->arcs[i][j] = INF;
    printf("输入边/弧的信息(如果是有向图请注意弧头、弧尾顺序)：i,j,weight\n");
    scanf("%d,%d,%d",&i,&j,&w);  /*读入边(i,j,w)*/
    while(-1 != i)               /*读入i为-1时结束*/
    {
        g->arcs[i][j] = w;
        if(1 == flag)
            g->arcs[j][i] = w;
        scanf("%d,%d,%d",&i,&j,&w);
    }
}

/*Prim算法构造图g的最小生成树(g为无向图,u为出发顶点)*/
void prim(graph *g,int u)
{
    int i,j,k,min;
    int lowcost[N];             //lowcost[i]为顶点i到最小生成树中所有顶点间的最小权值(lowcost[i]=0表示顶点i属于MST)
    int closest[N];             //closest[i]为最小生成树中所有顶点间到顶点i最近的一个顶点序号
    for(i=0;i<g->vexnum;i++)    /*求其他顶点到出发顶点u的权*/
    {
        lowcost[i] = g->arcs[u][i];
        closest[i] = u;
    }
    lowcost[u]=0;
    for(i=1;i<g->vexnum;i++)    /*循环求最小生成树中的各条边*/
    {
        min = INFIN;
        for(j=0;j<g->vexnum;j++) //找到不属于最小生成树,且到最小生成树中所有顶点间权值最小的顶点k
        {
            if(lowcost[j]!=0 && lowcost[j]<min)
            {
                min = lowcost[j];
                k = j;
            }
        }
        printf("(%c,%c)--%d\n",g->vexs[closest[k]],g->vexs[k],lowcost[k]);  /*输出该边*/
        lowcost[k] = 0;           /*顶点k加入最小生成树*/

        for(j=0;j<g->vexnum;j++)  //每加入一个顶点,需更新不属于MST的顶点到MST中顶点的最小权值,以及对应的最近的顶点
        {
            if(g->arcs[k][j]!=0 && g->arcs[k][j]<lowcost[j])
            {
                lowcost[j] = g->arcs[k][j];
                closest[j] = k;
            }
        }
    }
}

/*输出图g中顶点startVex到EndVex的最短路径*/
void printPath(graph g,int startVex,int EndVex,int path[N][N])
{
    int stack[N],top = 0;    /*准备一个栈*/
    int flag[N];             /*输出路径顶点标志(1:已输出;0:未输出)*/
    int i,s,e;
    for(i=0;i<g.vexnum;i++)  //初始化flag[i]为0
        flag[i] = 0;
    s = startVex;
    e = EndVex;
    printf("%c",g.vexs[s]);
    flag[s] = 1;
    stack[top++] = e;  //终点e入栈

    while(top > 0)     /*寻找s到e的路径*/
    {
        for(i=0;i<g.vexnum;i++)   //遍历s到e的最短路径中经过的,且还未输出的顶点
        {
            if(1==path[e][i] && 0==flag[i])
            {
                if(g.arcs[s][i] != INF)   //s到i的最短路径就是s->i,不包含其它顶点
                {
                    printf("->%c(%d)",g.vexs[i],g.arcs[s][i]);
                    flag[i] = 1;
                    s = i;
                    e = stack[--top];  //出栈
                    break;
                }
                if(g.arcs[s][i]==INF && i!=e)   //s到i的最短路径包含其它顶点
                    stack[top++] = i;  //入栈
            }
        }
    }
    //判断终点e是否输出
    if(0 == flag[e])
    {
        printf("->%c(%d)",g.vexs[e],g.arcs[s][e]);
        flag[e] = 1;
    }
}

/*dijkstra算法求图g的单源最短路径,v为源点序号*/
void dijkstra(graph g,int v)
{
    int dist[N];        //dist[i]表示:源点v到顶点i的最短路径长度(初始化为INF)
    int s[N];           //s[i]表示:是否找到源点v到顶点i的最短路径(0:未找到;1:已找到)
    int path[N][N];     //path[i][j]表示:源点v到顶点i的最短路径是否经过顶点j(0:不经过;1:经过)
    int mindis;         //mindis表示:在所有还未找到最短路径的顶点中,dist[i]的最小值(即与源点最近的距离)
    int i,j,u,k;
    for(i=0;i<g.vexnum;i++)      /*初始化操作*/
    {
        dist[i] = g.arcs[v][i];
        s[i] = 0;
        for(j=0;j<g.vexnum;j++)
            path[i][j] = 0;
        //顶点v到顶点i有弧(即弧的权值小于INF),则源点v到顶点i的最短路径经过v、i
        if(g.arcs[v][i] < INF)
        {
            path[i][v] = 1;
            path[i][i] = 1;
        }
    }
    dist[v] = 0;  //自身到自身距离为0
    s[v] = 1;     //自身到自身没有最短路径
    for(i=1;i<g.vexnum;i++)
    {
        mindis = INFIN;
        for(j=0;j<g.vexnum;j++)   //遍历所有还未找到最短路径的顶点,找出dist[]值最小的顶点u,并更新mindis
        {
            if((0==s[j]) && (dist[j]<mindis))
            {
                u = j;
                mindis=dist[j];
            }
        }
        s[u]=1;   //顶点u的最短路径已找到

        //每找到一个顶点的最短路径,需判断加入其作为中间顶点后,其余未找到最短路径的顶点到源点距离是否减小,若减小则更新距离dist
        for(j=0;j<g.vexnum;j++)
        {
            if((s[j]==0) && (dist[u]+g.arcs[u][j]<dist[j]))
            {
                dist[j] = dist[u]+g.arcs[u][j]; //更新最短距离dist
                for(k=0;k<g.vexnum;k++)
                    path[j][k] = path[u][k];    //顶点u最短路径经过的所有顶点
                path[j][j] = 1;                 //顶点自身
                g.arcs[v][j] = INF;
            }
        }
    }
    //循环vexnum-1次后:
    //dist[i]的值就是通过dijkstra算法计算出的源点v到顶点i的最短路径长度
    //path[i][…]则记录了顶点i最短路径经过的所有顶点

    printf("\n顶点%c->到各顶点的最短路径\n",g.vexs[v]);
    for(i=0;i<g.vexnum;i++)
    {
        printf("\n顶点%c->顶点%c：",g.vexs[v],g.vexs[i]);
        if(dist[i]==INF || dist[i]==0)
            printf("无路径");
        else
        {
            printf("最短路径长度=%d  ",dist[i]);
            printf("经过顶点：");
            //这里给printPath函数新添了一个参数path,以传入图g的path数组,不然会报错
            printPath(g,v,i,path);  /*输出v到i的路径*/
        }
    }
}

void showprim()    /*最小生成树prim算法演示*/
{
    graph ga;
    createGraph_w(&ga,1);
    printf("最小生成树：\n");
    prim(&ga,0);
}

void showdij()    /*dijstra算法演示*/
{
    graph ga;
    createGraph_w(&ga,0);
    dijkstra(ga,0);
}

int main()
{
    showprim();   /*prim算法演示*/
    getchar();
    showdij();    /*dijstra算法演示*/
    return 0;
}

• 下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图，求其最小生成树；输入的第二部分为有向图，求其最短路径。

ABCDEF#

0,1,6

0,2,1

0,3,5

1,2,5

1,4,3

2,3,5

2,4,6

2,5,4

3,5,2

4,5,6

-1,-1,-1

二、最短路径，输入：

ABCDEF#

0,2,10

0,5,100

0,4,30

1,2,5

2,3,50

3,4,20

3,5,10

4,3,20

4,5,60

-1,-1,-1

• 运行结果：（并画出两个图）

• 第一个图

• 第二个图

一开始我是直接运行的老师提供的代码，运行结果如下：

求最小生成树是对的，但是求最短路径时出问题（网上大部分代码运行结果都如下图）

所以不仅是让我们运行程序，还需要对这些代码进行修改才能正常工作。

可以对比一下出问题的代码，看看什么地方进行了修改，以及错误的原因。

• 关于上面的代码，弄清楚其中各个数组代表的意义，算法的实现过程就比较清晰了

Prim算法构造最短生成树：

lowcost数组记录不属于最小生成树的顶点到属于最小生成树的顶点中的最小代价

• lowcost[i]的值为顶点 i 到最小生成树中所有顶点间的最小权值
• lowcost[i]=0：顶点 i 属于最小生成树

closest数组记录最小生成树中的所有顶点到其余顶点代价最小的一个

• closest[i]的值为最小生成树中所有顶点间到顶点 i 最近的一个顶点的序号

dijkstra算法求最短路径：

dist数组记录源点到各个顶点的最短路径长度

• dist[i]的值为源点 v 到顶点 i 的最短路径长度
• dist[i]初始化为源点 v 到顶点 i 的弧的权值，之后再不断更新

s数组记录是否找到源点到各个顶点的最短路径

• s[i]=0：未找到源点 v 到顶点 i 的最短路径
• s[i]=1：找到源点 v 到顶点 i 的最短路径

path数组记录源点到各个顶点的最短路径是否包含其它顶点

• path[i][j]=0：源点 v 到顶点 i 的最短路径不经过顶点 j
• path[i][j]=1：源点 v 到顶点 i 的最短路径经过顶点 j

另外在printPath函数中输出最短路径经过的顶点时，需要注意：

不能直接按序号由小到大依次输出经过的顶点，那样输出的只是最短路径经过的顶点，而非正确的路径顺序。

g.arcs[s][i] != INF：s 到 i 的最短路径就是s->i，不包含其它顶点，可直接输出

g.arcs[s][i] == INF：s 到 i 的最短路径包含其它顶点，不可直接输出，暂时入栈保存