代码钢琴家 阅读(120) 评论(0)

邻接矩阵存储法

回顾:图G = <V,E>

邻接矩阵存储法的主要思想如下

1、用一个数组存储所有顶点,代表集合V中的元素

2、用一个二维数组存边,代表集合E中的元素

 

 

无向图的邻接矩阵存储

 我们通过具体的例子来讲解,以下图为例

 

 

                          

 

 

1、边使用矩阵来构建模型,这使得每一个顶点和其它顶点之间都有边的有无 的 表示的机会。若有边,则他们交点 为1 ,否则为0。

2、无向图的边的矩阵一定是一个对称矩阵,因为无向图只关心边是否存在,而不关心方向,V0和V1有边,那么V1和V0也有边。

3、因为这里不研究有圈图,所以主对角线都是0

 先牛刀小试 一下,构建数据类型,写出API。     :)

 

代码都很好理解,唯一 一个技巧就是create函数中的二重for循环,利用了选择排序中的思想,避免了边信息的重复填充,也就是例如,输入V0和V1边的关系后,就不必输入V1和V0的关系了。

在上一篇文章中提到:

  顶点数为n的图,最多有条边,这里的二重for循环的时间复杂度恰好也是O() = O(n2)

这个技巧后面都会用到。

 for (int j = 0; j <MAX_VERTEX; ++j)   //填充边关系 
    {
        for (int i = j+1; i < MAX_VERTEX; ++i)
        {
            
            printf("若元素%c和%c有边,则输入1,否则输入0\t",pGraph->vertexArr[j],pGraph->vertexArr[i]);
            
            scanf("%d",&( pGraph->edgeArr[j][i]));
            pGraph->edgeArr[i][j] = pGraph->edgeArr[j][i];     //对称 
        }
    }

 

 

代码:

#include<stdio.h>


#define MAX_VERTEX  4

typedef char DataType;                 //图中元素的目标数据类型 


typedef struct    
{                  
    DataType vertexArr[MAX_VERTEX];        //顶点元素数组 

    int edgeArr[MAX_VERTEX][MAX_VERTEX];   //边矩阵二维数组 
    

}ArrayGraph;

void ArrayGraph_init(ArrayGraph *pGraph);
void ArrayGraph_create(ArrayGraph *pGraph);
void ArrayGraph_show(ArrayGraph *pGraph);



int main()
{
    ArrayGraph g;
    ArrayGraph_init(&g);       //初始化图 
    ArrayGraph_create(&g);     //创建图 
    ArrayGraph_show(&g);       //打印图 



    return 0;
}



//初始化为一个无圈图 ,也就是边矩阵中,主对角线元素都是0 
void ArrayGraph_init(ArrayGraph *pGraph)
{
    
    for (int i = 0; i < MAX_VERTEX; i++)

        pGraph->edgeArr[i][i] = 0;

}


void ArrayGraph_create(ArrayGraph *pGraph)
{
    

    for (int i = 0; i < MAX_VERTEX; ++i)    //填充顶点数组,也就是输入顶点元素 
    {
        printf("输入第%d个顶点值\n",i+1);
        
        scanf(" %c",&(pGraph->vertexArr[i])); 

    }

    for (int j = 0; j <MAX_VERTEX; ++j)   //填充边关系 
    {
        for (int i = j+1; i < MAX_VERTEX; ++i)
        {
            
            printf("若元素%c和%c有边,则输入1,否则输入0\t",pGraph->vertexArr[j],pGraph->vertexArr[i]);
            
            scanf("%d",&( pGraph->edgeArr[j][i]));
            pGraph->edgeArr[i][j] = pGraph->edgeArr[j][i];     //对称 
        }
    }



}


