第8章_图论

图是又一种非线性数据结构。在图结构中，数据元素之间的关系是多对多的，即如果任选一个结点作为初始结点，则图中任意一个结点有多个前驱结点和多个后继结点。

图

图是由结点集合及结点间的关系集合组成的一种数据结构。

图的实现

领接矩阵存储结构下图操作的实现

例：带权图为

SeqList.h

typedef struct {
    DataType list[MaxSize];
    int size;
}SeqList;

//顺序表操作实现
//1.初始化
void ListInitiate(SeqList*L)
{
    L->size = ;//定义初始数据元素个数
}

//2.求当前数据元素个数
int ListLength(SeqList L)
{
    return L.size;//返回顺序表L的当前数据元素个数
}

//3.插入数据元素
int ListInsert(SeqList*L,int i,DataType x)
{
    /*
    在顺序表L的第i(0<=i<=size)个位置前插入数据元素值x
    插入成功返回1，插入失败返回0
    */
    int j;
    if(L->size >= MaxSize)
    {
        printf("顺序表已满无法插入！\n");
        return ;
    }
    else if(i <  || i > L->size)
    {
        printf("参数i不合法！\n");
        return ;
    }
    else
    {
        /*为插入做准备*/
        for(j=L->size;j > i; j--)
        {
            L->list[j] = L->list[j-];
        }
        L->list[i] = x; /*插入元素x*/
        L->size++;      /*元素个数加1*/
        return ;
    }
}

//4.删除数据元素
int ListDelete(SeqList*L,int i,DataType*x)
{
    /*
    删除顺序表L中位置为i(0<=i<=size-1)的数据元素并存放到x中
    删除成功返回1，删除失败返回0
  */
    int j;
    if(L->size <= )
    {
        printf("顺序表已空无数据元素可删！\n");
        return ;
    }
    else if(i <  || i > L->size - )
    {
        printf("参数i不合法\n");
        return ;
    }
    else
    {
        *x = L->list[i];    /* 保存删除的元素到x中*/
        for(j = i;j < L->size-; j++)
        {
            L->list[j] = L->list[j+];
        }
        L->size--;          /*数据元素个数减1*/
        return ;
    }
}

//5.取数据元素
int ListGet(SeqList L,int i,DataType* x)
{
    /* 取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0*/
    if(i <  || i > L.size - )
    {
        printf("参数i不合法！\n");
        return ;
    }
    else
    {
        *x=L.list[i];
        return ;
    }
}
           

AdjMGraph.h

#include "SeqList.h"        //包含顺序表头文件

typedef struct 
{
    SeqList Vertices;                       //存放结点的顺序表
    int edge[MaxVertices][MaxVertices];     //存放边的邻接矩阵
    int numOfEdges;                         //边的条数
} AdjMGraph;                                //图的结构体定义

void Initiate(AdjMGraph* G,int n)   //初始化
{
    int i,j;
    for(i = ;i < n; i++)
    {
        for(j = ;j < n; j++)
        {
            if(i == j) G->edge[i][j] = ;
            else
                G->edge[i][j] = MaxWeight;
        }
    }

    G->numOfEdges = ;              //连的条数置为0
    ListInitiate(&G->Vertices);     //顺序表初始化
}

//在图G中插入结vertex
void InsertVertex(AdjMGraph*G,DataType vertex)
{
    ListInsert(&G->Vertices,G->Vertices.size,vertex);       //在顺序表尾插入
}


//在图G中插入边<v1,v2>,边<v1,v2>的权为weight
void InsertEdge(AdjMGraph*G,int v1,int v2,int weight)
{
    if(v1 <  || v1 > G->Vertices.size || v2 <  || v2 > G->Vertices.size)
    {
        printf("参数v1或v2越界出错！\n");
        exit();
    }

    G->edge[v1][v2] = weight;
    G->numOfEdges ++;
}

