data structure——图

图的存储结构：

  • 图的顺序存储结构：邻接矩阵的结构型
    有两个数组：一个一维数组存储图中的顶点信息；一个二维数组存储图中的边或弧的信息。
    缺点：如果边数相对于顶点数较少，那么边数组的存储空间是一个很大的浪费。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    typedef struct
    {
    	int no;  //顶点编号
    	char info;  //顶点的其他信息，视情况而定写不写
    }VertexType;

    typedef struct //图的定义
    {
    	int edges[maxSize][maxSize];  //邻接矩阵定义，可看做边表
    	int n,e;  //顶点数和边数
    	VertexType vex[maxSize];  //顶点表，存放结点信息
    }MGraph;  //图的邻接矩阵类型

    邻接矩阵事例：
邻接矩阵
  • 图的链式存储结构：邻接表
    数组与链表相结合；图中顶点用一维数组来存储（也可用单链表）；图中的每个顶点的邻接点用单链表来存储。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

typedef struct ArcNode  //边表
{
	int adjvex;  //该边所指向的结点的位置，就是顶点标号
	struct ArcNode *nextarc;  //指向这个顶点结点的另一条边的指针
	int info;  //该边的相关信息
}ArcNode;

typedef struct   //顶点表
{
	char data;  //顶点信息
	ArcNode *firstarc;  //指向第一条边的指针
}VNode;

typedef struct 
{
	VNode adjlist[maxSize];  //邻接表
	int n,e;  //顶点数和边数
}AGraph;  //图的邻接表类型

邻接表事例：
ArcNode是“边”（边结点）的结构体，是用点与点之间的关系来表示边的。其中的adjvex（Adjacent vertices邻接顶点的缩写）这条边所指的顶点，是顶点在数组中的下标，*next是指向下一个边结点的指针。
VNode是“顶点”的结构体，AGraph是“图”的结构体，其中定义了一个VNode型的数组来储存顶点，n,e是结点数和边数。
邻接表
邻接表中，如果是有向图的话，邻接表是存储的是这个结点引出的边，也即“出度”，而如果存储的是指向这个结点的边，也即“入度”的话，这个存储结构就是“逆邻接表”。

邻接矩阵和邻接表
  • 有向图的十字链表存储结构

如果我们想即存储出度又存储入度呢？我们可以这样：
其中的firstIn是指向入边链表中第一个结点的指针，firstOut指向第一个出边链表的指针。
start是指当前边起点的数据域，end是当前边终点的数据域，nextIn指向这个顶点的下一个入边，nextOut指向这个结点的下一个出边。

十字链表

这就是有向图的十字链表存储结构。

  • 无向图的邻接多重表

我们在看到用邻接表存储无向图的时候，会出现重复存储的情况，那么我可以这样：
左上方是顶点的结构体设计，右上方是边结点的结构体设计。
其中的Vi是边的起点，Vj是边的终点。ViNext是表示与Vi相关的下一个边结点，VjNext是表示与Vj相关的下一个边结点。

邻接多重表

遍历
这里dfs和bfs的代码所对应的都是图的邻接表的存储方式的遍历。

  • 深度优先遍历（DFS）

很类似于树的先序遍历算法，
这里用了一个visit[]数组，设置为一个标记，如果这个结点已经访问过了就设置为1，如果没有访问过默认为0。
注意：Visit函数和visit[]数组不是同一个东西，第10句中的下一个结点指的是在邻接表中当前结点的下一个结点。

1
2
3
4
5
6
7
8
9
10
11
12
void DFS(int c,AGraph *G)
{
	visit[v]=1;
	Visit(v);  //Visit函数代表了对顶点v的访问
	ArcNode* q=G->adjList[v].first;  //这里是p指向顶点的第一条边
	while(q!=NULL)
	{
		if(visit[q->adjV]==0)  //如果这个顶点没有被访问过，那么就访问他
			DFS(q->adjV,G);  //递归处理
			q=q->next;  //指向当前顶点的下一个结点
	}
}
dfs
  • 广度优先遍历（BFS）
    类似于树的层次遍历，遍历过程会用到一个列表。主要过程是：取一个顶点进行访问，入队，并将这个点标记为已访问；接着，访问这个结点的下一个结点，没有访问过就访问，标记为1，入队，如此循环将邻接点都入队，p为空时就出队，然后循环对这个出队顶点的所有没有被访问过的邻接顶点进行访问，标记，入队，依次循环最后，直至出队使得队列为空，结束循环。
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
void BFS(AGraph *G,int v,int visit[maxsize])
{
	ArcNode *p;
	int que[maxSize],front=0,rear=0;  //创建一个队列que
	int j;
	Visit(v);  //访问任意一个v结点
	visit[v]=1;  //标记为已访问
	rear=(rear+1)%maxSize;  //当前结点入队
	que[rear]=v;  //入队，（是将数组下标写进队列中）
	while(front!=rear)  //如果队列不为空，就循环
	{
		front=(front+1)%maxSize;  //出队
		j=que[front];  
		p=G->adjlist[j].first;  //p指向这个出队顶点j的第一条边
		while(p!=NULL)  //当p不空的时候,
		{
			if(visit[p->adjV]==0)  //如果p的邻接点没有被访问过，
			{
				Visit(p->adjV);  //就访问他,
				visit[p->adjV]=1;  //接着标记为已访问，
				rear=(rear+1)%maxSize;  //该顶点也入队
				que[rear]=p->adjV;  //入队
			}
			p=p->next;  //访问下一条边
		}
	}
}
bfs
  • 最小生成树

由一个图按照某种规则导出的一个树，叫生成树。最小生成树：构成这个生成树的所有分支的权值和最小。

prime算法
求最小生成树的代码：

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
void Prim(int n ,float MGraph[][n],int v0,float &sum)//顶点个数，带权图，构造生成树的起始顶点，
{                                                    //存储最小权值和（代价）
	int lowCost[n],vSet[n];  
	int v,k,min;
	for(int i=0;i<n;++i)
	{
		lowCost[i]=MGraph[v0][i];  //lowCost[]指向vo初始点的同一行的不同列的顶点
		vSet[i]=0;
	}
	v=v0;  //v指向第一个结点，
	vSet[v]=1;  //已经并入，所以标记设置为1
	sum=0;  //初始化
	for(int i=0;i<n-1;++i)
	{
		min=INF; //min初始化为无穷大
		for(int j=0;j<n,++j)
			if(vSet[j]==0&&lowCost[j]<min)
			{
				min=lowCost[j];
				k=j;
			}
			vSet[k]=1;
			v=k;  //v指向如今刚进入的结点
			sum+=min;  //min的值累加到sum
			for(int j=0;j<n;++j)  //更新lowCost数组
				if(vSet[j]==0&&MGraph[v][j]<lowCost[j])
					lowCost[j]=MGraph[v][j];
	}
}

lowCost[]数组是用来存储当前生成树到图中其余顶点的边的最小权值。vSet[i]为1时就说明已经被并入生成树中，为0就没有并入。
v指向刚并入的顶点。

v0是最小生成树的初始结点，所以v=v0

kruskal算法

把当前未被并入的，且并入后不会产生环的最小边进行并入。
如何检测并入后到底会不会产生环呢？就用到了“并查集”。所谓的并查集，就是通过这些图中的点构造出来的树，每一个结点在相连的时候，要一直查到到根结点，如果根结点不相同，说明图中选取边之后不会产生环，所以可以选择这个这个结点的边。

相关的存储结构：