图的存储 ( 十字链表 )

   直接进入正题,存图最简单易懂的就是邻接矩阵。然后就是邻接表。这个不懂，可以先看看数据结构书。默认你会邻接表。讲十字链表还是得先说说是什么：

    十字链表（Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。

比如就以这幅图为例：       

------------------------------------------------------------------------------------------------------------------

下面是邻接矩阵表示方法：

邻接表的优化就是让他跳着遍历，变一下就是邻接表了：

然而，十字邻接表就是再添加逆向邻接表，如图：

邻接表建图一般是这样：

邻接表就是只有横向关系的一幅图；十字链表就是

 这样的。关系。

十字链表和邻接表优点: 邻接表对于某一点遍历它能够到达的所有点的边比较方便与快;但是遍历某一些到他的边就不太方便,所以就有了十字链表

下面是自己用链式写的,正确性不确定,有错误还望大牛们发现提出来,代码仅供参考。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdlib.h>

using namespace std;
const int MAXSIZE=1010;

struct EdgeNode  //边
{
    int s,t;
    int value;
    EdgeNode *Forward,*Reverse;
};

struct VertexNode  //点
{
    EdgeNode *Forward,*Reverse,*ForwardTail,*ReverseTail;
};
struct Graph
{
    EdgeNode Edge[MAXSIZE];
    VertexNode Vertex[MAXSIZE];
    int num_edge,num_vertex,ntotal;
};
void init(Graph& G)
{
    G.num_edge=G.num_vertex=G.ntotal=0;
}
void init_edge(EdgeNode& E)
{
    E.Forward=E.Reverse=NULL;
    E.value=0;
}
void addedge(int s,int t,int value,Graph& G)
{
    init_edge(G.Edge[G.ntotal]);
    G.Edge[G.ntotal].s=s,G.Edge[G.ntotal].t=t,G.Edge[G.ntotal].value=value;
    if(G.Vertex[s].Forward==NULL)
    {
        G.Vertex[s].Forward=&G.Edge[G.ntotal];
        G.Vertex[s].ForwardTail=&G.Edge[G.ntotal];
    }
    else
    {
        G.Vertex[s].ForwardTail->Forward=&G.Edge[G.ntotal];
        G.Vertex[s].ForwardTail=&G.Edge[G.ntotal];
    }

    if(G.Vertex[t].Reverse==NULL)
    {
        G.Vertex[t].Reverse=&G.Edge[G.ntotal];
        G.Vertex[t].ReverseTail=&G.Edge[G.ntotal];
    }
    else
    {
        G.Vertex[t].ReverseTail->Reverse=&G.Edge[G.ntotal];
        G.Vertex[t].ReverseTail=&G.Edge[G.ntotal];
    }
    G.ntotal++;
}
void CreatGraph(Graph& G)
{
    scanf("%d%d",&G.num_edge,&G.num_vertex);// 请输入边数,点数
    for(int i=0; i<=G.num_vertex; i++)
    {
        G.Vertex[i].Forward=G.Vertex[i].ForwardTail=NULL;
        G.Vertex[i].Reverse=G.Vertex[i].ReverseTail=NULL;
    }
    for(int i=0; i<G.num_edge; i++)
    {
        int s,t,val;
        scanf("%d%d%d",&s,&t,&val);
        addedge(s,t,val,G);
    }
}
void visit(Graph& G)
{
    for(int i=0;i<G.num_vertex;i++)
    {
        EdgeNode *temp=G.Vertex[i].Forward;
        while(temp!=NULL)
        {
            printf("%d to %d is %d
",temp->s,temp->t,temp->value);
            temp=temp->Forward;
        }
        printf("
");
    }
    printf("
逆向遍历
");
    for(int i=0;i<G.num_vertex;i++)
    {
        EdgeNode *temp=G.Vertex[i].Reverse;
        while(temp!=NULL)
        {
            printf("%d to %d is %d
",temp->s,temp->t,temp->value);
            temp=temp->Reverse;
        }
        printf("
");
    }
}
int main()
{

    Graph G;
    init(G);
    CreatGraph(G);
    visit(G);
    return 0;
}