//在图G中删除边<v1,v2>
void DeleteEdge(AdjMGraph*G,int v1,int v2)
{
    if(v1 <  || v1 > G->Vertices.size || v2 <  || v2 > G->Vertices.size || v1 == v2)
    {
        printf("参数v1或v2越界出错！\n");
        exit();
    }

    if(G->edge[v1][v2] == MaxWeight || v1 == v2)
    {
        printf("该边不存在！\n");
        exit();
    }

    G->edge[v1][v2] = MaxWeight;
    G->numOfEdges--;
}

//删除结点V
void DeleteVerten(AdjMGraph*G,int V)
{
    int n = ListLength(G->Vertices),i,j;
    DataType x;
    for(i = ;i < n; i++)
    {
        for(j = ;j < n; j++)
        {
            if((i == V || j == V) && G->edge[i][j] >  && G->edge[i][j] < MaxWeight)
                G->numOfEdges--;            //计算被删除边
        }
    }

    for(i = V;i < n; i++)
        for(j = ;j < n; j++)
            G->edge[i][j] = G->edge[i + ][j];
    for(i = ;i < n; i++)
        for(j = V; j < n; j++)                  //删除结第V列
            G->edge[i][j] = G->edge[i][j + ];
    ListDelete(&G->Vertices,V,&x);              //删除结V
}

//在图G中寻找序号为v的结点的第一个邻接结点
//如果这样的邻 接结存在，返回该邻接结的序号；否则，返回-1
int GetFirstVex(AdjMGraph G,int v)
{
    int col;
    if(v <  || v > G.Vertices.size)
    {
        printf("参数v1越界出错！\n");
        exit();
    }

    for(col = ;col < G.Vertices.size; col++)
        if(G.edge[v][col] >  && G.edge[v][col] < MaxWeight) return col;
    return -;
}

//在图G中寻找v1结点的邻接结点v2的下一个邻接结点
//如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1
//v1和v2都是相应结点的序号
int GetNextVex(AdjMGraph G,int v1,int v2)
{
    int col;
    if(v1 <  || v1 > G.Vertices.size || v2 <  || v2 > G.Vertices.size)
    {
        printf("参数v1或v2越界出错！\n");
        exit();
    }

    for(col = v2 + ;col < G.Vertices.size; col++)
        if(G.edge[v1][col] >  && G.edge[v1][col] < MaxWeight) return col;
    return -;
}
           

AdjMGraphCreate.h

typedef struct 
{
    int row;        //行下标
    int col;        //列下标
    int weight;     //权值
} RowColWeight;     //边信息结构体定义

//在图G中插入n个结点信息V和e条边信息E
void CreatGraph(AdjMGraph*G,DataType V[],int n,RowColWeight E[],int e)
{
    int i,k;
    Initiate(G,n);
    for(i = ;i < n; i++)
        InsertVertex(G,V[i]);                           //结点插入
    for(k = ;k < e; k++)
        InsertEdge(G,E[k].row,E[k].col,E[k].weight);    //边插入
}
           

main.c

#include <stdio.h>
#include <stdlib.h>

typedef char DataType;
#define MaxSize 100
#define MaxVertices 10
#define MaxEdges 100
#define MaxWeight 10000

#include "AdjMGraph.h"
#include "AdjMGraphCreate.h"

void main(void)
{
    AdjMGraph g1;
    DataType a[] = {'A','B','C','D','E'};
    RowColWeight rcw[] = {
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
    };
    int n = ,e = ;
    int i,j;

    CreatGraph(&g1,a,n,rcw,e);
    DeleteEdge(&g1,,);        //删除<0,4>
    DeleteVerten(&g1,);        //删除结点3

    printf("结点集合为：");
    for(i = ;i < g1.Vertices.size; i++)
        printf("%c ",g1.Vertices.list[i]);
    printf("\n");

    printf("权值集合为：\n");
    for(i = ;i < g1.Vertices.size; i++)
    {
        for(j = ;j < g1.Vertices.size; j++)
            printf("%5d ",g1.edge[i][j]);
        printf("\n");
    }
}
           

邻接表的存储结构

typedef struct Node
{
    int dest;               //邻接边的弧头结点序号
    struct Node * next;     
} Edge;                     //邻接边单链表的结点结构体

typedef struct 
{
    DataType data;          //结点数据元素
    int score;              //邻接边的弧尾结点序号
    Edge * adj;             //邻接边的头指针
} AdjLHeight;               //数组的数据元素类型结构体