void ArrayGraph_show(ArrayGraph *pGraph)
{


    printf("\n\n顶点元素如下\n");
    for (int i = 0; i < MAX_VERTEX; ++i)
    {
        
        printf("%-5c", pGraph->vertexArr[i]);
    }
    printf("\n\n");


    
    puts("边矩阵如下\n\n"); 
    printf("%-2c",' ');
    for(int i=0;i<MAX_VERTEX;++i)
      printf("%-5c",pGraph->vertexArr[i]);
    putchar('\n');  
    
    
    
    for (int j = 0; j <MAX_VERTEX; ++j)
    {
        printf("%-2c",pGraph->vertexArr[j]);
        for (int i = 0; i < MAX_VERTEX; ++i)
        {
            printf("%-5d",pGraph->edgeArr[i][j]);

        }
        putchar('\n');
    }
    
    printf("\n\n");
}
View Code

 

 

有向图的邻接矩阵存储

 

 

使用邻接矩阵呢存储时,有向图和无向图的区别在与 边和弧矩阵的差别。因为弧是有方向的,所以我们 以对角线为界,将矩阵划分为2个区域:

左下区域表示出弧标记区域,坐上区域代表入弧标记区域(当然也可以交换,看个人习惯)

如  若代表弧的矩阵为arcArr

   arcArr[V2][V3] 为1,且在出弧标记区域,则说明 V3<------V2

   arcArr[V3][V2] 为0,且在入弧标记区域,则说明 V2---\--->V3

 

代码:

#include<stdio.h>

#define  MAX_VERTEX  4

typedef char DataType;                 //图中元素的目标数据类型 


typedef struct    
{                  
    DataType vertexArr[MAX_VERTEX];        //顶点元素数组 

    int arcArr[MAX_VERTEX][MAX_VERTEX];   //弧矩阵二维数组 
    

}ArrayGraph;

void ArrayGraph_init(ArrayGraph *pGraph);
void ArrayGraph_create(ArrayGraph *pGraph);
void ArrayGraph_show(ArrayGraph *pGraph);



int main()
{
    ArrayGraph g;
    ArrayGraph_init(&g);
    ArrayGraph_create(&g);
    ArrayGraph_show(&g);



    return 0;
}



//初始化为一个无圈图 ,也就是弧矩阵中,主对角线元素都是0 
void ArrayGraph_init(ArrayGraph *pGraph)
{
    
    for (int i = 0; i < MAX_VERTEX; i++)

        pGraph->arcArr[i][i] = 0;

}


void ArrayGraph_create(ArrayGraph *pGraph)
{
    

    for (int i = 0; i < MAX_VERTEX; ++i)  //填充顶点数组
    {
        printf("输入第%d个顶点值\n",i+1);
        
        scanf(" %c",&(pGraph->vertexArr[i])); 

    }

    for (int j = 0; j <MAX_VERTEX; ++j)   //填充边关系 
    {
        for (int i = j+1; i < MAX_VERTEX; ++i)
        {
            
            printf("若元素%c有指向%c的弧,则输入1,否则输入0\t",pGraph->vertexArr[i],pGraph->vertexArr[j]);
            scanf("%d",&( pGraph->arcArr[j][i]));
            
            printf("若元素%c有指向%c的弧,则输入1,否则输入0\t",pGraph->vertexArr[j],pGraph->vertexArr[i]);
            scanf("%d",&( pGraph->arcArr[i][j]));
        }
    }






}


void ArrayGraph_show(ArrayGraph *pGraph)
{


    printf("\n\n顶点元素如下\n");
    for (int i = 0; i < MAX_VERTEX; ++i)
    {
        
        printf("%-5c", pGraph->vertexArr[i]);
    }
    printf("\n\n");


    
    puts("弧矩阵如下\n\n"); 
    printf("%-2c",' ');
    for(int i=0;i<MAX_VERTEX;++i)
      printf("%-5c",pGraph->vertexArr[i]);
    putchar('\n');  
    
    
    
    for (int j = 0; j <MAX_VERTEX; ++j)
    {
        printf("%-2c",pGraph->vertexArr[j]);
        for (int i = 0; i < MAX_VERTEX; ++i)
        {
            printf("%-5d",pGraph->arcArr[i][j]);

        }
        putchar('\n');
    }
    putchar('\n');  
}
View Code

 

 

