技术

数据结构之图论基础

1、图的数据存储

1.1、 邻接矩阵

图的邻接矩阵是由两个数组完成，一个一维数组存储图中的顶点;一个二维数组存储图中的边或弧。
如果图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为：
arc[i][j]等于1（如果（Vi，Vj）属于E），反之等于0。
有向图也差不多，有了出度和入度的概念
网 就是有权的图

邻接矩阵的创建

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITY 65535

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义  */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct
{
	VertexType vexs[MAXVEX]; /* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
	int numNodes, numEdges; /* 图中当前的顶点数和边数  */
}MGraph;

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *G)
{
	int i,j,k,w;
	printf("输入顶点数和边数:\n");
	scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
	for(i = 0;i <G->numNodes;i++) /* 读入顶点信息,建立顶点表 */
		scanf(&G->vexs[i]);
	for(i = 0;i <G->numNodes;i++)
		for(j = 0;j <G->numNodes;j++)
			G->arc[i][j]=INFINITY;	/* 邻接矩阵初始化 */
	for(k = 0;k <G->numEdges;k++) /* 读入numEdges条边，建立邻接矩阵 */
	{
		printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
		scanf("%d,%d,%d",&i,&j,&w); /* 输入边(vi,vj)上的权w */
		G->arc[i][j]=w; 
		G->arc[j][i]= G->arc[i][j]; /* 因为是无向图，矩阵对称 */
	}
}

int main(void)
{    
	MGraph G;    
	CreateMGraph(&G);
	
	return 0;
}

1.2、邻接表

与邻接矩阵不同，就是把顶点存在一个数组，然后其邻接点以链表的方式存储即可，节约空间。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大顶点数,应由用户定义 */

typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

typedef struct EdgeNode /* 边表结点  */
{
	int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
	EdgeType info;		/* 用于存储权值,对于非网图可以不需要 */
	struct EdgeNode *next; /* 链域,指向下一个邻接点 */
}EdgeNode;

typedef struct VertexNode /* 顶点表结点 */
{
	VertexType data; /* 顶点域,存储顶点信息 */
	EdgeNode *firstedge;/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];

typedef struct
{
	AdjList adjList; 
	int numNodes,numEdges; /* 图中当前顶点数和边数 */
}GraphAdjList;

/* 建立图的邻接表结构 */
void  CreateALGraph(GraphAdjList *G)
{
	int i,j,k;
	EdgeNode *e;
	printf("输入顶点数和边数:\n");
	scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
	for(i = 0;i < G->numNodes;i++) /* 读入顶点信息,建立顶点表 */
	{
		scanf(&G->adjList[i].data); 	/* 输入顶点信息 */
		G->adjList[i].firstedge=NULL; 	/* 将边表置为空表 */
	}
	
	
	for(k = 0;k < G->numEdges;k++)/* 建立边表 */
	{
		printf("输入边(vi,vj)上的顶点序号:\n");
		scanf("%d,%d",&i,&j); /* 输入边(vi,vj)上的顶点序号 */
		e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */
		e->adjvex=j;					/* 邻接序号为j */                         
		e->next=G->adjList[i].firstedge;	/* 将e的指针指向当前顶点上指向的结点 */
		G->adjList[i].firstedge=e;		/* 将当前顶点的指针指向e */               
		
		e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */
		e->adjvex=i;					/* 邻接序号为i */                         
		e->next=G->adjList[j].firstedge;	/* 将e的指针指向当前顶点上指向的结点 */
		G->adjList[j].firstedge=e;		/* 将当前顶点的指针指向e */               
	}
}

int main(void)
{    
	GraphAdjList G;    
	CreateALGraph(&G);
	
	return 0;
}

2、图的遍历

与树的遍历一样，就图的一个顶点出发，访遍所有其余顶点且使每一个顶点仅被访问一次，这一过程就是图的遍历（BFS，DFS）

2.1、深度优先搜索DFS

