图的引子和数据结构以及相关的操作

时间:2021-11-02 10:21:56

本博客的代码的思想和图片参考:好大学慕课浙江大学陈越老师、何钦铭老师的《数据结构》

Graph

1 What is the graph

1.1 Graph Definition

a) show the relationship of many to many

b) contain:

1.a group of terminal points: use the V(Vertex)stand for the collection of vertex

2.a group of edges: using the E(Edge) to stand for the collection of terminal edges

 

edge:edge is the two vertex connection. For example:

No direction edge is use(v,w) to stand for a path v and w can reach each other. Direction edge is use<v,w> to stand for a path from v to w. We don’t think repeat edge and self path.

 图的引子和数据结构以及相关的操作

 

 图的引子和数据结构以及相关的操作

图的引子和数据结构以及相关的操作

 

 

 

The number in the edge is the weight of the edge. For example,we can use those number stand for the distance between the two vertexes.

We call the graph with weight as the network.

图的引子和数据结构以及相关的操作

 

 

 

 

 

2 Define Abstract Data Type and Operate

2.1 Date Type Name

图:Graph

 

2.2 The Collection of the Data Type

G(V,E) is not null,contains limited points’ collection and limited edges’ collection.

2.3 The Collection of Operate

Operation Collections

a):

   /*build a empty graph then return*/

q Graph Create();

 

b):

   /*insert a new vertex into the graph

*/

q Graph InsertVertex(Graph G, Vertex v);

 

c):

/*

insert a new edge into the graph

*/

q Graph InsertEdge(Graph G, Edge e);

 

d):

/* from the vertex v start, depth first search graph*/

q void DFS(Graph G, Vertex v);

 

e)

   /*from the vertex start,breadth first search graph*/

q void BFS(Graph G, Vertex v);

/*get min path from vertex v to other vertex*/

q void ShortestPath(Graph G, Vertex v, int Dist[]);

   

  /*calculate the min created tree*/

q void MST(Graph G);

......

 

3 How to show a graph using program

3.1 Adjacent Matrix

G[n][n]:There are N vertex from 0 to N-1 stored in the matrix

 

1 if<vi,vj> is the edge in the graph

G[i][i]=

0 if <vi,vj> is not edge in the graph

 

 

For example:

 图的引子和数据结构以及相关的操作

 

 

We find the matrix is symmetrical,So we only store halt of those data.

So we can use a one-dimensional array to stand for the above two-dimensional.

 图的引子和数据结构以及相关的操作

 

The one-dimensional length is n*(n+1)/2,The G(i,j) in the one-dimensional index is (i*(i+1)/2+ j ). If the graph is network,we just modify the 1 to the weight value.

 

 

3.1.1 The Advantages of Adjacent Matrix

图的引子和数据结构以及相关的操作

 

 

3.1.2 The Disadvantages of Adjacent Matrix

 图的引子和数据结构以及相关的操作

 

 

3.1.3 Sparse Matrix

In sparse matrix,the 0  element is too many.

3.2 Adjacent Table

We set a point to every vertex and let them to point the vertexes that they are adjacent. From following picture,we find we need N head point and 2*E(edge) node

For example:

 

 图的引子和数据结构以及相关的操作

 

 

Think this method is really reduce space?

From above picture,in no direction graph ,we store the node twice.4-->9 and 9-->4.It waste the space.But if the graph is very spare,we use the adjacent table is very reduce the space.But is the graph is not spare graph,the adjacent will waste many space.

 

3.2.1 The Advantage and the Disadvantage of Adjacent Table

 图的引子和数据结构以及相关的操作

 

 

 

 

3.2.2 Orthogonal List

We know we only get indegree(入度) from the adjacent table.If will want get outdegree(出度), we need construct reverse adjacent table. Is a link list can provide the tow advantage. We can try orthogonal list. Let’s see following picture.

 图的引子和数据结构以及相关的操作

3.3 What method we will chose?

From the above two ways,we can know: adjacent matrix store N vertex need N*(N+1)/2 space The adjacent table store N vertex need N + 2*E(edge)space.

If N*(N+1)/2 >= N+2*E

 

 