typedef struct 
{
    AdjLHeight a[MaxVertices];  //邻接表数组
    int numOfVerts;             //结点个数
    int numOfEdges;             //边个数
} AdjLGraph;                    //邻接表结构体

//初始化操作函数
void AdjInitiate(AdjLGraph* G)
{
    int i;
    G->numOfVerts = ;
    G->numOfEdges = ;
    for(i = ;i < MaxVertices; i++)
    {
        G->a[i].score = i;          //置邻接边的弧头结点
        G->a[i].adj = NULL;         //置邻接边单链表头指针初值
    }
}

//撤消操作函数
void AdjDestroy(AdjLGraph*G)
{
    int i;
    Edge*p,*q;
    for(i = ;i < G->numOfVerts; i++)
    {
        p = G->a[i].adj;
        while(p != NULL)
        {
            q = p->next;
            free(p);
            p = q;
        }
    }
}

//插入结点操作函数
//在图G中的第i(0<=i<MaxVertices)个位置插入结点数据元素vertex
void InsertVertex(AdjLGraph*G,int i,DataType vertex)
{
    if(i >=  && i < MaxVertices)
    {
        G->a[i].data = vertex;          //存储结点数据元素vertex
        G->numOfVerts++;                //个数加1
    }
    else
        printf("结点越界");
}

//插入边操作函数
//在图G中加入边<v1,v2>的信息
void InsertEdge(AdjLGraph*G,int v1,int v2)
{
    Edge*p;
    if(v1 <  || v1 >= G->numOfVerts || v2 <  || v2 >= G->numOfVerts)
    {
        printf("参数v1或v2越界出错！");
        exit();
    }

    p = (Edge*)malloc(sizeof(Edge));        //申请邻接边单链表结点空间
    p->dest = v2;                           //置邻接边弧头序号
    p->next = G->a[v1].adj;                 //新结点插入单链表的表头
    G->numOfEdges++;                        //边个数加1
}

//删除边操作函数
//删除图G中的边<v1,v2>信息
void DeleteEdge(AdjLGraph*G,int v1,int v2)
{
    Edge*curr,*pre;
    if(v1 <  || v1 >= G->numOfVerts || v2 <  || v2 >= G->numOfVerts)
    {
        printf("参数v1或v2越界出错！");
        exit();
    }

    pre = NULL;
    curr = G->a[v1].adj;

    while(curr != NULL && curr->dest != v2)
    {
        //在v1结点的邻接边单链表中查找v2结点
        pre = curr;
        curr = curr->next;
    }

    //删除表示邻接边<v1,v2>的结点
    if(curr != NULL && curr->dest == v2 && pre == NULL)
    {
        //当邻 接边<v1,v2>的结点是单链表的第一个结点时
        G->a[v1].adj = curr->next;
        free(curr);
        G->numOfEdges--;
    }
    else if(curr != NULL && curr->dest == v2 && pre != NULL)
    {
        //当邻 接边<v1,v2>的结点不是单链表的第一个结点时
        pre->next = curr->next;
        free(curr);
        G->numOfEdges--;
    }
    else
    {
        //当邻接边<v1,v2>的结点不存在时
        printf("边<v1,v2>不存在！");
    }
}

//取第1个邻接结点
int GetFirstVex(AdjLGraph G,int v)
{
    //取图G中结点v的第一个邻接结点
    //取到时返回该邻接结点的对应序号，否则返回-1
    Edge*p;
    if(v <  || v > G.numOfVerts)
    {
        printf("参数v1或v2越界出错！");
        exit();
    }

    p = G.a[v].adj;
    if(p != NULL) return p->dest;   //返回该邻接结点的对应序号
    else
        return -;                  //返回-1
}