无向网的邻接矩阵存储

无向网的边是有权值的,这个值可以是任何一个合法的值,什么样的值是合法的呢?这需要根据图的具体用途来定。所以,我们不能用简单的0,1来代表边。

如果2个顶点无关联,他们也不能用0表示,因为0也可能是一个合法的wieght值,所以,我们来要根据图的用途定义一个weight值的无效值,也就是wight不可能的取值。

同样用一个栗子。

 

V0 V1之间的权值为12

V0 V2之间的权值为1

V0 V3之间的权值为5

V2 V3之间的权值为7

其他无关联,weight值为规定的 invalid weight value。无效值不一定要用相应类型的最大值表示,只要在此问题背景下weight永远不可能取得就可以用来做invalid weight value。

 

       

 

 

 代码:

#include<stdio.h>

#define MAX_VERTEX 4     

#define INVALID_WEIGHT -1

typedef char DataType;     //存储的元素类型 
typedef int WeightType;    //权值的类型 

typedef struct
{
    DataType vertexArr[MAX_VERTEX];             //存储顶点的数组 

    WeightType edgeArr[MAX_VERTEX][MAX_VERTEX]; //存储边的二维数组 

}UArrayNet;     //数据结构类型:无向网 


void UArrayNet_init(UArrayNet*pGraph);
void UArrayNet_create(UArrayNet*pGraph);
void UArrayNet_show(UArrayNet *pGraph);

int main()
{
    UArrayNet net;
    UArrayNet_init(&net);

    UArrayNet_create(&net);
    UArrayNet_show(&net);



    return 0;
}

void UArrayNet_init(UArrayNet*pGraph)
{
    for (int i = 0; i < MAX_VERTEX; ++i)
    {
        pGraph->edgeArr[i][i] = INVALID_WEIGHT;
    }


}


void UArrayNet_create(UArrayNet*pGraph)
{
    for (int i = 0; i < MAX_VERTEX; ++i)  //填充顶点数组
    {
        printf("输入第%d个顶点值\n", i + 1);

        scanf(" %c", &(pGraph->vertexArr[i]));

    }

    for (int j = 0; j <MAX_VERTEX; ++j)   //填充边关系 
    {
        for (int i = j + 1; i < MAX_VERTEX; ++i)
        {

            printf("若元素%c和%c有边,则输入权值,否则输入无效值%d\t", pGraph->vertexArr[j], pGraph->vertexArr[i], INVALID_WEIGHT);

            scanf("%d", &(pGraph->edgeArr[j][i]));
            pGraph->edgeArr[i][j] = pGraph->edgeArr[j][i];     //对称 
        }
    }


}

void UArrayNet_show(UArrayNet *pGraph)
{


    printf("\n\n顶点元素如下\n");
    for (int i = 0; i < MAX_VERTEX; ++i)
    {

        printf("%-5c", pGraph->vertexArr[i]);
    }
    printf("\n\n");



    puts("边矩阵如下");
    printf("%-2c", ' ');
    for (int i = 0; i<MAX_VERTEX; ++i)
        printf("%-5c", pGraph->vertexArr[i]);
    putchar('\n');



    for (int j = 0; j <MAX_VERTEX; ++j)
    {
        printf("%-2c", pGraph->vertexArr[j]);
        for (int i = 0; i < MAX_VERTEX; ++i)
        {
            if(pGraph->edgeArr[i][j]==INVALID_WEIGHT)
            {
                printf("%-5c", '#');
                
            } 
            else
                printf("%-5d", pGraph->edgeArr[i][j]);

        }
        putchar('\n');
    }
}
View Code

 

 

有向网的邻接矩阵存储

有向网和有向图的原理是一样,这里不再扩充。

 

 

 

 

邻接表储存实现

 

 

邻接矩阵存储很好理解,但是,有时候太浪费空间了,特别是对于顶点数多,但是关联关系少的图

举个极端的栗子。

