[关闭]
@skyword 2017-06-03T02:59:46.000000Z 字数 7048 阅读 1305

第十一次上机报告

问题描述

邻接表存图

  1. 实现基本函数和测试函数，以8-17为例
  2. 设计邻接表存图下的DFS,BFS函数
  3. 编写删除结点的函数

处理思路

邻接表存图：对于图中每个结点，维护一个链表，存储该点的各个邻接点
DFS：深度优先搜索，在每个结点，沿每条路径向内遍历并输出，没有后继结点时回溯
BFS：队列实现
删除点：首先对于要删除的点u，查找所有的邻接点v，调用删边函数delete_edge(u,v)。其次对于所有其他结点v，查找其邻接点中是否有u，若有，删除边（v,u），最后G->V--，即图中结点数目减一

代码设计

ADJD.h

main.cpp 测试主程序
没有额外函数

程序代码

ADJD.h

  1. #ifndef ADJD_H_INCLUDED
  2. #define ADJD_H_INCLUDED
  4. #include <cstdio>
  5. #include <iostream>
  6. #include <queue>
  7. using namespace std;
  8. #define Max_V 20
  9. typedef struct node
  10. {
  11.     int head;
  12.     node* nxt;
  13. } edge; //for edge in adj_graph
  15. typedef struct
  16. {
  17.     char val;
  18.     int start;
  19.     edge* adj;//head node of adj list for each node
  20. } Adj_List_Ele;
  22. typedef struct
  23. {
  24.     int V;
  25.     int E;
  26.     Adj_List_Ele L[Max_V];
  27.     void Adj_Graph_Init();
  28.     void Adj_Destroy();
  29.     void print();
  30.     void print_vertex(int index, int type);
  31.     void Adj_Delete_Vertex(int index);
  32. } Adj_Graph;
  34. void Adj_Graph::Adj_Graph_Init()
  35. {
  36.     this->E = 0;
  37.     this->V = 0;
  38.     for(int i = 0; i < Max_V; i++)//that is, we number vertex from 0
  39.     {
  40.         this->L[i].adj = NULL;
  41.         this->L[i].start = i;
  42.     }
  43. }
  45. void Adj_Graph::Adj_Destroy()
  46. {
  47.     edge* p,* q;
  48.     for(int i = 0; i < this->V; i++)
  49.     {
  50.         p = this->L[i].adj;
  51.         while(p != NULL)
  52.         {
  53.             q = p->nxt;
  54.             free(p);
  55.             p = q;
  56.         }
  57.     }
  58. }
  60. void Adj_Insert_Vertex(Adj_Graph* G, int index, char val)//add a vertex whose value = val, numbered index.
  61. {
  62.     if(index >= 0 && index < Max_V)
  63.     {
  64.         G->L[index].val = val;
  65.         G->V ++;
  66.     }
  67.     else printf("Add vertex failed. Its index should between 0 ~ %d.\n",Max_V-1);
  68. }
  70. void Adj_Insert_Edge(Adj_Graph* G, int s, int t)//add an edge from s to t
  71. {
  72.     if(s < 0 || t < 0 || s >= G->V || t >= G->V)
  73.     {
  74.         printf("Add edge failed. The index of these two vertex should between 0 ~ %d.\n",(G->V)-1);
  75.         return;
  76.     }
  77.     edge* p;
  78.     p = (edge*)malloc(sizeof(edge));
  79.     p->head = t;
  80.     p->nxt = G->L[s].adj;
  81.     G->L[s].adj = p;
  82.     G->E ++;
  83. }
  85. void Adj_Delete_Edge(Adj_Graph* G, int s, int t, int type)//delete edge from s to t
  86. //Here, type is operation type; type = 0 means using this function manually, type = 1 means using this function by other functions
  87. {
  88.     if(s < 0 || t < 0 || s >= G->V || t >= G->V)
  89.     {
  90.         printf("Delete edge failed. The index of these two vertex should between 0 ~ %d.\n",(G->V)-1);
  91.         return;
  92.     }
  93.     edge* pre, *now;
  94.     pre = NULL;
  95.     now = G->L[s].adj;
  96.     while(now != NULL && now->head != t)
  97.     {
  98.         pre = now;
  99.         now = now->nxt;
  100.     }
  101.     if(now != NULL && pre == NULL && now->head == t)//pre is null means t is the first link-node of v1
  102.     {
  103.         G->L[s].adj = now->nxt;
  104.         free(now);
  105.         G->E --;
  106.     }
  107.     else if(now != NULL && now->head == t)//we find t, but t is not the first link-node of v1
  108.     {
  109.         pre->nxt = now->nxt;//jump off "now"
  110.         free(now);
  111.         G->E --;
  112.     }
  113.     else
  114.     {
  115.         if(type == 0)printf("There isn't an edge from %d to %d, though graph G has these two vertexes in it.\n",s,t);
  116.     }
  117. }
  119. int Adj_GetFirst(Adj_Graph* G, int index)//get the first node of v
  120. {
  121.     if(index < 0 || index >= G->V)printf("The index should between 0 and %d.\n",(G->V)-1);
  122.     edge* p;
  123.     p = G->L[index].adj;
  124.     if(p == NULL)return -1;
  125.     else return p->head;
  126. }
  128. int Adj_GetSecond(Adj_Graph* G, int index1, int index2)
  129. {
  130.     if(index1 < 0 || index1 >= G->V || index2 < 0 || index2 >= G->V)
  131.     {
  132.         printf("The index should between 0 and %d.\n",(G->V)-1);
  133.         return 0;
  134.     }
  136.     edge* p;
  137.     p = G->L[index1].adj;
  138.     while(p->head != NULL)
  139.     {
  140.         if(p->head != index2)
  141.         {
  142.             p = p->nxt;
  143.         }
  144.         else break;
  145.     }
  146.     p = p->nxt;
  147.     if(p != NULL)return p->head;
  148.     else return -1;
  149. }
  151. void Adj_Graph::Adj_Delete_Vertex(int index)//delete single vertex in graph
  152. {
  153.     if(index < 0 || index >= this->V)
  154.     {
  155.         printf("The index should between 0 and %d.\n",(this->V)-1);
  156.         return;
  157.     }
  158.     edge* e;
  159.     e = this->L[index].adj;
  160.     while(e != NULL)
  161.     {
  162.         Adj_Delete_Edge(this, index, e->head, 1);
  163.         e = e->nxt;
  164.     }
  165.     //cout<<"****"<<endl;
  166.     for(int i = 0; i < this->V; i++)
  167.     {
  168.         if(i == index)continue;
  169.         e = this->L[i].adj;
  170.         while(e != NULL)
  171.         {
  172.             if(e->head != index)
  173.                 e = e->nxt;
  174.             else
  175.             {
  176.                 Adj_Delete_Edge(this, i, e->head, 1);
  177.                 break;
  178.             }
  179.         }
  180.     }
  181.     this->L[index].val='#';
  182.     /*
  183.     for(int i = 0; i < this->V; i++)
  184.     {
  185.         if(i != index)continue;
  186.         //now i == index
  187.         else
  188.         {
  189.             for(int j = i+1; j < this->V; j++)
  190.             {
  191.                 this->L[j-1] = this->L[j];
  192.                 //int now = this->L[j-1].adj->nxt->head;
  193.                 //printf("****%c ",this->L[now].val);
  194.             }
  195.             break;
  196.         }
  197.     }
  198.     */
  199.     //this->V--;
  200. }
  201. void Adj_Graph::print()
  202. //print graph by order following: print each link-node for each node ordered by index
  203. {
  204.     for(int i = 0; i < this->V; i++)
  205.     {
  206.         if(this->L[i].val == '#')continue;
  207.         printf("Vertex #%d : %c \n",i,this->L[i].val);
  208.         printf("It's suffix vertex: ");
  209.         edge* n;
  210.         n = (edge*)malloc(sizeof(edge));
  211.         n = this->L[i].adj;
  212.         int cnt = 0;
  213.         while(n != NULL)
  214.         {
  215.             cnt++;
  216.             int now = n->head;
  217.             n = n->nxt;
  218.             printf("%c ",this->L[now].val);
  219.         }
  220.         if(cnt == 0)printf("empty.");
  221.         printf("\n");
  222.     }
  223. }
  225. void Adj_Graph::print_vertex(int index, int type)
  226. //print single vertex of graph, type = 0 means manually using, type = 1 means by other functions
  227. {
  228.     char c = this->L[index].val;
  229.     if(c == '#')return;
  230.     else printf("%c",this->L[index].val);
  231.     if(type == 0)printf("\n");
  232.     else printf(" ");
  233. }
  234. //Search by DFS and BFS
  235. void Adj_DFS(Adj_Graph* G, int v, int vis[])
  236. {
  237.     int nxt;
  238.     vis[v] = 1;
  239.     G->print_vertex(v, 1);
  240.     nxt = Adj_GetFirst(G, v);
  241.     while(nxt != -1)
  242.     {
  243.         if(vis[nxt] == 0) Adj_DFS(G, nxt, vis);
  244.         nxt = Adj_GetSecond(G, v, nxt);
  245.     }
  246. }
  247. void Adj_BFS(Adj_Graph* G, int v, int vis[])
  248. {
  249.     int u,w;
  250.     queue<int>q;
  251.     vis[v] = 1;
  252.     G->print_vertex(v, 1);
  253.     q.push(v);
  254.     while(!q.empty())
  255.     {
  256.         u = q.front();
  257.         q.pop();
  258.         w = Adj_GetFirst(G, u);
  259.         while(w != -1)
  260.         {
  261.             if(vis[w] == 0)
  262.             {
  263.                 vis[w] = 1;
  264.                 G->print_vertex(w, 1);
  265.                 q.push(w);
  266.             }
  267.             w = Adj_GetSecond(G, u, w);
  268.         }
  269.     }
  270. }
  271. #endif // ADJD_H_INCLUDED

