/*依赖队列达成图的拓扑排序C程序*/
#include<stdlib.h>
#define maxvertexnum 20/*概念最多的极点数*/
#define null 0
#define maxqueue 20
#define m 10  /*概念最多入度数*/

作业:用邻接表完结图的深度与广度优先遍历。(做出来的遍历结果体系非凡State of Qatar

豆蔻年华、基本术语

/*图的邻接表的边表结点*/
typedef struct node
{
 int adjvex;/*存放邻接点序号*/
 
 /*若要表示边上的权,可加多贰个数据域*/ 
    struct node *next; 
}edgenode;

前后相继如下:

 

/*图的邻接表表示的极点表结点*/
typedef struct vnode
{
 int vertex;/*极点数据域*/ 
    edgenode *firstedge;/*边表头指针*/ 
}vertexnode; 
/*用向量定义图的邻接表表示的极点表*/
typedef vertexnode adjlist[maxvertexnum]; 

/*邻接表表示的图的深浅优先找出和广度优先找寻程序*/
#include <stdio.h>
#define maxvertexnum 100
#define queuesize 100
#define null 0

图:由夏朝、非空点集和边集结组成,简写成G(V,E卡塔尔国;

/*定义图的邻接表*/ 
typedef struct
{
    adjlist adjlist;/*邻接表*/
    int n;/*顶点数*/ 
    int e;/*边数*/ 
}algraph;

typedef struct
{
 int front,rear,count,data[queuesize];
}cirqueue; 
typedef int vertextype; 

Vertex:图中的极点;

int queue[maxqueue];/*队列的数组注解*/
int front=-1;/*队头*/
int rear=-1;/*队尾*/
 

/*图的邻接表的边结点定义*/
typedef struct node
{
 int adjvex; 
    struct node *next; 
}edgenode;

 

/*创立有向图g的邻接表*/
void createalgraph(algraph *g)
{
 int i,j,k,r;
    edgenode *s;
    printf(“ncreat_digraph:n”);
    printf(“input n,e.n”);
    scanf(“%d,%d”,&g->n,&g->e);/*输入图g的极点数和边数*/
    printf(“input nodes(after input a node then enter ‘Enter’):n”);
    for(i=1;i<=g->n;i++)  /*布局二个只含n个极点,边数为0的图*/
    {
     scanf(“%d”,&(g->adjlist.vertex)); /读入顶点音讯*/
        g->adjlist.firstedge=null;  
/
将极点结点的firstedge域置为空*/
    }
    for(k=1;k<=g->e;k++) /*树立边表*/
    {
     printf(“input i,j(1~n):n”);
        scanf(“%d,%d”,&i,&j);  /*读入边(vi,vj)的尖峰对序号*/
        s=(edgenode *)malloc(sizeof(edgenode));
        s->adjvex=j;/*将序号j归入边结点*s的邻接点序号adjvex域*/**

/*图的邻接表表示的顶峰结点定义*/
typedef struct vnode
{
 vertextype vertex; 
    edgenode *firstedge; 
}vertexnode; 

无向图:图中每条边都未曾动向;

        s->next=g->adjlist.firstedge;
        /
将边结点*s作为第二个邻接点插入到序号为i的终端的边表中*/
        g->adjlist*.firstedge=s;
    }
}**

typedef vertexnode adjlist[maxvertexnum]; 

有向图:图中每条边都有方向;

/*打字与印刷邻接表*/
void print(adjlist g,int n)
{
 edgenode *q;
    int i;
    printf(“nPrint out the linjiebiao of graph:n”);
    for(i=1;i<=n;i++)
    {
        printf(“%d->”,g.vertex);/出口头结点数组的数据*/
        while(q!=null)
        {
         printf(“%d-“,q->adjvex);/*出口边表的数目*/
            q=q->next;
        }
        printf(“n”);
    }
}*

/*定义图的邻接表*/ 
typedef struct
{
 adjlist adjlist;
    int n; 
    int e; 
}algraph;

 

/*图的拓扑排序(队列卡塔尔(قطر‎*/
int toposort(adjlist g,int n)
{
 edgenode *r;
 int i;
 for(i=1;i<=n;i++)
    if(r->indegree==0)
      enqueue(i);
    while((i=dequeue())!=-1)
    {
      printf(”  %d  “,i);
输出入度为零的终极*
      g=r->next;
      while(g!=null)
      {
       i=r->indegree;
       r->indegree
–;
       if(r->indegree*==0)
          enqueue(i);
       g=g->next;
 **

typedef enum
{
 FALSE,TRUE
}boolean;
boolean visited[maxvertexnum]; 

无向边:边是绝非动向的,写为(a,b卡塔尔国

/*树立图g的邻接表表示*/
void createalgraph(algraph *g)
{
 int i,j,k;
    int flag;
    edgenode *s;
    printf(“ncreat:n”);
    printf(“digraph–0n”);
    printf(“undigraph–1n”);
    scanf(“%d”,&flag);
    printf(“input n,en”);
    scanf(“%d,%d”,&g->n,&g->e);
    printf(“input nodes:n”);
    for(i=0;i<g->n;i++)
    {
     scanf(“%d”,&(g->adjlist.vertex));
        g->adjlist
.firstedge=null;
    }
    for(k=0;k<g->e;k++)
    {
     printf(“input i,j(0~n-1):n”);
        scanf(“%d,%d”,&i,&j);
        s=(edgenode *)malloc(sizeof(edgenode));
        s->adjvex=j;
        s->next=g->adjlist.firstedge;
        g->adjlist
.firstedge=s;
        if (flag)
        {
         s=(edgenode *)malloc(sizeof(edgenode));
            s->adjvex=i;
            s->next=g->adjlist[j].firstedge;
            g->adjlist[j].firstedge=s;
        }
   }
}**

有向边:边是有来头的,写为

void dfs(algraph *g,int i)
{
 edgenode *p;
    printf(“nvisit vertex:%d”,g->adjlist.vertex);
    visited
=TRUE;
    p=g->adjlist.firstedge;
    while(p)
    {
     if (!visited[p->adjvex])
        dfs(g,p->adjvex);
        p=p->next;
    }
}**

有向边也改为弧;领头终极称为弧尾,停止极点称为弧头;

/*对以邻接表表示的图g进行深度优先寻觅*/
void dfstraverse(algraph *g)
{
 int i;
    for(i=0;i<g->n;i++)
    visited=FALSE;
    for(i=0;i<g->n;i++)
    if(!visited
)
    dfs(g,i);
    printf(“n”);
}**

 

void bfs(algraph *g,int k)
{
 int i,j;
    cirqueue *q;
    edgenode *p;
    q=(cirqueue *)malloc(sizeof(cirqueue));
    q->rear=q->front=q->count=0;
    printf(“nvisit vertex:%d”,g->adjlist[k].vertex);
    visited[k]=TRUE;
    q->data[q->r

不问可以知道图:一纸空文指向自身的边、不设有两条重复的边的图;

 

无向完全图:每一种终端之间皆有一条边的无向图;

有向完全图:每一个终端之间都有两条互为相反的边的无向图;

 

疏弃图:边相对于极带来讲比超级少的图;

密布图:边比比较多的图;

 

权重:图中的边或许会包蕴叁个权重,为了差别边的长度;

网:带有权重的图;

 

度:与一定极点相连接的边数;

出度、入度:对于有向图的概念,出度表示此极点为起源的边的数额,入度表示此极点为终极的边的多少;

 

环:第五个极点和最终一个极限相符的路子;

粗略环:除去第八个顶点和结尾二个顶峰后尚未再度顶点的环;

 

连通图:大肆三个顶点都互相衔接的图;

极辛辛那提通子图:包含竟也许多的极限(必得是连着的),即找不到其余叁个终端,使得此极点能够接连到此极明斯克通子图的随机三个极限;

连接分量:极奥斯汀通子图的多寡;

强连通图:此为有向图的定义,表示任性三个极点a,b,使得a能够一而再连续到b,b也能连采纳a
的图;

 

生成树:n个极点,n-1条边,并且保证n个极点相互衔接(空中楼阁环);

最小生成树:此生成树的边的权重之和是颇负生成树中幽微的;

 

AOV网:结点表示活动的网;

AOE网:边表示活动的持续时间的网;


二、图的创造存款和储蓄:

 

1、邻接矩阵法:

 //图边数多时,有向图/无向图/有向网/无向网都可用其来存款和储蓄。

 //可是当边数非常少时不切合用此措施,会产生空间浪费

 

图的邻接矩阵存款和储蓄方式是用七个数组来代表图。三个生机勃勃维数组存款和储蓄图中极点音信,一个二维数组(邻接矩阵)存款和储蓄图中的边或弧的消息。

    设图G有n个顶点,则邻接矩阵是四个n*n的方阵,定义为:

    图片 1

    看一个实例,下图左便是二个无向图。

    图片 2

   
从地点能够看出,无向图的边数组是三个对称矩阵。所谓对称矩阵就是n阶矩阵的元满意aij =
aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元和左下角绝对应的元全是相等的。

    从那些矩阵中,相当轻便通晓图中的音信。

    (1)要看清任性两顶点是还是不是有边无边就相当轻便了;

   
(2)要精通有个别极点的度,其实正是以此终端vi在邻接矩阵中第i行或(第i列)的因素之和;

   
(3)求极点vi的持有邻接点正是将矩阵中第i行元素扫描三次,arc[i][j]为1就是邻接点;

   
而有向图讲究入度和出度,极点vi的入度为1,偏巧是第i列各数之和。极点vi的出度为2,即第i行的各数之和。

    若图G是网图,有n个极点,则邻接矩阵是三个n*n的方阵,定义为:

    图片 3

   
这里的wij表示(vi,vjState of Qatar上的权值。无穷大表示一个微型机允许的、大于所有边上权值的值,也正是多个不或许的极限值。上面左图正是八个有向网图,右图正是它的邻接矩阵。

    图片 4

下边是其代码达成:

 

#include

#include

#include

#define NUM 20;

#define BIG 22365;

 

typedef enum{DG,UNG,DN,UDN} graphtype;   //图的种类

typedef int vrtype;      //顶点类型

typedef int *infotype;    //边的连锁消息项目

 

//定义极点关系项目

typedef struct Arccell{

  int arckink;    
 //边的体系,即极点关系项目,无向图为1/0,表是还是不是相邻。无向网为权值

 //infotype info;   //指向该边全体有关音讯

}arccell;

 

//定义无向图/网

typedef struct{

   graphtype gkind;  //图的类别

   vrtype vr[NUM];   //积攒全体终端

   arccell arc[NUM][NUM];  //储存全体边

   int vrnum,arcnum;  //顶点和边的个数

}graph;

 


 //点位某些极点在数组中的地点

int locate(graph G,vrtype v){

   int i;

   for(i=0;ivrnum;i++)

      if(G->vr[i]==v)

         break;

    if(i>=G->vrnum)

        return -1;

    else

        return i;

}


 //创造无向图/网

int  createUDN(graph G){

   scanf(“%d %d “,&vrnum,&arnum 卡塔尔国;  //
输入极点和边数量以至边相关音讯数据

   for(i=0;i

      scanf(“%d”,&vr[i]);

   for(i=0;i

     for(j=0;j

        arc[i][j]={BIG,NULL};

    for(i=0;i

        scanf(“%d %d %d”,&vr1,&vr2,&arckink卡塔尔;  //输入极点关系项目

        j=locate(G,vr1State of Qatar;  //定位俩顶点

        k=locate(G,vr2卡塔尔国;  //输入极点关系项目

        if(i!=-1&&j!=-1卡塔尔(قطر‎{  //俩极点均设有

            G->arc[j][k]->arckink;

         

           
G->arc[j][i]->artype=G->arc[i][j]->artype;
 //将音信复制到其对称边上

            G->arc[j][i]->info=G->arc[i][j]->info;

        }

    }

    return 0;

}


 //创造有向图/网。

与成立无向图/网形似,然而最后不用复制消息到其对称弧上。再度不作重复成立

 

 int createDN(graph G){

 

    return 0;

}

 


int creategraph(graph GState of Qatar{   //选用要积累的图的花色

   switch(G->gtype){

      case DG:createNG(G);

      case UNG:createUNG(G);

      case DN:createDN(G);

      case UDN:createUDN(G);

      default:return ERROR;

   }

}

 

int main()    //主函数。

{

    graph G;

    creategraph(G);

    return 0;

}

 


 

2、邻表法:

//邻表法消除了邻接矩阵的顽疾,但对此每一种终端而已,查找其出度轻易,而要找入读却得遍历整个图才干找到。故邻表法不符合有向图/网存款和储蓄。无向图/网能够其来积攒,比十字链表法轻便

 

    邻接表的拍卖措施是如此的:

   
(1)图中极点用多少个黄金时代维数组存款和储蓄,当然,顶点也能够用单链表来积累,但是,数组能够较轻巧的读取极点的音讯,特别低价。

   
(2)图中种种终端vi的装有邻接点构成叁个线性表,由于邻接点的个数不定,所以,用单链表存款和储蓄,无向图称为极点vi的边表,有向图则称为极点vi作为弧尾的出边表。

    举个例子,下图正是三个无向图的邻接表的布局。

    图片 5

   
从图中得以看见,极点表的相继结点由data和firstedge八个域表示,data是数据域,存款和储蓄极点的信息,firstedge是指针域,指向边表的率先个结点,即此顶点的第三个邻接点。边表结点由adjvex和next多个域组成。adjvex是邻接点域,存款和储蓄某极点的邻接点在顶点表中的下标,next则存款和储蓄指向边表中下三个结点的指针。

   
对于带权值的网图,能够在边表结点定义中再充实三个weight的数据域,存款和储蓄权值音信就能够。如下图所示。

    图片 6

 

对此邻接表构造,图的树立代码如下。

#define BIG 26655;

#define NUM 20;

 

typedef char vrtype; //极点为字符时无法是换行符,因为出口字符要换行

typedef int *infotype;

 

 

//定义极点关系项目

typedef struct Arccell{

  int tail;

  int weight;      //无向网为权值,无向图无需。

 //infotype info;   //指向该边全数相关信息

  struct Arccell *next;

}arccell;

 

//定义极点类型

typedef struct {

   vrtype data;

   arccell *firstarc;

}vrcell;

 

 

//定义无向图/网类型

typedef struct{

   vrcell vr[NUM];   //积攒全体终端

   int vrnum,arcnum;  //极点和边的个数

}graph;

 

 

void CreateGraph(Graph g)

{

    int i, j, k;

    EdgeNode *e;

    EdgeNode *f;

  //  printf(“输入极点数和边数:n”);

    scanf(“%d,%d”, &g->numVertexes, &g->numEdges);

 

    for(i = 0; i < g->numVertexes; i++State of Qatar    //输入极点消息

    {

       // printf(“请输入极点%d:n”, i);

        g->adjList[i].data = getchar();

        g->adjList[i].firstedge = NULL;     //将边表置为空表

 

        while(g->adjList[i].data == ‘n’)

        {

            g->adjList[i].data = getchar();

        }

    }

 

    //建设结构边表

    for(k = 0; k < g->numEdges; k++)

    {

        printf(“输入边(vi,vj卡塔尔上的极点序号:n”);

        char p, q;

        p = getchar();

        while(p == ‘n’)

        {

            p = getchar();

        }

        q = getchar();

        while(q == ‘n’)

        {

            q = getchar();

        }

        int m, n;

        m = Locate(g, p);

        n = Locate(g, q);

        if(m == -1 || n == -1)

        {

            return;

        }

        //向内部存款和储蓄器申请空间,生成边表结点

        e = (EdgeNode *)malloc(sizeof(EdgeNode));

        if(e == NULL)

        {

            fprintf(stderr, “malloc() error.n”);

            return;

        }

        //邻接序号为j

        e->adjvex = n;

        //将e指针指向当前极端指向的布局

        e->next = g->adjList[m].firstedge;

        //将当前终端的指针指向e

        g->adjList[m].firstedge = e;

 

 

        f = (EdgeNode *State of Qatarmalloc(sizeof(EdgeNode卡塔尔(قطر‎卡塔尔国;
 //有向图/网则没有必要开展这一步

        if(f == NULL)

        {

            fprintf(stderr, “malloc() error.n”);

            return;

        }

        f->adjvex = m;

        f->next = g->adjList[n].firstedge;

        g->adjList[n].firstedge = f;

    }

}

 


 

3、十字链表法:

 

十字链表(Orthogonal
List)是有向图的风度翩翩种存款和储蓄方法,它实际上是邻接表与逆邻接表的组成,即把每一条边的边结点分别协会到以弧尾极点为头结点的链表和以弧头极点为头极点的链表中。在十字链表表示中,极点表和边表的结点构造分别如图8.13
的(aState of Qatar和(bState of Qatar所示。

图片 7

 

 
     
在弧结点中有八个域:此中尾域(tailvex卡塔尔和头(headvexState of Qatar分别提醒弧尾和弧头这七个顶点在图中的地点,链域hlink
指向弧头雷同的下一条弧,链域tlink 指向弧尾相像的下一条弧,info
域指向该弧的连锁新闻。弧头相通的弧在同豆蔻梢头链表上,弧尾相像的弧也在同样链表上。它们的头结点即为极点结点,它由多个域组成:此中vertex
域存款和储蓄和终极相关的消息,如极点的称号等;firstin 和firstout
为多少个链域,分别针对以该终端为弧头或弧尾的第八个弧结点。比如,图8.14(a卡塔尔(قطر‎中所示图的十字链表如图8.14(b)所示。若将有向图的邻接矩阵看成是萧疏矩阵的话,则十字链表也得以看作是邻接矩阵的链表存款和储蓄构造,在图的十字链表中,弧结点所在的链表非循环链表,结点之间针锋相投地方自然变成,不自然按极点序号有序,表头结点即极点结点,它们之间而是顺序存储。有向图的十字链表存款和储蓄表示的花样描述如下:

 

#define
MAX_VERTEX_NUM 20

typedef
struct ArcBox {

int
tailvex,headvex;

struct
ArcBox * hlink, tlink; /分别为弧头相符和弧尾相财的弧的链域*/

InfoType
info;

}ArcBox;

typedef
struct VexNode {

  VertexType
vertex:

  ArcBox
fisrin, firstout;

}VexNode;

typedef
struct {

   VexNode
xlist[MAX_VERTEX_NUM];

   int
vexnum,arcnum;

}OLGraph;

图片 8

 

 

 
     下边给出营造二个有向图的十字链表存款和储蓄的算法。通过该算法,只要输入n
个极端的音讯和e
条弧的消息,便可创立该有向图的十字链表,其算法内容如下。

void
CreateDG(LOGraph **G)

{

 
     scanf (&(*G->brcnum),&(*G->arcnum),&IncInfo);

 
     for (i=0;i<*G->vexnum;++i){

     scanf(&(G->xlist[i].vertex));

    *G->xlist[i].firstin=NulL;*G->xlist[i].firstout
=NULL;

 
         }

for(k=0;k

{  
scanf(&v1,&v2);

i=LocateVex(*G,v1);
j=LocateVex(*G,v2);

p=(ArcBox*)
malloc (sizeof(ArcBox));

*p={
i,j,*G->xlist[j].fistin,*G->xlist[i].firstout,NULL}

*G->xlist[j].fisrtin=*G->xlist[i].firstout=p;

if
(IncInfo) Input( p->info);

}

}

 

在十字链表中既轻易找到认为尾的弧,也便于找到以vi
为头的弧,因此轻巧求得顶点的出度和入度(或需求,可在建构十字链表的还供给出)。同时,由算法8.3
可见,创设十字链表的时日复杂度和树立邻接表是相似的。在某个有向图的选拔中,十字链表是很有用的工具。