下图中,5个顶点都是孤立的,然而为了存储边的信息,要分配一个5X5的矩阵。本来一条边都没有,没必要用存储空间来存储边,但还要分配额外的空间。

           

 

 

 

无向图与邻接表

用邻接表则可以避免这种浪费。邻接表用动态表结构存储边,更加灵活:有一个边就分配一个空间去存储,没有就不分配。

我们仍然用邻接矩阵中那个图的例子来说明邻接表的构建思想。

邻接表只需要一个数组,但是这个数组有点复杂,需要解剖一下。如下图。

 

 

 

可以发现,用邻接表存储时,图中的每一个节点 不仅要存储本顶点的数据data,好要存储一个表,这个表存储了此顶点的所有临接点的索引。2点确定一线,那么就能存储此节点相关的所有的边了。

 

 

代码:

 

注:代码中,我并没有手动编写链表,而是用了C++标准库中的vector模板,它是一个线性表,具体说是在堆中的动态数组。push_back()就是向表中添加新的元素。

这样做的目的是为了让代码更简洁,思路更清晰。我不想把书抄一遍,这样我写这篇随便也就失去了意义。

而且,书上的很多例子中,将多种数据结构的构建混杂在一起,根本不知道降低耦合度,如果我以前学过了链表,而且也自己实现了,为什么不直接拿来用呢?吐槽完毕。

 

#include<stdio.h>
#include<vector>

#define MAX_VERTEX 4
using std::vector;        //使用C++标准库中的vector来作为list,它实质就是一个顺序表 


typedef char DataType;

typedef struct node
{
    DataType data;            //顶点数据 
    vector<int> indexList;    //存储顶点邻接点索引的 表 

}Node;


typedef Node* UListGraph;


/********************************/
void UListGraph_init(UListGraph*pGraph);
void UListGraph_create(UListGraph  graph);
void UListGraph_show(UListGraph graph);
void UListGraph_destroy(UListGraph*pGraph);

int main(void)
{

    UListGraph g;

    UListGraph_init(&g);
    UListGraph_create(g);
    UListGraph_show(g);

    UListGraph_destroy(&g);



    return 0;
}


void UListGraph_init(UListGraph*pGraph)
{

    (*pGraph) = new Node[MAX_VERTEX];


}


void UListGraph_create(UListGraph  graph)
{

    
    
    for (int i = 0; i < MAX_VERTEX; ++i)  //填充顶点数组
    {
        printf("输入第%d个顶点值\n",i+1);
        
        scanf(" %c",  &(graph[i].data)); 

    }

    for(int i=0;i<MAX_VERTEX;++i)
        for(int j=i+1;j<MAX_VERTEX;++j)
        {
            printf("如果元素%c和%c之间有边,请输入1,否则输入0",graph[i].data,graph[j].data);

            int opt;
            scanf("%d",&opt);

            if(opt==1)
            {
                graph[i].indexList.push_back(j);
                graph[j].indexList.push_back(i);
            }


        }



}



void UListGraph_show(UListGraph graph)
{
    
    printf("顶点元素如下:\n\n"); 
    for(int i=0;i<MAX_VERTEX;i++)
    {
        printf("%c\t",graph[i].data);
    }
    printf("\n\n");



    for(int i=0;i<MAX_VERTEX;i++)
    {
        printf("元素%c的邻接点 :",graph[i].data);

        Node tnode = graph[i];

        for(int k=0;k<tnode.indexList.size();++k)
        {
            printf("%c\t",graph[tnode.indexList[k]].data);
        }

        putchar('\n');
    }


}


void UListGraph_destroy(UListGraph*pGraph)
{
    delete (*pGraph);
    *pGraph = NULL;        
       

}
View Code

 

 

 

 

无向网的邻接表

无向网的邻接表,因为网是带权值的,所以,还要为边附加权值信息。

确切的说,就是IndexList表 中存储的是一个个的结构体,这个结构体不仅保存邻接点的索引,还用一个成员保存了本顶点和他的邻接点之间边的权值。

 