main.cpp

  1. #include <malloc.h>
  2. #include <cstdio>
  3. #include <iostream>
  4. #include <cstring>
  5. #include "ADJD.h"
  6. using namespace std;
  8. int vis[20]={0};
  9. int main()
  10. {
  11.     Adj_Graph* G;
  12.     G = (Adj_Graph*)malloc(sizeof(Adj_Graph));
  13.     G->Adj_Graph_Init();
  14.     //Insert 6 vertexes as the graph described.
  15.     for(int i = 0; i < 6; i++)
  16.     {
  17.         char c = 'A'+i;
  18.         Adj_Insert_Vertex(G, i, c);
  19.     }
  20.     Adj_Insert_Edge(G, 5, 0); Adj_Insert_Edge(G, 4, 0); Adj_Insert_Edge(G, 0, 1);
  21.     Adj_Insert_Edge(G, 2, 1); Adj_Insert_Edge(G, 3, 2); Adj_Insert_Edge(G, 1, 3);
  22.     Adj_Insert_Edge(G, 3, 4); Adj_Insert_Edge(G, 5, 4); Adj_Insert_Edge(G, 1, 5);
  23.     Adj_Insert_Edge(G, 2, 5); Adj_Insert_Edge(G, 3, 5);
  24.     G->print();
  25.     //Illegally adding vertex
  26.     Adj_Insert_Vertex(G, 21, 'd');
  27.     //Illegally adding edge
  28.     Adj_Insert_Edge(G, 5, 9);
  29.     //Delete an edge,legally and illegally
  30.     //printf("Delete edge from 0 to 1.\n");
  31.     //Adj_Delete_Edge(G, 0, 1, 0);
  32.     //G->print();
  33.     //Adj_Delete_Edge(G, 0, 1, 0);
  34.     //Adj_Delete_Edge(G, 0, 9, 0);
  35.     //printf("**%d",Adj_GetFirst(G, 0));
  36.     printf("DFS-order of G: \n");
  37.     Adj_DFS(G, 0, vis);
  38.     printf("\n");
  39.     memset(vis, 0 , sizeof(vis));
  40.     printf("BFS-order of G: \n");
  41.     Adj_BFS(G, 0, vis);
  42.     printf("\n");
  43.     G->Adj_Delete_Vertex(0);
  44.     G->print();
  45. }