//取下一个邻接结点
//取图G中结点v1的邻 接结点v2的下一个邻接结点
//取到时返回该邻 接结瓣对应序号，否则返回-1
int GetNextVex(AdjLGraph G,int v1,const int v2)
{
    Edge * p;
    if(v1 <  || v1 > G.numOfVerts || v2 <  || v2 > G.numOfVerts)
    {
        printf("参数v1或v2越界出错！");
        exit();
    }

    p = G.a[v1].adj;
    while(p != NULL)
    {
        if(p->dest != v2)
        {
            p = p->next;
            continue;
        }
        else break;
    }

    p = p->next;                        //p指向邻接结点v2的下一个邻 接结点
    if(p != NULL) return p->dest;       //返回该邻接结点的对应序号
    else return -;                     //返回-1
}

typedef struct 
{
    int row;        //行下标
    int col;        //列下标
    int weight;     //权值
} RowCol;       //边信息结构体定义

//创建图
//创建有n个结点e条边的图G
//结点信息存放在数组v中，边信息存放在数组d中
void CreateGraph(AdjLGraph*G,DataType v[],int n,RowCol d[],int e)
{
    int i,k;
    AdjInitiate(G);
    for(i = ;i < n; i++) InsertVertex(G,i,v[i]);           //插入结点
    for(k = ;k < e; k++) InsertEdge(G,d[k].row,d[k].col);  //插入边
}

           

图的遍历

图的深度和广度优先遍历算法

与树的遍历操作相似，图遍历操作的定义是访问图中的每一个结点且每个结点只被访问一次。图的遍历方法主要有两种：一种是深度优先搜索遍历，另一种是广度优先搜索遍历。图的深度优先搜索遍历类同于树的先根遍历，图的广度优先搜索遍历类同于树的层序遍历。

深度优先遍历

AdjMGraphTraverse.h

#include "SeqCQueue.h"

//连通图G以v为初始结点的访问操作为Visit()的深度优先遍历
//数组visited标记了相应结点是否已访问过，0表示未访问，1表示已访问
void DepthFSearch(AdjMGraph G,int v,int visited[],void Visit(DataType item))
{
    int w;
    Visit(G.Vertices.list[v]);          //访问结点
    visited[v] = ;                     //置已访问标记

    w = GetFirstVex(G,v);               //取第一个邻接结点
    while(w != -)
    {
        if(!visited[w])
            DepthFSearch(G,w,visited,Visit);    //递归
        w = GetNextVex(G,v,w);                  //取下一个邻接结点
    }
}

//非连通图G的访问操作为Visit()的深度优先遍历
void DepthFirstSearch(AdjMGraph G,void Visit(DataType item))
{
    int i;
    int * visited = (int*)malloc(sizeof(int)*G.Vertices.size);
    for(i = ;i < G.Vertices.size; i++)
        visited[i] = ;
    for(i = ;i < G.Vertices.size; i++)
        if(!visited[i])
            DepthFSearch(G,i,visited,Visit);

    free(visited);
}


//广度优先遍历
//连通图G以v为初始结点访问操作为Visit()的广度优先遍历
//数组visited标记了相应结点是否已访问过，0表示未访问，1表示已访问
void BroadFSearch(AdjMGraph G,int v,int visited[],void Visit(DataType item))
{
    DataType u,w;
    SeqCQueue queue;
    Visit(G.Vertices.list[v]);      //访问结点
    visited[v] = ;

    QueueInitiate(&queue);          //队列初始化
    QueueAppend(&queue,v);          //初始结点v入入
    while(QueueNotEmpty(queue))     //队列非空时
    {
        QueueDelete(&queue,&u);     //出队列
        w = GetFirstVex(G,u);       //取结点u的第一个邻接结点
        while(w != -)
        {
            if(!visited[w])
            {
                Visit(G.Vertices.list[w]);      //访问结点w
                visited[w] = ;                 //置已访问标记
                QueueAppend(&queue,w);          //结点w入队列
            }
            w = GetNextVex(G,u,w);              //取下一个邻接结点
        }
    }
}

//非连通图G访问操作为Visit()的广度优先遍历
void BroadFirstSearch(AdjMGraph G,void Visit(DataType item))
{
    int i;
    int * visited = (int*)malloc(sizeof(int)*G.Vertices.size);

    for(i = ;i < G.Vertices.size; i++)
        visited[i] = ;
    for(i = ;i < G.Vertices.size; i++)
        if(!visited[i]) BroadFSearch(G,i,visited,Visit);
    free(visited);
}
           