typedef struct edge
{
    int otherVerTex;          //本顶点和索引为otherVertex的顶点形成一条边
    WeightType weight;        //边的权值


}Edge


//使用方法如下:用V0和V1来举例

// Edge edge = {1 , 12};
// V0.IndexList.push_back(edge );
//

 

 

 

 

有向图和十字链表

 

 邻接表对于无向图来说很适用,但是对于有向图来说就不适用了,因为邻接表中,每一个节点的IndexList只能存储一种状态的弧,出弧或者入弧(逆邻接表),那怎么将一个顶点的出入弧都存储起来呢?

那就是将邻接表和逆邻接表都用起来,也就是一个节点需要存储:①data,②inArcList,入弧记录表,③outArcList,出弧记录表

 

 

 

 

可以看出,十字表比邻接表更复杂,因为十字表要存储更多的数据。

 

 代码:

 

#include<stdio.h>
#include<vector>

using std::vector;

#define MAX_VERTEX 4 

typedef char DataType;


typedef struct arc{ 

    int headVertex;         //此条弧的头尾结点的index
    int tailVertex;         //此条弧的头尾结点的index

    //WeightType weight;    //此弧的附加信息,比如权重,这里是有向图,不是网,所以不需要weight

}Arc;

typedef struct node{

    DataType data;   //顶点数据域

    vector<Arc> outArc;     //此顶点的所有 出度 弧 表
    vector<Arc> inArc;      //此顶点的所有 入度 弧 表 

}Node;


typedef Node* Graph;

void Graph_init(Graph* pG);
void Graph_create(Graph g);
void Graph_show(Graph g);
void Graph_destroy(Graph*pg);


int main(void)
{


    Graph g;

    Graph_init(&g);
    Graph_create(g);
    Graph_show(g);

    return 0;
}



void Graph_init(Graph* pG)
{

    (*pG) = new Node[MAX_VERTEX];
    if(*pG == NULL)
    {
        exit(-1);
    }

}

void Graph_create(Graph g)
{

    int opt;
    
    for (int i = 0; i < MAX_VERTEX; ++i)  //填充顶点数组
    {
        printf("输入第%d个顶点值\n",i+1);
        
        scanf(" %c",  &(g[i].data)); 

    }

    for(int j=0;j<MAX_VERTEX;++j)
        for(int i=j+1;i<MAX_VERTEX;++i)
        {


            printf("若元素%c有指向%c的弧,则输入1,否则输入0\t",g[j].data,g[i].data);
           
            scanf("%d",&opt);

            if(opt==1)
            {
                Arc* parc = new Arc;
                parc->headVertex = i;
                parc->tailVertex = j;
                
                g[j].outArc.push_back(*parc);
                g[i].inArc.push_back(*parc);

            }

            
            printf("若元素%c有指向%c的弧,则输入1,否则输入0\t",g[i].data,g[j].data);
           
            scanf("%d",&opt);

            if(opt==1)
            {
                
                Arc* parc = new Arc;
                parc->headVertex = j;
                parc->tailVertex = i;

                g[i].outArc.push_back(*parc);
                g[j].inArc.push_back(*parc);
                     

            }

        }

}

void Graph_show(Graph g)
{


    for (int j = 0; j <MAX_VERTEX; ++j)
    {
        printf("顶点数据%c\n",g[j].data);
       
        printf("发射:");

        
        for(int i=0;i<g[j].outArc.size();++i)
        {
            printf("%c\t",g[g[j].outArc[i].headVertex].data);
        }


        putchar('\n');
        printf("接收:");

        for(int i=0;i<g[j].inArc.size();++i)
        {
            printf("%c\t",g[g[j].inArc[i].tailVertex].data);
        }

        printf("\n\n");

    }
    


}



void Graph_destroy(Graph*pg)
{
    //once you use new or malloc in your C/C++ project,you must remember
    //to delete or free the memory you allocated
    //I have no time to complete this code
    //you can try yourself
    //:)
}
View Code

 

 

邻接多重表

 没时间了~以后补!

 

 

 

下一篇:图的遍历