梗概:

这里主要讨论简单图

图的抽象结构

包含两部分:

顶点的有穷非空集合
边的集合

图的符号记法:

G(V,E) 说明:

G表示一个图
V为图中顶点的集合
E为图中边的集合

边集合的符号记法:

E={(A,B),(C,D),<E,F>,(G,H)}

图的特点:

多父对一子, 一父对多子即每一个顶点, 都有可能有多个入度, 也可能有多个出度
1. 而树是一父对多子, 一子对一父
图中任意两个顶点间可能有多条路径
1. 而树任意两个顶点间只有一条路径

特殊的图:

无向完全图

child::无向完全图

有向完全图

child::有向完全图

稠密图和稀疏图

稠密与稀疏都是对边的数量而言的稠密和稀疏是模糊的概念, 两个概念的分界也是模糊的一般规定分界条件为边数=nlogn (log的底随意取任何数)

网

child::网

数学性质:

边总数与度总数的关系:

边总数=度总数/2

邻接矩阵

简单无权无向图

方阵关于主对角线对称
一个顶点的度=该顶点对应行的所有数之和=该顶点对应列的所有数之和

简单无权有向图

一个顶点的入度=该顶点对应列的所有数之和
一个顶点的出度=该顶点对应行的所有数之和

边数的取值范围:

n为顶点数

下限(能取到):

对非连通图无向图: 0
对连通无向图: n-1
1. 此时为极小连通子图

上限(能取到):

对无向图: $C_{n}^{2}$
对有向图: $A_{n}^{2}$
对非连通无向图: $C_{n - 1}^{2} = \frac{( n - 1 ) ( n - 2 )}{2}$
1. 非连通无向图只要有一个顶点不连通就行了, 故该图 = (n-1)个顶点的完全无向图 + 1个孤立顶点

顶点与边的对应确定关系:

n为顶点数边数=

对无向完全图: $C_{n}^{2}$
对有向完全图: $A_{n}^{2}$

无向图的环存在条件:

边数>n-1则必定存在环(⭐)

计算机中的存储结构

图在计算机中的存储方式有多种, 其中邻接矩阵和邻接表最重要

邻接矩阵
邻接表
1. 特点:
  1. 对于有向图, 只能找到单向的边
十字链表
1. 特点:
  1. 只适用于有向图
  2. 能找到双向的边
  3. 创建表的时间复杂度=邻接表的
邻接多重表
1. 特点:
  1. 只适用于无向图

邻接矩阵(adjacency matrix)

梗概:
1. 用一个线性表(一般为数组)存储所有顶点结点
2. 每个顶点结点都只存储数据
3. 用一个方形矩阵(用二维数组模拟)存储边结点
  1. 每个顶点同时作为行和列
    1. 对有向图: 行为弧尾, 列为弧头, 即行指向列
    2. 对无向图: 行列没有顺序
4. 边结点分为两个区域来存储:
  1. 邻接域(名为adj)
    1. 对无权简单图
      1. 用1表示所在行与列构成的无向边存在, 用0表示不存在
    2. 对简单网
      1. 用∞(计算机中用大于权值上限的数来模拟)表示不存在边, 用权值表示存在边
  2. 信息域(名为info)
    1. 存储关于对应边的信息

邻接表和逆邻接表

用线性表(数组或链表,一般是数组)存储每个顶点的两部分内容

第一个是数据域(名为vexdata)

第二个是单链表域(名为firstarc)

该单链表一般没有头结点

该域存储一个指针, 指向单链表第一个边结点

对简单无权图, 链表边结点分三区域储存

指针域(数组下标)(名为adjvex), 其指向线性表中某个顶点
1. 对简单无向图
  1. 指向邻接点之一
2. 对简单有向图
  1. 对邻接表
    1. ⭐指向出度顶点(即弧头)之一
  2. 对逆邻接表
    1. ⭐指向入度顶点(即弧尾)之一
后继域(名为nextarc), 指向下一个结点
信息域(名为info)
1. 存储对应边的信息或权值

十字链表

操作:

抽象定义:

