图论相关——邻接多重表与十字链表

数据结构

邻接多重表

什么是邻接多重表？图的数据结构表示有很多，邻接矩阵、邻接表、还有今天要将的邻接多重表和十字链表，都是很经典的图的数据结构表示。一般来说，在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但是如果邻接表存储的是无向图类型的话，对于边的操作很麻烦，需要对两条链表进行判断操作，而邻接多重表就是为了解决邻接表存储无向图带来的操作麻烦而诞生的，这里引用下c语言中文网的段落

邻接多重表(Adjacency Multilist)主要用于存储无向图。因为，如果用邻接表存储无向图，每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中，这给图的某些操作带来不便。例如，对已访问过的边做标记，或者要删除图中某一条边等，都需要找到表示同一条边的两个结点
深度截图_选择区域_20171206140846.png

邻接多重表中，顶点集合的数据结构是一个结构体数组，这个结构体有两个信息，一个是该节点的名称，还有一个是第一条依附于该节点的边的指针域；

1
2
3
4
struct VexBox {
    VertexType data;
    EBox *firstedge;
}

接下来是边的结构信息：边的结构也是一个结构体，包含了两个顶点在顶点集合的位置（数组下表），这两个顶点我们假设为ivex和jvex，那么会有两个对应的边类型的指针域，分别是ifirstedge和jfirstedge，分别是指向下一条依附于顶点ivex的边和下一条依附于顶点jvex的边，还有一个边的info指针域，用于连接边的信息（像权值信息这些）；

1
2
3
4
5
struct EBox {
    int ivex, jvex;
    EBox *ifirstedge, *jfirstedge;
    InfoType *info
}

最后，我们建一个结构体用于管理这个邻接多重表，int vexnum代表了邻接多重表中顶点的个数，edgenum代表了邻接多重表中边的条数；

1
2
3
4
struct Graph {
    int vexnum, edgenum;
    struct VexBox vertices[MAX_VEX_NUMS];
}

最后，我们看看邻接多重表的建图代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int Locate (VertexType v, Graph G) {
    int i;
    for(i =0; i < G.vexnum; i ++) {
    if(strcmp(v, G.vertices[i].data)==0)
        return i;
    }
    return-1;
}

void CreatGraph(Graph *G) {
    int i, j, k, l;
    char s[MAX_INFO];
    VertexType va, vb;
    EBox *p;
    cin >> G.vexnum >> G.edgenum;
    for(i =0; i < G.vexnum; i ++) {
        cin >> G.vertices[i].data;
        G.vertices[i].firstedge = NULL;
    }
    for(k =0; k < G.edgenum; k ++){
        cin >> va >> vb;
        i = Locate(va, G);
        j = Locate(vb, G);
        p = new EBox;
        p -> ivex = i;
        p -> jvex = j;
        p -> info = NULL;
        p -> ifirstedge = G.vertices[i].firstedge;
        G.vertices[i].firstedge = p;
        p -> jfirstedge = G.vertices[j].firstedge;
        G.vertices[j].firstedge = p;
    }
}

十字链表

深度截图_选择区域_20171207234318

图的表示方式有邻接表，当然也有逆连接表，十字链表就是邻接表和逆连接的结合体，因此，用十字链表进行表示有向图，可以很轻松的找到一条弧的弧头节点和一条弧的弧尾节点。

相比于邻接多重表，十字链表的顶点集合数据结构定义与弧的结构定义有些许不同，对于十字链表的顶点结合数据结构定义如下：

顶点的定义：

1
2
3
4
struct ArcNode {
    VertexType data;
    struct ArcBox *firstin, *firstout;
}

十字链表的顶点节点有两个指针域，一个是第一条以该顶点的入度的弧——firstin，一个是第一条以该顶点为出度的弧——firstout；

接着是弧的结构定义：

1
2
3
4
struct  ArcBox {
    int ivex，jvex；
    struct ArcBox  *headbox，*tailbox；
}

有向图的弧结构定义和邻接多重表很是类似，首先都有两个int类型的变量用于存储弧头和弧尾在顶点集合的位置，然后是两个指针域，一个是指向下一条与该条弧具有相同弧尾的弧——tailbox，一个是指向下一条具有相同弧头的弧——headbox。

定义一个结构体用于管理十字链表：

1
2
3
4
struct Graph {
    int vexnum, arcnum;
    struct ArcNode vertices[MAX_VER_NUMS];
}

十字链表的建图代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void CreateDG(Graph *G) {
    int i, j, k;
    int IncInfo;
    char str[MAX_Info];
    ArcBox *p;
    VertexType v1, v2;
    scanf("%d,%d,%d",&G -> vexnum, &G -> arcnum, &IncInfo);
    for(i =0; i < G -> vexnum;++i) {
        scanf("%s",&G -> xlist[i].data);
        G -> vertices[i].firstin = NULL;
        G -> vertices[i].firstout = NULL;
    }
    for(k =0; k < G -> arcnum;++k) {
        scanf("%s%s",&v1,&v2);
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        p = (ArcBox *)malloc(sizeof(ArcBox));
        p->tailvex = i;
        p->headvex = j;
        p->hlink = G -> vertices[j].firstin;
        p->tlink = G- > vertices[i].firstout;
        G -> vertices[j].firstin = G -> vertices[i].firstout = p;
        if(IncInfo) {
            scanf("%s", str);
            p->info = (InfoType *)malloc((strlen(str) + 1) * sizeof(InfoType));
            strcpy(p->info, str);
        }
        else
            p->info = NULL;
    }
    return true;
}

（以上图片均取自c语言中文网 http://c.biancheng.net/cpp/）