main.c

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

typedef char DataType;
#define MaxSize 100
#define MaxVertices 10
#define MaxEdges 100
#define MaxWeight 10000
#define MaxQueueSize 100

#include "AdjMGraph.h"
#include "AdjMGraphCreate.h"
#include "AdjMGraphTraverse.h"

void Visit(DataType item) //定义访问操作的函数
{
    printf("%c ",item);
}

void main(void)
{
    AdjMGraph g1;
    DataType a[] = {'A','B','C','D','E'};
    RowColWeight rcw[] = {
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
    };
    int n = ,e = ;

    CreatGraph(&g1,a,n,rcw,e);

    printf("深度优先搜索序列为：");
    DepthFirstSearch(g1,Visit);

    printf("\n广度优先搜索序列：");
    BroadFirstSearch(g1,Visit);
    printf("\n");
}
           

最小生成树

如果无向连通图是一个带权图，那么它的所有生成树中必有一棵边的权值总和为最小的生成树，称这棵生成树为最小代价生成树，简称最小生成树。

普里姆算法

Prim.h

typedef struct 
{
    VerT vertex;
    int weight;
} MinSpanTree;

//用普里姆算法建立带权图G的最小生成树closeVertex
void Prim(AdjMGraph G,MinSpanTree closeVertex[])
{
    VerT x;
    int n = G.Vertices.size,minCost;
    int * lowCost = (int*)malloc(sizeof(int)*n);
    int i,j,k;

    for(i = ;i < n; i++)               //初始化
        lowCost[i] = G.edge[][i];

    //从结点0出发构造最小生成树
    ListGet(G.Vertices,,&x);           //取结点0
    closeVertex[].vertex = x;          //保存结点0
    lowCost[] = -;                    //标记结点0

    for(i = ;i < n; i++)
    {
        //寻找当前最小权值的边所对应的弧头结点k
        minCost = MaxWeight;        //MaxWeight为定义的最大权值
        for(j = ;j < n; j++)
        {
            if(lowCost[j] < minCost && lowCost[j] > )
            {
                minCost = lowCost[j];
                k = j;
            }
        }

        ListGet(G.Vertices,k,&x);       //取弧头结点k
        closeVertex[i].vertex = x;      //保存弧头结点k
        closeVertex[i].weight = minCost;    //保存相应的权值
        lowCost[k] = -;                //标记结点k

        //根据加入集合U的结点k修改lowCost中的数值
        for(j = ;j < n; j++)
        {
            if(G.edge[k][j] < lowCost[j])
                lowCost[j] = G.edge[k][j];
        }
    }
}
           

main.c

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

typedef char DataType;
typedef char VerT;
#define MaxSize 100
#define MaxVertices 10
#define MaxWeight 10000
#define N 7

#include "AdjMGraph.h"
#include "AdjMGraphCreate.h"
#include "Prim.h"

void main(void)
{
    AdjMGraph g;
    DataType a[] = {'A','B','C','D','E','F','G'};
    RowColWeight rcw[] = {
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
    };

    int n = ,e = ,i;
    MinSpanTree closeVertex[];

    CreatGraph(&g,a,n,rcw,e);
    Prim(g,closeVertex);

    //输出prim函数得到的最小生成树的结点序列和权值序列
    printf("初始结点 = %c\n",closeVertex[].vertex);
    for(i = ;i < n; i++)
        printf("结点 = %c 边的权值 = %d\n",closeVertex[i].vertex,closeVertex[i].weight);
}
/*
初始结点 = A
结点 = B 边的权值 = 50
结点 = E 边的权值 = 40
结点 = D 边的权值 = 50
结点 = F 边的权值 = 30
结点 = G 边的权值 = 42
结点 = C 边的权值 = 45
Press any key to continue
*/
           

最短路径

在一个图中，若从一个结点到另一个结点存在着路径，定义路径长度为一条路径上所经过的边的数目。图中从一个结点到另一个结点可能存在着多条路径，则路径长度最短的那条称作最短路径，其长度称作最短路径长度或最短距离。