创建图: CreateGraph(G)
1. 前提: 图G不存在
销毁图: DestoryGraph(G)
1. 前提: 图G存在
按值查找顶点位置: LocateVertex(G,v)
1. 前提: 图G存在, 顶点v值合法
2. 结果: 返回v的位置, 找不到返回空
通过顶点位置获得值: GetVertex(G,i)
1. 前提: 图G存在
2. 结果: 返回值, 不存在则返回空
找第一个邻接点: FirstAdjVertex(G,v)
1. 前提: 图G存在, 顶点v值合法
2. 结果: 返回顶点v的第一个邻接点, 不存在邻接点或不存在顶点则返回空
找下一个邻接点: NextAdjVertex(G,v,w)
1. 前提: 图G存在, w为顶点v的某个邻接点
2. 结果: 返回顶点v的下一个邻接点, 其排在w的后面, 如v的下一个邻接点不存在, 返回空
插入顶点: InsertVertex(G,u)
1. 前提: 图G存在, u值合法
2. 结果: 添加一个结点u
删除顶点: DeleteVertex(G,v)
1. 前提: 图G存在, v值合法
2. 结果: 删除顶点v与其相关联的弧
插入弧: InsertArc(G,v,w)
1. 前提: 图G存在, v值,w值都合法
2. 结果: 新增一条弧<v,w>
删除弧: DeleteArc(G,v,w)
1. 前提: 图G存在, v值和w值合法, 存在弧<v,w>
2. 结果: 删除弧<v,w>
遍历顶点: TraverseGraph(G)
1. 前提: 图G存在
2. 结果: 按照某种次序, 只访问一次每个顶点
深度优先搜索连通分量: DepthFirstSearch(G, v)
1. 前提: 图G存在
2. 结果: 深度优先搜索顶点v所处于的连通分量
广度优先搜索连通分量: BreadthFirstSearch(G,v)
1. 前提: 图G存在
2. 结果: 广度优先搜索顶点v所处于的连通分量

梗概:

遍历操作:

图主要有两种遍历顺序:

child::深度优先搜索
child::广度优先搜索

实际应用

child::最小生成树算法

最短路径

child::弗洛伊德 Floyd 图顶点最短路径算法

在c语言中的实现:

抽象存储方式下

遍历全部顶点:

代码:

#define True 1
#define False 0
#define Error -1
#define OK 1
#define Graph AdjMatrix
/*访问标记数组*/
int visited[MAX_VERTEX_NUM];
void TraverseGraph(Graph* G){
//用深度优先顺序,遍历图中的每个顶点,需另外声明图G类型
/*初始化访问标记数组*/
    for(vi=0;vi<G->vexnum;vi++) visited[vi]=False;
/*防止非连通图中有独立顶点遗漏*/
    for(vi=0;vi<G->vexnum;vi++)
	    /*这里以深度优先为例,也可以用其他顺序*/
        if(!visited[vi])DepthFirstSearch(G,vi);
}

深度优先搜索:

梗概:

对递归形式的深度优先搜索

逐个遍历访问邻接点, 以保证每个邻接点都能被访问, 且不重复
访问前还得看看是否已经被访问过了, 因为图中一个顶点有多条入度, 说不定某个邻接点在另外的入度上访问过了

对非递归形式的深度优先搜索

分析递归过程:
1. 递归的时候每一层总是陷入第一个深度优先算法
2. 每一层都要等到上一个深度优先搜索返回之后才能执行下一个
  1. 即要等到上一个深度优先搜索那层的全部都递归完
用栈去模拟递归
1. 每走进一个邻接点, 就把当前的所有邻接点入栈
2. 入栈之后取一个, 继续走进去
递归和非递归访问同一层邻接点的顺序相反, 但都是深度优先

代码:

