Code666 (代码贴、代码片段)

[C++] 数据结构与算法----4.3 用邻接表储存图1、求一个顶点的入度2、求一个顶点的 →→→→→进入此内容的聊天室

来自 , 2019-04-02, 写在 C++, 查看 127 次.
URL http://www.code666.cn/view/0ae3f79a
  1. #include<iostream>
  2. using namespace std;
  3. const int MVN = 21;
  4. typedef char VexType;//顶点元素类型
  5. typedef struct ArcNode
  6. {
  7.         int adjvex;//弧指向的顶点位置
  8.         int adj;//权
  9.         ArcNode *nextarc;//指向下一条弧的顶点
  10. }*ArcPtr;
  11. struct VexNode
  12. {
  13.         VexType data;//顶点数据
  14.         ArcPtr firstarc;//指向第一条依附于该顶点的弧
  15.         bool visited;//是否被访问过
  16. };
  17. struct ALGraph
  18. {
  19.         VexNode vexs[MVN];
  20.         int kind, vexnum, arcnum;//类型，顶点数，弧数
  21. };
  22. int LocateVex(ALGraph &G, VexType v);//查找顶点
  23. bool InsertArc(ALGraph &G, VexType u, VexType v, int w = 1);//插入弧
  24. void CreateGraph(ALGraph &G, int Kind, char v[]);
  25. void GraphPrint(ALGraph &G);
  26. int Outdegree(ALGraph &G, VexType u);//求一个顶点的出度
  27. int Indegree(ALGraph &G, VexType u);//求一个顶点的入度
  28. int* degree(ALGraph &G);//求全部顶点的入度
  29.  
  30. int main()
  31. {
  32.         char g[] = "sbcd#sbscsdbcbdcd#";
  33.         cout << "序列为 "<< endl<<g<< endl;
  34.         int Kind = 1;
  35.         ALGraph G;
  36.         CreateGraph(G, Kind, g);
  37.         GraphPrint(G);
  38.         VexType u = 's';
  39.         int n = Outdegree(G, u);
  40.         cout << "顶点"<<u<<"的出度为" << n << endl;
  41.         VexType v = 'c';
  42.         int m = Indegree(G, v);
  43.         cout << "顶点"<<v<<"的入度为" << m << endl;
  44.         int *a = degree(G);
  45.         cout << "各个顶点的入度依次为:";
  46.         for (int j = 1; j <= G.vexnum; j++)
  47.         {
  48.                 cout << a[j] << "  ";
  49.         }
  50.         cout << endl;
  51.  
  52.         return 0;
  53. }
  54. int LocateVex(ALGraph &G, VexType v)
  55. {
  56.         int i;
  57.         for (i = G.vexnum; i>0 && G.vexs[i].data != v; i--);
  58.         return i;
  59. }
  60. bool InsertArc(ALGraph &G, VexType u, VexType v, int w )
  61. {
  62.         ArcPtr p;
  63.         int i, j;
  64.         bool found;
  65.         i = LocateVex(G, u);
  66.         if (i == 0)
  67.         {
  68.                 return false;
  69.         }
  70.         j = LocateVex(G, v);
  71.         if (j == 0 || j == i)
  72.         {
  73.                 return false;
  74.         }
  75.         for (found = false, p = G.vexs[i].firstarc; p && !found; p = p->nextarc)
  76.         {
  77.                 if (p->adjvex == j)
  78.                 {
  79.                         found = true;
  80.                 }
  81.         }
  82.         if (found)
  83.         {
  84.                 return false;
  85.         }
  86.         G.arcnum++;
  87.         p = new ArcNode;
  88.         p->adjvex = j;
  89.         p->adj = w;
  90.         p->nextarc = G.vexs[i].firstarc;
  91.         G.vexs[i].firstarc = p;
  92.         if (G.kind <= 2)
  93.         {
  94.                 return true;
  95.         }
  96.         G.arcnum++;
  97.         p = new ArcNode;
  98.         p->adjvex = i;
  99.         p->adj = w;
  100.         p->nextarc = G.vexs[j].firstarc;
  101.         G.vexs[j].firstarc = p;
  102.         return true;
  103. }
  104. void CreateGraph(ALGraph &G, int Kind, char v[])
  105. {
  106.         int i, w;
  107.         G.kind = Kind;
  108.         G.arcnum = 0;
  109.         i = 0;
  110.         while (true)
  111.         {
  112.                 if (v[i] == '#')
  113.                 {
  114.                         break;
  115.                 }
  116.                 i++;
  117.                 G.vexs[i].data = v[i - 1];
  118.                 G.vexs[i].firstarc = NULL;
  119.         }
  120.         G.vexnum = i;
  121.         i++;
  122.         while (true)
  123.         {
  124.                 if (v[i] == '#')
  125.                 {
  126.                         break;
  127.                 }
  128.                 if (G.kind == 1 || G.kind == 3)
  129.                 {
  130.                         w = 1;
  131.                 }
  132.                 else
  133.                 {
  134.                         w = v[i + 2] - 48;
  135.                 }
  136.                 InsertArc(G, v[i], v[i + 1], w);
  137.                 i = i + 2;
  138.                 if (w == 2 || w == 4)
  139.                 {
  140.                         i++;
  141.                 }
  142.         }
  143.  
  144. }
  145. void GraphPrint(ALGraph &G)
  146. {
  147.         ArcPtr p;
  148.         cout << "邻接表" << endl;
  149.         for (int i = 1; i <= G.vexnum; i++)
  150.         {
  151.                 cout << G.vexs[i].data;
  152.                 for (p = G.vexs[i].firstarc; p; p = p->nextarc)
  153.                 {
  154.                         cout << "->" << p->adjvex;
  155.                 }
  156.                 cout << endl;
  157.         }
  158. }
  159. int Outdegree(ALGraph &G, VexType u)
  160. {
  161.         int i = LocateVex(G, u);
  162.         int n = 0;
  163.         ArcPtr p;
  164.         for (p = G.vexs[i].firstarc; p; p = p->nextarc)
  165.         {
  166.                 n++;
  167.         }
  168.         return n;
  169. }
  170. int Indegree(ALGraph &G, VexType u)
  171. {
  172.         int i = LocateVex(G, u);
  173.         int n = 0;
  174.         ArcPtr p;
  175.         for (int j = 1; j <= G.vexnum; j++)
  176.         {
  177.                 if (j == i)
  178.                 {
  179.                         continue;
  180.                 }
  181.                 for (p = G.vexs[j].firstarc; p; p = p->nextarc)
  182.                 {
  183.                         if (p->adjvex == i)
  184.                         {
  185.                                 n++;
  186.                                 break;
  187.                         }
  188.  
  189.                 }
  190.         }
  191.         return n;
  192. }
  193. int* degree(ALGraph &G)
  194. {
  195.         int *a;
  196.         a = new int[G.vexnum + 1];
  197.         for (int i = 1; i <= G.vexnum; i++)
  198.         {
  199.                 a[i] = 0;
  200.         }
  201.         ArcPtr p;
  202.         for (int j = 1; j <= G.vexnum; j++)
  203.         {
  204.                 for (p = G.vexs[j].firstarc; p; p = p->nextarc)
  205.                 {
  206.                         a[p->adjvex]++;
  207.                 }
  208.         }
  209.         return a;
  210. }

回复 "数据结构与算法----4.3 用邻接表储存图1、求一个顶点的入度2、求一个顶点的"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666