由于图的基本操作的代码较多，我放到这一章来写。图可以用两种方法来存储，但是本人偏爱链表的表示方法，所以以下代码也都是是基于邻接链表的存储方式。
1 /* 2 以下存储结构参考严蔚敏版数据结构，不懂的可以翻阅查看 3 */ 4 const int UNDIGRAPH = 0; //无向图 5 const int DIGRAPH = 1; //有向图 6 const int MAX_VERTEX_NUM = 20; 7 8 typedef struct ArchNode 9 {10 int vertexIndex; //该弧指向顶点在图中顶点数组的索引，对应vertexs[20]的下标11 ArchNode *nextarc; //指向下一条弧的指针12 InfoTypde info; //比如弧的权重13 }ArchNode;14 15 typedef struct Vertex16 {17 VertexType data; //顶点信息18 ArchNode *firstarc; //指向第一条弧的指针19 }Vertex;20 21 //这样定义图有个坏处，一旦定义好，图中结点的个数就固定了！22 typedef struct Graph23 {24 Vertex *vertexs[MAX_VERTEX_NUM]; //存储顶点的数组,存放的是指向顶点的指针25 int vexNum; //当前图中的定点数26 int arcNum; //当前图中的弧的个数27 int kind; //图的种类，有向图还是无向图28 }Graph; //图的创建
1 /* 2 初始条件：kind是图的类型，目前有有向图和无向图 两种. 3 返回值 ：无。---大部分函数都无返回值，是对图的引用进行操作的 4 */ 5 void createGraph(Graph *&G,int kind) 6 { 7 if(G) G = NULL; 8 G = (Graph *)malloc(sizeof(struct Graph)); 9 assert(NULL != G);10 for(int i = 0; i < MAX_VERTEX_NUM; ++i)11 {12 G->vertexs[i] = NULL; //初始化指向顶点的指针为NULL13 }14 G->kind = kind; //设置图的种类15 G->vexNum = 0; //初始化图中顶点的个数16 G->arcNum = 0; //初始化图中弧的个数17 } //图的销毁
1 /* 2 初始条件：G存在 3 返回值 ：无。---大部分函数都无返回值，是对图的引用进行操作的 4 */ 5 void destoryGraph(Graph *&G) 6 { 7 ArchNode *cur,*next; 8 if(NULL == G) 9 return;10 //遍历顶点11 for(int i = 0; i < G->vexNum; ++i)12 {13 if(!G->vertexs[i])14 continue;15 next = G->vertexs[i]->firstarc;16 cur = G->vertexs[i]->firstarc;17 while(cur)18 {19 next = cur->nextarc;20 free(cur);21 cur = next;22 }23 G->vertexs[i]->firstarc = NULL;24 }25 free(G);26 G = NULL;27 } //向图中增加结点
1 //向图中增加结点 2 /* 3 初始条件：G存在，data是结点的数据值 4 */ 5 void addVertexToGraph(Graph *&G,VertexType data) 6 { 7 if(G->vexNum >= MAX_VERTEX_NUM) 8 { 9 cout << "Too many vertex!" << endl;10 return ;11 }12 for(int i = 0; i < G->vexNum; ++i)13 {14 if(!G->vertexs[i])15 continue;16 if(G->vertexs[i]->data == data)17 {18 cout << "Already exists!" << endl;19 return; //不允许重复 20 }21 }22 Vertex *pVeterx;23 pVeterx = (Vertex *)malloc(sizeof(struct Vertex));24 pVeterx->data = data;25 pVeterx->firstarc = NULL;26 G->vertexs[G->vexNum] = pVeterx;27 G->vexNum++;28 } //从图中删除一个结点
1 void delVertexFromGraph(Graph *&G,VertexType data) 2 { 3 bool haveThisVertex = false; 4 ArchNode *cur,*next,*temp,*pre; 5 Vertex *anotherVertex; 6 if(NULL == G) 7 return; 8 if(G->vexNum <= 0) 9 {10 cout << "Have no vertex!" << endl;11 return ;12 }13 for(int i = 0; i < G->vexNum; ++i)14 {15 if(!G->vertexs[i])16 continue;17 if(G->vertexs[i]->data == data)18 {19 haveThisVertex = true;20 //以下循环用来删除顶点所指向的弧链表21 next = cur = G->vertexs[i]->firstarc;22 if(G->kind == DIGRAPH) //如果是有向图23 {24 while(cur)25 {26 next = cur->nextarc;27 free(cur);28 G->arcNum --; //弧的个数减一29 cur = next;30 }31 G->vertexs[i] = NULL;32 }33 else if(G->kind == UNDIGRAPH) //如果是无向图，这个麻烦点34 {35 while(cur)36 {37 //找到待删除的弧的另一个结点，将它的弧链表中指向被删除结点的弧也删掉38 anotherVertex = G->vertexs[cur->vertexIndex]; //找到待删除弧对应的另一个结点39 temp = anotherVertex->firstarc,pre = NULL;40 while(temp) //这个循环是为了删除另一个结点中保存弧信息41 {42 if(temp->vertexIndex == i)43 {44 //如果是首节点45 if(NULL == pre) //或者if(NULL == pre)46 {47 anotherVertex->firstarc = temp->nextarc;48 free(temp);49 }50 else51 {52 pre->nextarc = temp->nextarc;53 free(temp);54 }55 break; //找到即停止循环56 }57 pre = temp;58 temp = temp->nextarc;59 }60 next = cur->nextarc;61 free(cur);62 G->arcNum --; //弧的个数减一63 cur = next;64 }65 G->vertexs[i] = NULL;66 }67 for(int j = i; j < G->vexNum - 1; ++j)68 {69 G->vertexs[j] = G->vertexs[j + 1];70 }71 G->vertexs[j] = NULL; //72 G->vexNum-- ; //结点的个数减一73 break;74 }75 }76 if(!haveThisVertex)77 cout << "没有该结点！" << endl;78 } //从图中查找一个值为指定值的结点的索引
1 //初始条件：G存在，data是指定结点的数据值 2 int findVertexIndexInGraph(const Graph *G,VertexType data) 3 { 4 if(NULL == G) 5 return -1; 6 for(int i = 0; i < G->vexNum; ++i) 7 { 8 if(!G->vertexs[i]) 9 continue;10 if(G->vertexs[i]->data == data)11 {12 return i;13 break;14 }15 }16 return -1;17 } //向图中增加一条弧，有有向图和无向图之分
1 //初始条件：G存在，指定起始点，和弧的权重 2 void addArchToGraph(Graph *&G,VertexType startData,VertexType endData,InfoTypde weight = 0) 3 { 4 ArchNode *pArchNode,*cur; 5 //先要找到start和end 6 if(NULL == G) 7 return; 8 int startVertexIndex = findVertexIndexInGraph(G,startData); 9 int endVertexIndex = findVertexIndexInGraph(G,endData);10 cur = G->vertexs[startVertexIndex]->firstarc;11 while(cur)12 {13 if(cur->vertexIndex == endVertexIndex)14 {15 cout << "Already have this arch!" << endl;16 return ;17 }18 cur = cur->nextarc;19 }20 if(startVertexIndex >= 0 && endVertexIndex >= 0)21 {22 if(G->kind == DIGRAPH) //如果是有向图23 {24 pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode)); //创建一个弧结点25 pArchNode->info = weight;26 pArchNode->nextarc = NULL;27 pArchNode->vertexIndex = endVertexIndex;28 cur = G->vertexs[startVertexIndex]->firstarc;29 if(NULL == cur)30 {31 G->vertexs[startVertexIndex]->firstarc = pArchNode;32 }33 else34 {35 while(cur->nextarc)36 {37 cur = cur->nextarc;38 }39 cur->nextarc = pArchNode;40 }41 G->arcNum ++; //弧的条数加一42 }43 else if(G->kind == UNDIGRAPH) //如果是无向图44 {45 pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode)); //创建一个弧结点46 pArchNode->info = weight;47 pArchNode->nextarc = NULL;48 pArchNode->vertexIndex = endVertexIndex;49 cur = G->vertexs[startVertexIndex]->firstarc;50 if(NULL == cur)51 {52 G->vertexs[startVertexIndex]->firstarc = pArchNode;53 }54 else55 {56 while(cur->nextarc)57 {58 cur = cur->nextarc;59 }60 cur->nextarc = pArchNode;61 }62 pArchNode = (ArchNode *)malloc(sizeof(struct ArchNode)); //再创建一个弧结点63 pArchNode->info = weight;64 pArchNode->nextarc = NULL;65 pArchNode->vertexIndex = startVertexIndex;66 cur = G->vertexs[endVertexIndex]->firstarc;67 if(NULL == cur)68 {69 G->vertexs[endVertexIndex]->firstarc = pArchNode;70 }71 else72 {73 while(cur->nextarc)74 {75 cur = cur->nextarc;76 }77 cur->nextarc = pArchNode;78 }79 G->arcNum ++; //弧的条数加一80 }81 }82 else83 {84 cout << "起点或终点不存在！" << endl;85 return ;86 }87 } //从图中删除一条弧
1 //初始条件：G存在，指定要删除弧连接的两个顶点 2 void delArchFromGraph(Graph *&G,VertexType startData,VertexType endData) 3 { 4 ArchNode *cur,*pre; 5 //先要找到start和end 6 if(NULL == G) 7 return; 8 int startVertexIndex = findVertexIndexInGraph(G,startData); 9 int endVertexIndex = findVertexIndexInGraph(G,endData);10 if(startVertexIndex >= 0 && endVertexIndex >= 0)11 {12 if(G->kind == DIGRAPH)13 {14 cur = G->vertexs[startVertexIndex]->firstarc,pre = NULL;15 while(cur)16 {17 if(cur->vertexIndex == endVertexIndex)18 {19 break;20 }21 pre = cur;22 cur = cur->nextarc;23 }24 if(NULL == cur)25 {26 cout << "这两个结点之间没有弧！" << endl;27 return ;28 }29 else30 {31 if(NULL == pre) //是首节点32 G->vertexs[startVertexIndex]->firstarc = cur->nextarc;33 else34 pre->nextarc = cur->nextarc;35 free(cur);36 G->arcNum --;37 }38 }39 else if(G->kind == UNDIGRAPH)40 {41 cur = G->vertexs[startVertexIndex]->firstarc,pre = NULL;42 while(cur)43 {44 if(cur->vertexIndex == endVertexIndex)45 {46 break;47 }48 pre = cur;49 cur = cur->nextarc;50 }51 if(NULL == cur)52 {53 cout << "这两个结点之间没有弧！" << endl;54 return ;55 }56 else57 {58 if(NULL == pre) //是首节点59 G->vertexs[startVertexIndex]->firstarc = cur->nextarc;60 else61 pre->nextarc = cur->nextarc;62 free(cur);63 //G->arcNum --;64 }65 66 cur = G->vertexs[endVertexIndex]->firstarc,pre = NULL;67 while(cur)68 {69 if(cur->vertexIndex == startVertexIndex)70 {71 break;72 }73 pre = cur;74 cur = cur->nextarc;75 }76 if(NULL == cur)77 {78 cout << "这两个结点之间没有弧！" << endl;79 return ;80 }81 else82 {83 if(NULL == pre) //是首节点84 G->vertexs[endVertexIndex]->firstarc = cur->nextarc;85 else86 pre->nextarc = cur->nextarc;87 free(cur);88 G->arcNum --;89 }90 }91 }92 else93 {94 cout << "起点或终点不存在！" << endl;95 return ;96 }97 } //深度优先遍历
1 //初始条件：图G存在 2 void DFSdetails(const Graph *G,int i,int satusArr[]) 3 { 4 ArchNode *cur; 5 if(satusArr[i] == 1 ) 6 return; 7 cout << G->vertexs[i]->data << " "; 8 satusArr[i] = 1; 9 cur = G->vertexs[i]->firstarc;10 while(cur)11 {12 DFSdetails(G,cur->vertexIndex,satusArr);13 cur = cur->nextarc;14 }15 }16 17 void DFS(const Graph *G)18 {19 int satusArr[MAX_VERTEX_NUM] = { 0};20 cout << "深度优先遍历：";21 if(NULL == G)22 return;23 for(int i = 0; i < G->vexNum; ++i)24 {25 DFSdetails(G,i,satusArr);26 }27 cout << endl;28 }