狄克斯特拉算法

Dijkstra.h

/*
函数共有四个参数，其中两个为输入参数，分别为带权图G和源点序号v0;另外两个为输出参数，
分别为distance[]和path[]。distance[]用来存放得到的从源点v0到其余各结点的最短距离数值，
path[]用来存放得到的从源点v0到其余各结点的最短路径上到达目标结点的前一结点下标
  */
void Dijkstra(AdjMGraph G,int v0,int distance[],int path[])
{
    int n = G.Vertices.size;
    int * s = (int*)malloc(sizeof(int)*n);
    int minDis,i,j,u;
    //初始化
    for(i = ;i < n; i++)
    {
        distance[i] = G.edge[v0][i];
        s[i] = ;
        if(i != v0 && distance[i] < MaxWeight) path[i] = v0;
        else
            path[i] = -;
    }

    s[v0] = ;  //标记结点v0已从集合T加入到集合S中
    //在当前还未找到最短 路径的结点集中选取具有最短距离的结点u
    for(i = ;i < n; i++)
    {
        minDis = MaxWeight;
        for(j = ;j < n; j++)
            if(s[j] ==  && distance[j] < minDis)
            {
                u = j;
                minDis = distance[j];
            }

        //当已不再存在路径时算法结束；此语句对非连通图是必须的
        if(minDis == MaxWeight) return ;
        s[u] = ;//标记结点u已从集合T加入到集合S中
        for(j = ;j < n; j++)
            if(s[j] ==  && G.edge[j][j] < MaxWeight && distance[u] + G.edge[u][j] < distance[j])
            {
                //结点v0经结点u到其他结点的最短距离和最短路径
                distance[j] = distance[u] + G.edge[u][j];
                path[j] = u;
            }
    }
}
           

main.c

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

typedef char DataType;
#define MaxSize 100
#define MaxVertices 10
#define MaxWeight 10000

#include "AdjMGraph.h"
#include "AdjMGraphCreate.h"
#include "Dijkstra.h"

void main(void)
{
    AdjMGraph g;
    char a[] = {
        'A','B','C','D','E','F'
    };

    RowColWeight rcw[] = {
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
        {,,},
    };

    int i,n = ,e = ;
    int distance[],path[];

    CreatGraph(&g,a,n,rcw,e);

    Dijkstra(g,,distance,path);

    printf("从结点%c到其他各结点的最短距离为：\n",g.Vertices.list[]);
    for(i = ;i < n; i++)
        printf("到结点%c的最短距离为：%d\n",g.Vertices.list[i],distance[i]);
    printf("从结点%c到其他各结点最短路径的前一结点为：\n",g.Vertices.list[]);
    for(i = ;i < n; i++)
        if(path[i] != -)
            printf("到结点%c的前一结点为：%c\n",g.Vertices.list[i],g.Vertices.list[path[i]]);
}

/*
从结点A到其他各结点的最短距离为：
到结点A的最短距离为：0
到结点B的最短距离为：20
到结点C的最短距离为：5
到结点D的最短距离为：22
到结点E的最短距离为：28
到结点F的最短距离为：12
从结点A到其他各结点最短路径的前一结点为：
到结点B的前一结点为：C
到结点C的前一结点为：A
到结点D的前一结点为：F
到结点E的前一结点为：B
到结点F的前一结点为：C
Press any key to continue
*/
           

弗洛伊德算法

void Floyd(int cost[][N],int n,int weight[][N],int path[][N])
{
    int i,j,k;
    //初始化
    for(i = 0;i < n; i++)
        for(j = 0;j < n; j++)
        {
            weight[i][j] = cost[i][j];
            path[i][j] = -1;
        }
    //n次递推
    for(k = 0;k < n; k++)
    {
        for(i = 0;i < n; i++)
        {
            for(j = 0;j < n; j++)
            {
                if(weight[i][j] > weight[i][k] + weight[k][j])
                {
                    //得到新的最短路径长度数值
                    weight[i][j] = weight[i][k] + weight[k][j];
                    //得到该最短路径经过的结点序号
                    path[i][j] = k;
                }
            }
        }
    }
}