数据结构:图（1）

一、图的基本概念

1.有向图

若图G中的每条边都是有方向的，则称G为有向图(Digraph)。

2.无向图

若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。

3.连通图的生成树

一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。

二、图的存储结构

1.数组表示法

用两个数组分别存储数据元素（顶点）的信息和数据元素之间的关系（边或弧）的信息。

2.邻接表表示法

对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。

三、图的遍历

图的遍历是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。

1.深度优先遍历

图的深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。

2.广度优先遍历

广度优先遍历类似于树的按层次遍历。采用的搜索方法的特点是尽可能先对横向进行搜索，故称其为广度优先搜索(Breadth-FirstSearch)。相应的遍历也就自然地称为广度优先遍历。

 1 ///Name:Tree
 2 ///Author:JA
 3 ///Date:2015-3-11
 4 
 5 
 6 
 7 ///图的存储结构
 8 //图的数组存储表示
 9 #define INFINITY   INT_MAX   //最大值
10 #define MAX_VERTEX_MUN 20    //最大顶点个数
11 typedef  enum{DG,DN,UDG,UDN}  GraphKind;  //{有向图，有向网，无向图，无向网}
12 typedef struct ArcCell{
13     VRType    adj;    //VRType是顶点关系类型
14     InfoType  *info;  //该弧相关信息的指针
15 }ArcCell,AdjMatrix[MAX_VERTEX_MUN][MAX_VERTEX_MUN];
16 typedef struct{
17     VertexType vexs[MAX_VERTEX_MUN];  //顶点向量
18     AdjMatrix  arcs;                //邻接矩阵
19     int vexnum, arcnum;             //图的当前顶点数和弧数
20     GraphKind   kind;               //图的种类标志
21 }MGraph;
22 
23 //图的邻接表存储表示
24 typedef struct node{//边表结点
25     int adjvex; //邻接点域
26     struct node *next; //链域
27         //若要表示边上的权，则应增加一个数据域
28 }EdgeNode;
29 typedef struct vnode{ //顶点表结点
30     VertexType vertex; //顶点域
31     EdgeNode *firstedge;//边表头指针
32 }VertexNode;
33 
34 typedef VertexNode AdjList[MaxVertexNum];//AdjList是邻接表类型
35 typedef struct{
36     AdjList adjlist;//邻接表
37     int n,e; 图中当前顶点数和边数
38 }ALGraph; //对于简单的应用，无须定义此类型，可直接使用AdjList类型。 
39 
40 //深度优先遍历
41 typedef enum{ FALSE,TRUE }Boolean;//FALSE为0，TRUE为1
42 Boolean visited[MaxVertexNum]; //访问标志向量是全局量
43 void DFSTraverse(ALGraph *G)
44 { //深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同
45     int i;
46     for (i = 0; i < G->n; i++)
47         visited[i] = FALSE; //标志向量初始化
48     for (i = 0; i < G->n; i++)
49     if (!visited[i]) //vi未访问过
50         DFS(G,i); //以vi为源点开始DFS搜索
51 }//DFSTraverse
52 
53 //邻接表表示图的广度优先搜索算法
54 void BFS(ALGraph*G，int k)
55 {// 以vk为源点对用邻接表表示的图G进行广度优先搜索
56     int i;
57     CirQueue Q; //须将队列定义中DataType改为int
58     EdgeNode *p;
59     InitQueue(&Q);//队列初始化
60     //访问源点vk
61     printf("visit vertex：％e"，G->adjlist[k].vertex);
62     visited[k] = TRUE;
63     EnQueue(&Q,k);//vk已访问，将其人队。（实际上是将其序号人队）
64     while (!QueueEmpty(&Q)){//队非空则执行
65         i = DeQueue(&Q); //相当于vi出队
66         p = G->adjlist[i].firstedge; //取vi的边表头指针
67         while (p){//依次搜索vi的邻接点vj(令p->adjvex=j)
68             if (!visited[p->adivex]){ //若vj未访问过
69                 printf("visitvertex：％c",C->adjlistlp->adjvex].vertex); //访问vj
70                 visited[p->adjvex] = TRUE;
71                 EnQueue(&Q, p->adjvex);//访问过的vj人队
72             }//endif
73             p = p->next;//找vi的下一邻接点
74         }//endwhile
75     }//endwhile
76 }//end of BFS

View Code

3/11/2015 9:52:47 AM