/*递归形式深度优先搜索*/
void DepthFirstSearch(Graph* G,int v0){
    //对v0操作
    visited[v0]=True;
    w=FirstAdjVertex(G,v0);
    /*对当前层的所有未访问顶点都深度优先搜索*/
    for(;w!=-1;){
        if(!visited[w])
            DepthFirstSearch(G,w);
        w=NextAdjVertex(G,v0,w);
    }
}
/*非递归形式深度优先搜索*/
void DepthFirstSearch(Graph *G, int v0){
//从v0出发深度优先搜索图G,需另外声明图G类型
    SeqStack S;
    InitStack(&S);
    Push(&S,v0);
    for(;!IsEmpty(S);){
        Pop(&S,&v);
        /*每个顶点都要先检查是否已访问
        因为每个顶点都有可能被意想不到的入度访问了*/
        if(!visited[v]){
            //对v操作
            visited[v]=True;
            /*把当前层的所有未访问顶点入栈等待处理*/
            w=FirstAdjVertex(G,v);
            for(;w!=-1;){
	            /*同上,要先检查是否已被访问*/
                if(!visited[w])
                    Push(&S,w);
                w=NextAdjVertex(G,v,w);
            }
        }
    }
}
 
void DNDepthFirstSearch_NonRecursive(AdjMatrix *G, int v0){
//与递归形式的遍历顺序一致
	SeqStack S;int v, w;
	InitStack(&S);Push(&S, v0);
	while (!IsEmpty(&S)){
		Pop(&S, &v);
		if (!visited[v]){
			visit(G, v);//操作v
			visited[v] = True;
			int *stack = (int *)calloc(G->vexnum, sizeof(int));
			int top = -1;
			w = DNFirstAdjVertex(G, v);
			for (; w != -1;){
				if (!visited[w])
					stack[++top] = w;//栈不会满的
				w = DNNextAdjVertex(G, v, w);
			}
			/*用栈的性质把邻接点顺序相反*/
			for (;top != -1;)
				Push(&S, stack[top--]);
			free(stack);
		}
	}
}

广度优先搜索

梗概:

队列用来回溯已访问过的顶点, 而不是用来排队将要被访问的顶点
从队列中取出最早访问过的顶点
1. 依次遍历该顶点的邻接点
2. 遍历完之后, 就马上将其入队
  1. 用于下一次回溯代码:

void BreadthFirstSearch(Graph *G, int v0){
//可以用在TraverseGraph()中
    //操作v0;
    SeqQueue Q;
    visited[v0]=True;
    InitQueue(&Q);
    EnterQueue(&Q,v0);
    int v,w;
    for(;!CycSeqQueue_IsEmpty;){
        DeleteQueue(&Q,&v);
        /*遍历所有邻接点*/
        w=FirstAdjVertex(G,v);
        for(;w!=-1;){
	        /*每个顶点都要先检查是否已访问
	        因为每个顶点都有可能被意想不到的入度访问了*/
            if(!visited[w]){
                //对w操作;
                visited[w]=True;
                /*用于下层遍历时从先访问的顶点找其邻接点*/
                EnterQueue(&Q,w);
            }
            w=NextAdjVertex(G,v,w);
        }
    }
}

求简单路径

梗概

找一条简单路径

采用深度优先搜索
用一维数组记录每一步经过的结点
如果沿着当前路径找到了目标结点, 则记录的路径即简单路径
需要给深度优先搜索递归传递深度信息, 以便回溯后覆盖记录的路径
1. 如果沿着当前路径找不到, 随着深度优先搜索回溯, 便会回溯到之前的分叉结点, 然后继续往下走, 当前路径自动覆盖了记录的路径

找出全部的简单路径

即找到后, 不停止搜索, 继续回溯到分叉结点, 遍历下一个邻接点(分叉)
1. 因为遍历邻接点本身就不会重复, 所以同一个结点的每个出度只会走一遍
每次回溯前, 都把刚才遍历完的顶点重新标记为未访问
1. 遍历某一结点时, 把该结点标记为已访问, 有两个作用:
  1. 防止遍历的时候往回走, 或者形成环路
  2. 让每个邻接点都只访问一次
2. 而对于该算法
  1. 回溯前(即遍历完的时候), 不需要了
    1. 回溯前还是会标记的, 防止回路
    2. 只不过遍历完之后, 就不可能形成环路
  2. 同一个结点可能同时出现在多个简单路径中

找出全部简单路径的代码