测试结果

基本函数

  1. Vertex #0 : A
  2. It's suffix vertex: B
  3. Vertex #1 : B
  4. It's suffix vertex: F D
  5. Vertex #2 : C
  6. It's suffix vertex: F B
  7. Vertex #3 : D
  8. It's suffix vertex: F E C
  9. Vertex #4 : E
  10. It's suffix vertex: A
  11. Vertex #5 : F
  12. It's suffix vertex: E A
  13. Add vertex failed. Its index should between 0 ~ 19.
  14. Add edge failed. The index of these two vertex should between 0 ~ 5.
  15. Delete edge from 0 to 1.
  16. Vertex #0 : A
  17. It's suffix vertex: empty.
  18. Vertex #1 : B
  19. It's suffix vertex: F D
  20. Vertex #2 : C
  21. It's suffix vertex: F B
  22. Vertex #3 : D
  23. It's suffix vertex: F E C
  24. Vertex #4 : E
  25. It's suffix vertex: A
  26. Vertex #5 : F
  27. It's suffix vertex: E A
  28. There isn't an edge from 0 to 1, though graph G has these two vertexes in it.
  29. Delete edge failed. The index of these two vertex should between 0 ~ 5.

搜索

  1. Vertex #0 : A
  2. It's suffix vertex: B
  3. Vertex #1 : B
  4. It's suffix vertex: F D
  5. Vertex #2 : C
  6. It's suffix vertex: F B
  7. Vertex #3 : D
  8. It's suffix vertex: F E C
  9. Vertex #4 : E
  10. It's suffix vertex: A
  11. Vertex #5 : F
  12. It's suffix vertex: E A
  13. DFS-order of G:
  14. A B F E D C
  15. BFS-order of G:
  16. A B F D E C
  18. Process returned 0 (0x0)   execution time : 0.034 s
  19. Press any key to continue.

删点

  1. Delete vertex F
  2. Vertex #0 : A
  3. It's suffix vertex: B
  4. Vertex #1 : B
  5. It's suffix vertex: D
  6. Vertex #2 : C
  7. It's suffix vertex: B
  8. Vertex #3 : D
  9. It's suffix vertex: E C
  10. Vertex #4 : E
  11. It's suffix vertex: A
  13. Process returned 0 (0x0)   execution time : 0.022 s
  14. Press any key to continue.
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注