Code666 (代码贴、代码片段)

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

来自 , 2020-11-27, 写在 C++, 查看 154 次.
URL http://www.code666.cn/view/16ba7217
  1. #include <iostream>
  2. #include <fstream>
  3. using namespace std;
  4. const int Infinity=-1;
  5. typedef char VexType;
  6. struct VexCell//顶点的信息
  7. {
  8.         VexType data;//顶点数据
  9.         bool visited;//是否被访问过
  10. };
  11. struct ArcCell//弧的信息
  12. {
  13.         int adj;    
  14. };
  15. const MVN=21;
  16. struct MGraph
  17. {
  18.         VexCell vexs[MVN];//顶点数组
  19.         ArcCell arcs[MVN][MVN];//邻接矩阵
  20.         int kind,vexnum,arcnum;//类型，顶点数，弧数
  21. };
  22. int LocateVex(MGraph &G,VexType v);//查找顶点
  23. bool InsertVex(MGraph &G,VexType u);//插入顶点
  24. bool InsertArc(MGraph &G,VexType u,VexType v,int w=1);//插入弧
  25. void CreateGraph(MGraph&G,char fn[]);//建立图
  26. int  qiuru(MGraph&G,VexType &x);//顶点的入度
  27. int  qiuchu(MGraph&G,VexType &x);//顶点的出度
  28. void Show(MGraph &G);
  29. int main()
  30. {
  31.         int count1=0;
  32.         int count2=0;
  33.         MGraph G;
  34.         VexType fn[]="fn.txt";
  35.         CreateGraph(G,fn);
  36.         Show(G);VexType x='a';
  37.         cout<<"顶点"<<x<<"的入度为："<<qiuru(G,x)<<endl;
  38.         cout<<"顶点"<<x<<"的出度为："<<qiuchu(G,x)<<endl;
  39.  
  40.  
  41.         return 0;
  42. }
  43.  
  44. bool InsertVex(MGraph&G,VexType u)
  45. {
  46.         int i;
  47.         if(G.vexnum+1>MVN)return false;
  48.         i=LocateVex(G,u);
  49.         if(i>0)return false;
  50.         G.vexnum++;
  51.         G.vexs[G.vexnum].data=u;
  52.         for(i=1;i<=G.vexnum;i++)
  53.                 G.arcs[i][G.vexnum].adj=G.arcs[G.vexnum][i].adj=Infinity;
  54.         return true;
  55. }
  56. bool InsertArc(MGraph&G,VexType u,VexType v,int w)
  57. {
  58.         int i,j;
  59.         i=LocateVex(G,u);if(i==0)return false;
  60.         j=LocateVex(G,v);
  61.         if(j==0||j==i||G.arcs[i][j].adj!=Infinity)return false;
  62.         G.arcs[i][j].adj=w;
  63.         G.arcnum++;
  64.         if(G.kind>=3)
  65.         {
  66.                 G.arcs[j][i].adj=w;
  67.             G.arcnum++;
  68.         }
  69.         return true;
  70. }
  71. int LocateVex(MGraph&G,VexType v)
  72. {
  73.         int i;
  74.         for(i=G.vexnum;i>0&&G.vexs[i].data!=v;i--);
  75.         return i;
  76. }
  77. void CreateGraph(MGraph&G,char fn[])
  78. {
  79.         int i,j,w;VexType u,v;ifstream f;
  80.         f.open(fn);f>>G.kind;i=0;
  81.         while(true)
  82.         {
  83.                 f>>u;if(u=='#')break; i++;G.vexs[i].data=u;
  84.         }
  85.         G.vexnum=i;
  86.         for(i=1;i<=G.vexnum;i++)
  87.                 for(j=1;j<=G.vexnum;j++) G.arcs[i][j].adj=Infinity;
  88.         G.arcnum=0;
  89.         while(true)//边
  90.         {
  91.                 f>>u>>v;if(u=='#'||v=='#')break;
  92.                 if(G.kind==1||G.kind==3)
  93.                         w=1;
  94.                 else f>>w;
  95.                 InsertArc(G,u,v,w);
  96.         }
  97.         f.close();
  98. }
  99. void Show(MGraph &G)
  100. {
  101.         int i=1,j=1;
  102.         cout<<"所有顶点为：";
  103.         for(i;i<=G.vexnum;i++)
  104.                 cout<<G.vexs[i].data<<" ";
  105.         cout<<endl<<"所有弧为：";
  106.         if(G.kind==1)
  107.         {
  108.                 for(i=1;i<=G.vexnum;i++)
  109.                         for(j=1;j<= G.vexnum;j++)
  110.                                 if(G.arcs[i][j].adj==1)
  111.                                         cout<<"<"<<G.vexs[i].data<<","<<G.vexs[j].data<<"> ";
  112.         }
  113.         else
  114.         {
  115.                 for(i=1;i<=G.vexnum;i++)
  116.                         for(j=1;j<i;j++)
  117.                                 if(G.arcs[i][j].adj==1)
  118.                                         cout<<"("<<G.vexs[i].data<<","<<G.vexs[j].data<<") ";
  119.         }
  120.         cout << endl;
  121. }
  122. int  qiuru(MGraph&G,VexType &x)
  123. {
  124.         int i,j;int count1=0;
  125.         i=LocateVex(G,x);
  126.         if(i==0)return -1;
  127.         for(j=1;j<=G.vexnum;j++)
  128.         {
  129.                 if(G.arcs[j][i].adj!=Infinity) count1++;
  130.         }
  131.         return count1;
  132. }
  133. int  qiuchu(MGraph&G,VexType &x)
  134. {
  135.         int i,j;int count2=0;
  136.         i=LocateVex(G,x);
  137.         if(i==0)return -1;
  138.         for(j=1;j<=G.vexnum;j++)
  139.         {
  140.                 if(G.arcs[i][j].adj!=Infinity) count2++;
  141.         }
  142.         return count2;
  143. }
  144.  
  145. //fn.txt
  146. 1
  147. a b c #
  148. a b
  149. b c
  150. a c
  151. # #

回复 "数据结构与算法----4.1 用数组存储图 1、求一个顶点的出度2、求一个顶点的"

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

captcha

贴代码片段 - Code666