void path_all2(Graph *G, int u, int tarV, int path[], int depth){
    visited[u] = 1;//置已访问标记,防止遍历环
    path[depth] = u;//将当前顶点添加到路径中
    depth++;//路径长度增加1
    if(u==tarV){//满足条件，输出一条路径
        printf("\npath: ");
        for(int i = 0; i <depth; i++)
            printf("%3d", path[i]);
        printf("\n");
    }
    int w = DNFirstAdjVertex(G,u);
    while(w!=-1){
        if(!visited[w])
            path_all2(G, w, tarV, path, depth);
        w = DNNextAdjVertex(G,u,w);
    }
    /*让该点顶能够被再次被遍历,
    去掉这行代码,算法只会得到一条简单路径*/
    visited[u] = 0;
}
 
void Path_all(Graph *G, int u,int tarV){
    int* path=(int *)calloc(G->vexnum,sizeof(int));
    for(int i=0;i<MAX_VERTEX_NUM;++i)
        visited[i]=0;
    path_all2(G, u, tarV, path, 0);
    free(path);
}

邻接矩阵的存储方式下:

定义:

梗概:

图结构体中有五个成员:
1. 顶点数据一维数组
2. 存储边的二维数组
3. 顶点总数
4. 边总数
5. 图的种类标记符代码:

#define MAX_VERTEX_NUM 64
#define INFINITY 32768 //用来表示无穷大
/*DG为有向图,DN为有向网,UDG为无向图,UDN为无向图*/
typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef char VertexData;
typedef int AdjType;
typedef char OtherInfo;
typedef struct ArcNode{
    /*对无权图,用1和0表示是否相邻*/
    /*对带权图,则为权值类型*/
    AdjType adj;
    /*弧的其他信息类型*/
    OtherInfo info;
}ArcNode;
typedef struct{
    /*存放顶点的数组*/
    VertexData vertex[MAX_VERTEX_NUM];
    /*相邻矩阵*/
    ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum, arcnum;
    /*图的种类标记*/
    GraphKind kind;
}AdjMatrix;

按值查找

int LocateVertex(AdjMatrix *G,VertexData v){
//按值查找顶点,返回其在线性表中的下标
    int i;
    for(i=0;i<G->vexnum;i++)
    if(G->vertex[i]==v){
        return i;
    }
    return 0; //报错
}

第一个邻接点

int DNFirstAdjVertex(AdjMatrix *G,int v){
//有向网中v的第一个邻接点, 没有返回-1
    for(int i=0;i<G->vexnum;++i)
        if(G->arcs[v][i].adj&&G->arcs[v][i].adj!=INFINITY)return i;
    return -1;
}

下一个邻接点

int DNNextAdjVertex(AdjMatrix *G,int v,int w){
//返回顶点v邻接顶点中,排在w后面的第一个,若w是最后一个,返回-1
    for(int i=w+1;i<G->vexnum;++i)
        if(G->arcs[v][i].adj&&G->arcs[v][i].adj!=INFINITY)return i;
    return -1;
}

创建有向网:

测试用的有向网(五点七边):

child:: 命令行输入:

代码:

int CreateDN(AdjMatrix *G){
//创建有向网
    int i,j,k,weight;
    VertexData rawin,v1, v2;
/*输入将要创建的顶点和弧总数*/
    printf("Enter vernum and arcnum(use space):\n");
    scanf("%d %d",&(G->vexnum),&(G->arcnum));
/*初始化每条边*/
    for(i=0;i<G->vexnum;i++)
        for(j=0;j<G->vexnum;j++)
            G->arcs[i][j].adj=INFINITY;
/*输入每个顶点的数据*/
    printf("Enter each vertex data(use space):\n");
    for(i=0;i<G->vexnum;i++){
        for(rawin=' ';rawin==' '||rawin=='\n';)
            scanf("%c",&rawin);
        G->vertex[i]=rawin;
    }
/*依次连接某两个顶点,并赋予权值*/
    printf("Enter a vertex and another vertex to connect them,");
    printf("and finally enter their weight");
    printf("(Single arc in a line,and use space):\n");
    for(k=0;k<G->arcnum;k++){
        for(rawin=' ';rawin==' '||rawin=='\n';)
            scanf("%c",&rawin);
        v1=rawin;
        for(rawin=' ';rawin==' '||rawin=='\n';)
            scanf("%c",&rawin);
        v2=rawin;
        scanf("%d",&weight);
        //scanf("%1[^ ^\n]%1[^ ^\n]%d",&v1,&v2,&weight);
        i=LocateVertex(G,v1);
        j=LocateVertex(G,v2);
        if(!(i||j))return 0;
        G->arcs[i][j].adj=weight;
    }
/*标志为有向网*/
    G->kind=DN;
    return 1;
}