深度优先搜索可以是一个递归过程，有点像树的前序遍历。
从图中某个顶点V出发，访问此顶点，然后从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相同的顶点都被访问到。
如果是邻接矩阵,DFS实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int visited[MAX];   //访问标志数组

void DFS(MGraph G, int i)
{
	int j;
	visited[i] = TRUE;
	printf("%c" , G.vexs[i]);
	for(j = 0; j< G.numVertexes; j++)
		if(G.arc[i][j] == 1 && !visited[j])
			DFS(G, j);   //这是一个递归调用
}

// 邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G)
{
	int i;
	for(i = 0; i < G.numVertexes; i++)
		visited[i] = FALSE;
	for(i = 0; i < G.numVertexes; i++)
		if(!visited[i])
			DFS(G,i);
}

如果是邻接表其实和邻接矩阵差不多：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void DFS(GraphAdjList GL, int i)
{
	EdgeNode *p;
	visited[i] = TRUE;
	printf("%c ", GL->adjList[i].data);
	p = GL->adjList[i].firstedge;
	while(p)
	{
		if(!visited[p->adjvex])
			DFS(GL, p->adjvex);
		p = p->next;
	}
}

void DFSTraverse(GraphAdjList GL)
{
	int i;
	for(i = 0; i < GL->numVertexes; i++)
		visited[i] = FALSE;
	for(i = 0; i < GL->numVertexes; i++)
	    if(!visited[i])
	    	DFS(GL, i);
}

可以对比两者复杂度看出，对于n个顶点e条边，由于邻接矩阵必须要要搜索nn的矩阵，复杂度为O（nn); 邻接点复杂度为O(n+e);

2.2、广度优先搜索BFS

如果深度优先搜索DFS像树的前序遍历，那么广度优先搜索BFS就有点像树的层序遍历。
如果把顶点直接连接的点看成第二层，依次类推，就有一个调整后的比较有层次的图了

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
30
31
32
33
void BFSTraverse(MGraph G)
{
    int i,j;
    Queue Q;
    for(i = 0; i < G.numVertexes; i++)
    	visited[i] = FALSE;
    InitQueue(&Q);
    for(i = 0; i < G.numVertexes; i++)
    {
    	if(!visited[i])
    	{
    		visited[i] = TRUE;
    		printf("%c", G.vexes[i]);
    		EnQueue(&Q, i);
    		while(!QueueEmpty(Q))
    		{
    			DeQueue(&Q, &i); //出队列
    			for(j = 0; j < G.numVertexes; j++)
    			{
    				if(G.arc[i][j]==1 && !visited[j])
    				{
    					visited[j] = TRUE;
    					printf("%c", G.vexes[j]);
    					EnQueue(&Q, j);
    				}
    			}
	    	}
  
	    }

	}

}

下面是邻接表的广度优先搜索

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
30
31
32
33
34
void BFSTraverse(GraphAdjList GL)
{
	int i;
	EdgeNode *p;
	Queue Q;
	for(i = 0; i < GL->numVertexes; i++)
		visited[i] = FALSE;
	InitQueue(&Q);
	for(i = 0; i < GL->numVertexes; i++)
	{
		if(!visited[i])
		{
			visited[i] = TRUE;
			printf("%c", GL->adjList[i].data);
			EnQueue(&Q, i);
			while(!QueueEmpty(Q))
			{
				DeQueue(&Q, &i);
				p = GL->adjList[i].firstedge;
				while(p)
				{
					if(!visited[p->adjvex])
					{
						visited[p->adjvex] = TRUE;
						printf("%c", GL->adjList[p->adjvex].data);
						EnQueue(&Q, p->adjvex);
					}
					p = p->next;
				} 
			}

		}
	}
}

对比DFS和BFS会发现其实两者的复杂度一样的，只是访问的顺序不一样了而已。两者没有什么优劣之分，只是在不同情况下需要考虑合适的方法。
深度优化适合目标明确，以找到目标为主要目的的情况；而广度优化适合在不断扩大遍历范围时找到相对最优解的情况。