4 Data Structure Code and Insert Code of Graph

 

adjacent matrix:

图的引子和数据结构以及相关的操作图的引子和数据结构以及相关的操作
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 #define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
 5 #define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/
 6 
 7 typedef int vertex;        /*define the data type of the vertex*/
 8 typedef int weightType;    /*define the data type of the weight*/
 9 typedef char dataType; /*define the data type of the vertex value*/
10 
11 /*define the data structure of the Edge*/
12 typedef struct eNode *ptrToENode;
13 typedef struct eNode{
14     vertex v1,v2;           /*two vertex between the edge <v1,v2>*/
15     weightType weight;      /*the value of the edge's weigth */
16 };
17 typedef ptrToENode edge;
18 
19 /*define the data structure of the graph*/
20 typedef struct gNode *ptrToGNode;
21 typedef struct gNode{
22     int vertex_number;  /*the number of the vertex*/
23     int edge_nunber;    /*the number of the edge*/
24     weightType g[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   /*define the adjacent matrix of graph*/
25     dataType data[MAX_VERTEX_NUM];                  /*define the dataType array to store the value of vertex*/
26 };
27 typedef ptrToGNode adjacentMatrixGraph;             /*a graph show by adjacent matrix*/
28 
29 /*
30 create a graph given the vertex number.
31 @param vertexNum The verter number of the graph
32 @return a graph with vertex but no any egdgs
33 */
34 adjacentMatrixGraph createGraph(int vertexNum){
35     vertex v,w;
36     adjacentMatrixGraph graph;
37     graph =(adjacentMatrixGraph)malloc(sizeof(struct gNode));
38     graph->vertex_number=vertexNum;
39     graph->edge_nunber=0;
40     /*initialize the adjacent matrix*/
41     for(v=0;v<graph->vertex_number;v++){
42         for(w=0;w<graph->vertex_number;w++){
43             graph->g[v][w]= INFINITY;
44         }
45     }
46 
47     return graph;
48 }
49 
50 /*
51 insert a edge to graph.We will distinct oriented graph and undirected graph
52 @param graph The graph you want to insert edge
53 @param e The edge you want to insert the graph
54 @param isOriented Whether the graph is oriented graph.If the graph is oriented
55         we will set adjacent matrix [n][m]=[m][n]=edge's weight,else we only set
56         the adjacent matrix [n][m]=edge's weight
57 */
58 void inserEdge(adjacentMatrixGraph graph,edge e,int isOriented){
59     graph->g[e->v1][e->v2]=e->weight;
60     if(!isOriented){
61         graph->g[e->v2][e->v1]=e->weight;
62     }
63 }
64 
65 /*
66 construct a graph according user's input
67 
68 @return a graph has been filled good
69 */
70 adjacentMatrixGraph buildGraph(){
71     adjacentMatrixGraph graph;
72     edge e;
73     vertex v;
74     int vertex_num,i;
75     scanf("%d",&vertex_num);
76     graph = createGraph(vertex_num);
77     scanf("%d",&(graph->edge_nunber));
78     if(!graph->edge_nunber){
79         e = (edge)malloc(sizeof(struct eNode));
80         for(i=0;i<graph->edge_nunber;i++){
81             scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
82             inserEdge(graph,e,1);
83         }
84     }
85 
86     for(i=0;i<graph->vertex_number;i++){
87         scanf("%c",&(graph->data[i]));
88     }
89 
90     return graph;
91 
92 
93 }
94 
95 
96 int main(){
97     printf("just test");
98     return 0;
99 }
Adjacent Matrix

 

adjacent table

图的引子和数据结构以及相关的操作图的引子和数据结构以及相关的操作
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 #define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
  5 #define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/
  6 
  7 typedef int vertex;        /*define the data type of the vertex*/
  8 typedef int weightType;    /*define the data type of the weight*/
  9 typedef char dataType; /*define the data type of the vertex value*/
 10 
 11 /*define the data structure of the Edge*/
 12 typedef struct eNode *ptrToENode;
 13 typedef struct eNode{
 14     vertex v1,v2;           /*two vertex between the edge <v1,v2>*/
 15     weightType weight;      /*the value of the edge's weigth */
 16 };
 17 typedef ptrToENode edge;
 18 
 19 /*define the data structure adjacent table node*/
 20 typedef struct adjNode *ptrToAdjNode;
 21 typedef struct adjNode{
 22     vertex adjVerx;         /*the index of the vertex*/
 23     weightType weight;      /*the value of the weight*/
 24     ptrToENode next;        /*the point to point the next node*/
 25 };
 26 
 27 /*define the data structure of the adjacent head*/
 28 typedef struct vNode{
 29     ptrToAdjNode head;      /*the point to point the adjacent table node*/
 30     dataType data;          /*the space to store the name of the vertex,but some time the vertex has no names*/
 31 }adjList[MAX_VERTEX_NUM];
 32 
 33 /*define the data structure of graph*/
 34 typedef struct gNode *ptrToGNode;
 35 typedef struct gNode{
 36     int vertex_number;  /*the number of the vertex*/
 37     int edge_nunber;    /*the number of the edge*/
 38     adjList g;          /*adjacent table*/
 39 };
 40 typedef ptrToGNode adjacentTableGraph;             /*a graph show by adjacent table*/
 41 
 42 
 43 /*
 44 create a graph given the vertex number.
 45 @param vertexNum The verter number of the graph
 46 @return a graph with vertex but no any egdgs
 47 */
 48 adjacentTableGraph createGraph(int vertexNum){
 49     adjacentTableGraph graph;
 50 
 51     vertex v;
 52     graph =(adjacentTableGraph)malloc(sizeof(struct gNode));
 53     graph->vertex_number=vertexNum;
 54     graph->vertex_number=0;
 55     /*initialize the adjacent table*/
 56     for(v=0;v<graph->vertex_number;v++){
 57         graph->g[v].head=NULL;
 58     }
 59     return graph;
 60 }
 61 
 62 /*
 63 insert a edge to graph.We will distinct oriented graph and undirected graph
 64 The e->v1 and e->v2 are the vertexs' indexs in the adjacent table
 65 @param graph The graph you want to insert edge
 66 @param e The edge you want to insert the graph
 67 @param isOriented Whether the graph is oriented graph.If the graph is oriented
 68         we will set adjacent table graph[v1]->head=v2 and set graph[v1].head=v2
 69         otherwise we only set graph[v1].head=v2
 70 */
 71 void insertEdge(adjacentTableGraph graph,edge e,int isOriented){
 72     /*build node<v1,v2>*/
 73     ptrToAdjNode newNode;
 74     newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
 75     newNode->adjVerx=e->v1;
 76     newNode->weight=e->weight;
 77     newNode->next = graph->g[e->v1].head;
 78     graph->g[e->v1].head=newNode;
 79     /*if the graph is directed graph*/
 80     if(!isOriented){
 81         newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
 82         newNode->adjVerx=e->v1;
 83         newNode->weight = e->weight;
 84         newNode->next = graph->g[e->v2].head;
 85         graph->g[e->v1].head=newNode;
 86     }
 87 }
 88 
 89 /*
 90 build a graph stored by adjacent table
 91 */
 92 adjacentTableGraph buildGraph(){
 93     adjacentTableGraph graph;
 94     edge e;
 95     vertex v;
 96     int vertex_num,i;
 97 
 98     scanf("%d",&vertex_num);
 99     graph  = createGraph(vertex_num);
100     scanf("%d",(graph->edge_nunber));
101     if(!graph->edge_nunber){
102         e = (edge)malloc(sizeof(struct eNode));
103         for(i=0;i<graph->edge_nunber;i++){
104             scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
105             insertEdge(graph,e,1);
106         }
107     }
108 
109     /*if the vertex has name*/
110     for(i=0;i<graph->vertex_number;i++){
111         scanf("%c",&(graph->g[i].data));
112     }
113     return graph;
114 }
115 
116 
117 int main(){
118     printf("just test");
119 }
Adjacnet Table

 

 

 orthogonal list

图的引子和数据结构以及相关的操作图的引子和数据结构以及相关的操作
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 #define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
  5 #define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/
  6 
  7 typedef int vertex;        /*define the data type of the vertex*/
  8 typedef int weightType;    /*define the data type of the weight*/
  9 typedef char dataType; /*define the data type of the vertex value*/
 10 
 11 /*define the data structure of the Edge*/
 12 typedef struct eNode *ptrToENode;
 13 typedef struct eNode{
 14     vertex v1,v2;           /*two vertex between the edge <v1,v2>*/
 15     weightType weight;      /*the value of the edge's weigth */
 16 };
 17 typedef ptrToENode edge;
 18 
 19 /*define the data structure of the orthogonal list table node*/
 20 typedef struct adjNode *ptrToAdjNode;
 21 typedef struct adjNode{
 22     vertex tailVertex;      /*the inde of tail vertex*/
 23     vertex headVertex;      /*the index of the head vertex*/
 24     weightType weight;      /*the valie of the weight*/
 25     ptrToAdjNode hLink;     /*the point to point next node who point the head vertex*/
 26     ptrToAdjNode tLink;     /*the point to point next node who point the tail vertex*/
 27 };
 28 /*define the data structure of orthogonal list of head node*/
 29 typedef struct headNode{
 30     dataType data;          /*the space to store the name of the vertex,but some time the vertex has no names*/
 31     ptrToAdjNode firstin;   /*the point to point the in-degree node*/
 32     ptrToAdjNode firstout;   /*the point to poit the out-degree node*/
 33 }headList[MAX_VERTEX_NUM];
 34 
 35 typedef struct gNode *ptrToGNode;
 36 typedef struct gNode{
 37     int vertex_number;  /*the number of the vertex*/
 38     int edge_nunber;    /*the number of the edge*/
 39     headList head;
 40 };
 41 typedef ptrToGNode orthogonalList;
 42 
 43 /*
 44 create a graph given the vertex number.
 45 @param vertexNum The verter number of the graph
 46 @return a graph with vertex but no any egdgs
 47 */
 48 orthogonalList createGraph(int vertexNum){
 49     orthogonalList graph;
 50     vertex v;
 51     graph =(orthogonalList)malloc(sizeof(struct gNode));
 52     graph->vertex_number;
 53     graph->edge_nunber=0;
 54     for(v=0;v<graph->vertex_number;v++){
 55         graph->head[v].firstin=NULL;
 56         graph->head[v].firstout=NULL;
 57     }
 58     return graph;
 59 }
 60 
 61 /*
 62 insert a edge to graph.We will distinct oriented graph and undirected graph
 63 The e->v1 and e->v2 are the vertexs' indexs in the orthogoanlList
 64 @param graph The graph you want to insert edge
 65 @param e The edge you want to insert the graph
 66 */
 67 void insertEdge(orthogonalList graph,edge e){
 68     ptrToAdjNode newNode;
 69     newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
 70     newNode->tailVertex=e->v1;
 71     newNode->headVertex=e->v2;
 72     newNode->weight = e->weight;
 73     /*let v1 head's firstout point to the new node */
 74     newNode->tLink=graph->head[e->v1].firstout;
 75     graph->head[e->v1].firstout=newNode;
 76 
 77     /*let v2 head's firstin point to new node*/
 78     newNode->hLink=graph->head[e->v2].firstin;
 79     graph->head[e->v2].firstin=newNode;
 80 }
 81 
 82 /*
 83 build a graph stored by orthogonal list
 84 */
 85 orthogonalList buildGraph(){
 86     orthogonalList graph;
 87     edge e;
 88     vertex v;
 89     int vertex_num,i;
 90 
 91     scanf("%d",&vertex_num);
 92     graph = createGraph(vertex_num);
 93     scanf("%d",&(graph->edge_nunber));
 94     if(!graph->vertex_number){
 95         e = (edge)malloc(sizeof(struct eNode));
 96         for(i=0;i<graph->edge_nunber;i++){
 97             scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
 98             insertEdge(graph,e);
 99         }
100     }
101 
102     /*if the vertex has name,we will set it following*/
103     for(i=0;i<graph->vertex_number;i++){
104         scanf("%c",&(graph->head[i].data));
105     }
106     return graph;
107 }
108 int main(){
109     printf("just test");
110     return 0;
111 }
Orthogonal List

 

 The Search of Graph

5.1 Depth First Search(DFS)

we will introduce it by following picture:

 图的引子和数据结构以及相关的操作

5.2 Breadth First Search(BFS)

 

BFS is similar with the tree level search.We using follow picture to display it’s principle.

 图的引子和数据结构以及相关的操作

 

 

 

6 Special Graph

6.1

we maybe meet some graphs, that are don’t connect to all nodes.

If we use BFS or DFS to search,we we find some node will be be searched. How to solve this problem.

The following we will use Chinese to describe.

 

首先我们要引入一些概念:

连通:如果从VW存在一条(无向)路径,则VW是连通的。

路径VW的路径是一系列的顶点{V,v1,v2,v3....W},其中任意相邻的顶点都有图的边。路径的长度是路径中边数之和(如果有权重则是所有的权重之和),如果VW之间所有的顶点都不同,则称为简单路径  

回路:起点等于终点的路径

连通图:图中任意两点均连通。

 

6.2 图不连通怎么办

连通分量:无向图的极大连通子图

极大顶点数:再加一个顶点图就不连通了。

极大边数:包含子图中所有顶点相连的所有边

下面使用一个图片来说明

 图的引子和数据结构以及相关的操作

 

 

 

 

n 强连通:有向图中顶点VW之间存在双向路径,则称VW是强连通的

n 强连通图:有向图中任意两顶点均强连通

n 强连通分量:有向图的极大强连通子图

 

 

6.3 不连通的图如何进行BFSDFS

对于不连通的图,对BFS来说,之前我们需要遍历每个节点的邻接点,但是如果出现不连通的图,我们需要把遍历每个节点的邻接点改为遍历每个节点的极大连通子图。对于DFS,我们需要在遍历每个节点的邻接点时改为遍历每个节点的极大连通子图即可。

BFS和DFS的遍历算法,使用的邻接表作为存储图的数据结构

 

图的引子和数据结构以及相关的操作图的引子和数据结构以及相关的操作
  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 #define MAX_VERTEX_NUM 100 /*define the max number of the vertex*/
  5 #define INFINITY 65535     /*define double byte no negitive integer max number is 65535*/
  6 
  7 
  8 
  9 typedef int vertex;        /*define the data type of the vertex*/
 10 typedef int weightType;    /*define the data type of the weight*/
 11 typedef char dataType; /*define the data type of the vertex value*/
 12 
 13 //int visited[MAX_VERTEX_NUM];
 14 
 15 /*define the data structure of the Edge*/
 16 typedef struct eNode *ptrToENode;
 17 typedef struct eNode{
 18     vertex v1,v2;           /*two vertex between the edge <v1,v2>*/
 19     weightType weight;      /*the value of the edge's weigth */
 20 };
 21 typedef ptrToENode edge;
 22 
 23 /*define the data structure adjacent table node*/
 24 typedef struct adjNode *ptrToAdjNode;
 25 typedef struct adjNode{
 26     vertex adjVerx;         /*the index of the vertex*/
 27     weightType weight;      /*the value of the weight*/
 28     ptrToENode next;        /*the point to point the next node*/
 29 };
 30 
 31 /*define the data structure of the adjacent head*/
 32 typedef struct vNode *ptrToVNode;
 33 typedef struct vNode{
 34     ptrToAdjNode head;      /*the point to point the adjacent table node*/
 35     dataType data;          /*the space to store the name of the vertex,but some time the vertex has no names*/
 36 }adjList[MAX_VERTEX_NUM];
 37 
 38 /*define the data structure of graph*/
 39 typedef struct gNode *ptrToGNode;
 40 typedef struct gNode{
 41     int vertex_number;  /*the number of the vertex*/
 42     int edge_nunber;    /*the number of the edge*/
 43     adjList g;          /*adjacent table*/
 44 };
 45 typedef ptrToGNode adjacentTableGraph;             /*a graph show by adjacent table*/
 46 
 47 
 48 /*
 49 create a graph given the vertex number.
 50 @param vertexNum The verter number of the graph
 51 @return a graph with vertex but no any egdgs
 52 */
 53 adjacentTableGraph createGraph(int vertexNum){
 54     adjacentTableGraph graph;
 55 
 56     vertex v;
 57     graph =(adjacentTableGraph)malloc(sizeof(struct gNode));
 58     graph->vertex_number=vertexNum;
 59     graph->edge_nunber=0;
 60     /*initialize the adjacent table*/
 61     for(v=0;v<graph->vertex_number;v++){
 62         graph->g[v].head=NULL;
 63     }
 64     return graph;
 65 }
 66 
 67 /*
 68 insert a edge to graph.We will distinct oriented graph and undirected graph
 69 The e->v1 and e->v2 are the vertexs' indexs in the adjacent table
 70 @param graph The graph you want to insert edge
 71 @param e The edge you want to insert the graph
 72 @param isOriented Whether the graph is oriented graph.If the graph is oriented
 73         we will set adjacent table graph[v1]->head=v2 and set graph[v1].head=v2
 74         otherwise we only set graph[v1].head=v2
 75 */
 76 void insertEdge(adjacentTableGraph graph,edge e,int isOriented){
 77     /*build node<v1,v2>*/
 78     ptrToAdjNode newNode;
 79     newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
 80     newNode->adjVerx=e->v2;
 81     newNode->weight=e->weight;
 82     newNode->next = graph->g[e->v1].head;
 83     graph->g[e->v1].head=newNode;
 84     /*if the graph is directed graph*/
 85     if(!isOriented){
 86         newNode =(ptrToAdjNode)malloc(sizeof(struct adjNode));
 87         newNode->adjVerx=e->v1;
 88         newNode->weight = e->weight;
 89         newNode->next = graph->g[e->v2].head;
 90         graph->g[e->v1].head=newNode;
 91     }
 92 }
 93 
 94 /*
 95 build a graph stored by adjacent table
 96 */
 97 adjacentTableGraph buildGraph(){
 98     adjacentTableGraph graph;
 99     edge e;
100     vertex v;
101     int vertex_num,i;
102 
103     //printf("please input the quantity of the vertex:");
104     scanf("%d",&vertex_num);
105     graph  = createGraph(vertex_num);
106     //printf("please input the quantity of the edges:");
107     scanf("%d",&(graph->edge_nunber));
108     if(graph->edge_nunber){
109         e = (edge)malloc(sizeof(struct eNode));
110         for(i=0;i<graph->edge_nunber;i++){
111             scanf("%d %d %d",&e->v1,&e->v2,&e->weight);
112             insertEdge(graph,e,1);
113         }
114     }
115 
116     /*if the vertex has name*/
117     for(i=0;i<graph->vertex_number;i++){
118         scanf(" %c",&(graph->g[i].data));
119     }
120     //printf("lala:%c,%c\n",graph->g[0].data,graph->g[1].data);
121     //printf("lala:%d\n",graph->vertex_number);
122     //printf("%c",graph->g[1].data);
123     return graph;
124 }
125 
126 
127 
128 /*==============================define a queue=====================================================*/
129 /*define a list to store the element in the queue*/
130 typedef ptrToVNode elementType;
131 typedef struct node *pList;
132 typedef struct node{
133     elementType element;
134     struct node *next;
135 };
136 
137 /*define a queue to point the list*/
138 typedef struct node2 *pQueue;
139 typedef struct node2{
140     pList front;    /*the front point to point the head of the list*/
141     pList rear;     /*the rear point to point the rear of of the list*/
142 };
143 
144 /*create a empty list to store the queue element*/
145 pList createEmptyList(){
146     pList list;
147     list = (pList)malloc(sizeof(struct node));
148     list->next=NULL;
149     return list;
150 }
151 /*create a empty queye*/
152 pQueue createEmptyQueue(){
153     pQueue queue = (pQueue)malloc(sizeof(struct node2));
154     queue->front=NULL;
155     queue->rear=NULL;
156     return queue;
157 }
158 
159 /*
160 Wether the queue is empty
161 @param queue The queue need to adjust
162 @return If the queue is null,return 1 otherwise return 0
163 */
164 int isQueueEmpty(pQueue queue){
165     return(queue->front==NULL);
166 }
167 
168 /*
169 Add a element to a queue,If the queue is null,we will create a new queue
170 @parama queue The queue we will add elememt to
171 @prama element The element we will add to queue
172 */
173 void addQueue(pQueue queue,elementType element){
174     if(isQueueEmpty(queue)){
175         pList list = createEmptyList();
176         list->element=element;
177         queue->front=queue->rear=list;
178     }else{
179         pList newNode = (pList)malloc(sizeof(struct node));
180         newNode->element = element;
181         newNode->next = queue->rear->next;
182         queue->rear->next=newNode;
183         queue->rear=newNode;
184     }
185 }
186 
187 /*
188 delete a element from a queue
189 @param queue The queue will be deleted a element
190 @return The element has been deleted
191 */
192 elementType deleteEleFromQueue(pQueue queue){
193     if(isQueueEmpty(queue)){
194         printf("the queue is empty,don't allow to delete elemet from it!");
195     }else{
196         pList oldNode = queue->front;
197         elementType element = oldNode->element;
198         if(queue->front==queue->rear){
199             queue->rear=queue->front=NULL;
200         }else{
201             queue->front=queue->front->next;
202         }
203         free(oldNode);
204         return element;
205     }
206 }
207 
208 /*
209 visite a graph's node
210 @param graph The graph to store the elements
211 @param v The index of vertex in the adjacent table
212 */
213 void visit(adjacentTableGraph graph,vertex v){
214     printf("%c ",graph->g[v].data);
215 }
216 
217 /*
218 Breadth first search
219 @param graph The graph stored by the adjacent table
220 @param startPoint The point we start search 
221 @param visited A array to tag the elemeent whether has been visited
222 */
223 void BFS(adjacentTableGraph graph,vertex startPoint,int *visited){
224     ptrToAdjNode p;
225     //printf("lala:%d",graph->g[3].head->adjVerx);
226     visited[startPoint]=1;
227     visit(graph,startPoint);
228     pQueue queue = createEmptyQueue();
229     addQueue(queue,&(graph->g[startPoint]));
230     while(!isQueueEmpty(queue)){
231         elementType element = deleteEleFromQueue(queue);
232         //printf("lala:%d\n",element->head->adjVerx);
233         for(p=element->head;p;p=p->next){
234             if(visited[p->adjVerx]==0){
235                 visited[p->adjVerx]=1;
236                 visit(graph,p->adjVerx);
237                 addQueue(queue,&(graph->g[p->adjVerx]));
238             }
239         }
240     }
241 }
242 
243 /*
244 Depth first search a graph
245 @param graph The graph need to search
246 @param startPoint The fisrt point we start search the graph
247 @paran int *visited The array we use to tag the vertex we has accessed.
248 */
249 void DFS(adjacentTableGraph graph,vertex startPoint,int *visited){
250     ptrToAdjNode p;
251     visit(graph,startPoint);
252     p=graph->g[3].head;
253     //printf("lala%d",p->adjVerx);
254     visited[startPoint]=1;
255     for(p=graph->g[startPoint].head;p;p=p->next){
256         if(visited[p->adjVerx]==0){
257         //printf("lala:%d",p->adjVerx);
258             DFS(graph,p->adjVerx,visited);
259         }
260     }
261 }
262 
263 
264 
265 int main(){
266     int i;
267     adjacentTableGraph graph=buildGraph();
268     int visited[graph->vertex_number];
269     for(i=0;i<graph->vertex_number;i++){
270         visited[i]=0;
271     }
272     DFS(graph,0,visited);
273     printf("\n");
274     for(i=0;i<graph->vertex_number;i++){
275         visited[i]=0;
276     }
277     BFS(graph,0,visited);
278     printf("just test\n");
279     return 0;
280 }
DFS和BFS

 

测试数据:

图的引子和数据结构以及相关的操作

 

 图的引子和数据结构以及相关的操作

测试结果:

图的引子和数据结构以及相关的操作