打印邻接矩阵与顶点数据

void printAdjMatrix(AdjMatrix *G){
	/*打印顶点数据*/
	printf("Data:\t");
    for(int i=0;i<G->vexnum;++i)
        printf("%c\t",G->vertex[i]);
	printf("\n\t");
	/*打印表头*/
    for(int i=0;i<G->vexnum;++i)
        printf("v%d\t",i);
    printf("\n");
    /*打印矩阵*/
    for(int i=0;i<G->vexnum;++i){
        printf("v%d\t",i);
        for(int j=0;j<G->vexnum;++j)
            printf("%d\t",G->arcs[i][j].adj);
        printf("\n");
    }
}

邻接表的存储结构下

定义:

梗概:

图结构体中有四个成员:
1. 顶点结点的一维数组
2. 顶点总数
3. 边总数
4. 图的种类标记符代码:

#define MAX_VERTEX_NUM 64
typedef char OtherInfo;
typedef char VertexData;
/*DG为有向图,DN为有向网,UDG为无向图,UDN为无向图*/
typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef struct ArcNode{
    //邻接顶点的下标
    int adjvex;
    struct ArcNode *nextarc;
    /*弧的其他信息类型*/
    OtherInfo info;
}ArcNode;
typedef struct{
    VertexData data;
    ArcNode *firstarc;
}VertexNode;
typedef struct{
    VertexNode vertex[MAX_VERTEX_NUM];
    int vexnum, arcnum;
    GraphKind kind;
}AdjList;

统计顶点入度

代码:

void FindInD(AdjList *G,int indegree[MAX_VERTEX_NUM]){
    int i;ArcNode* p;
    for(i=0;i<G->vexnum;++i)
        indegree[i]=0;
    for(i=0;i<G->vexnum;++i){
        p=G->vertex[i].firstarc;
        for(;p;){
            ++indegree[p->adjvex];
            p=p->nextarc;
        }
    }
}

十字链表结构下

定义:

梗概:

图结构体中有四个成员:
1. 顶点结点的一维数组
2. 顶点总数
3. 边总数
4. 图的种类标记符代码:

#define MAX_VERTEX_NUM 64
/*DG为有向图,DN为有向网,UDG为无向图,UDN为无向图*/
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef char VertexData;
typedef struct ArcNode{
    int tailvex,headvex;
    struct ArcNode *hlink, *tlink;
}ArcNode;
typedef struct VertexNode{
    VertexData data;
    ArcNode *firstin, *firstout;
}VertexNode;
typedef struct{
    VertexNode vertex[MAX_VERTEX_NUM];
    int vexnum, arcnum;
    GraphKind kind;
}OrthList;

创建十字链表

梗概:

每创建一条弧, 就要将这条弧插入到两个顶点所对应的链表中
1. 用头插法代码:

void CrtOrthList(OrthList *G){
    int i,n,e,k,vt,vh,j;
    ArcNode* p;
    /*输入顶点和弧总数*/
    scanf("%d,%d",&n,&e);
    G->vexnum =n;
    G->arcnum =e;
    for(i=0;i<n;i++){
        /*赋值数值给顶点*/
        scanf("%c",&(G->vertex[i].data));
        /*初始化存在的顶点*/
        G->vertex[i].firstin=NULL;
        G->vertex[i].firstout=NULL;
    }
    for(k=0;k<e;k++){
        /*输入要连接的两个顶点*/
        scanf("%c,%c",&vt,&vh);
        i=LocateVertex(G,vt);
        j=LocateVertex(G,vh);
        p=(ArcNode*)calloc(1,sizeof(ArcNode));
        /*赋值弧头和弧尾*/
        p->tailvex=i;p->headvex=j;
        /*用头插法分别插入链表*/
        p->tlink=G->vertex[i].firstout;
        G->vertex[i].firstout=p;
        p->hlink=G->vertex[j].firstin;
        G->vertex[j].firstin=p;
    }
}

🪴qql1's digital garden

探索

图

相关概念:

梗概: