图(邻接矩阵)

 1 #include <iostream>
 2 using namespace std;
 3 
 4 #define INFINITY  10000
 5 #define MAX_VERTEX_NUM  20
 6  
 7 /************************************************************************/
 8 /* 图的邻接矩阵表示法                                                   */
 9 /************************************************************************/
10 typedef struct  AcrCell
11 {
12   int adj;    // 顶点关系 无向图 0 或 1
13   char * info; // 弧的相关信息
14 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
15 
16 typedef struct 
17 {
18    char vexs[MAX_VERTEX_NUM]; //顶点向量
19    AdjMatrix  arcs;            //邻接矩阵
20    int vexnum, arcnum;        //图的当前顶点数和弧数
21 }MGraph;
22 
23 
24 int Locate_vexs(MGraph g,char v)
25 {
26   for(int i=0;i<g.vexnum;i++)
27   {  
28         if(g.vexs[i]==v)
29         {
30             return i;
31         }
32   }  
33   return -1;
34 }
35 
36 void CreateUDN(MGraph &G)
37 {  
38     char v1 = 0;
39     char v2 = 0;
40     int g_width = 0;
41 
42    cout<<"请输入有向图的顶点个数和弧的条数"<<endl;
43    cin>>G.vexnum>>G.arcnum;
44    cout<<"请输入顶点种类"<<endl;
45 
46     for(int i=0;i<G.vexnum;i++)
47     {
48          cin>>G.vexs[i];
49     }
50    
51     G.vexs[i] = '\0';
52    for (i=0;i<G.vexnum;i++) //初始化邻接矩阵
53    {
54          for(int j=0;j<G.arcnum;j++)
55          {
56              G.arcs[i][j].adj = INFINITY;
57              G.arcs[i][j].info = NULL;
58          }
59    }
60   
61    cout<<"请输入弧的长度和对应的两个顶点"<<endl;
62 
63        for(int k=0;k<G.arcnum;k++)
64        {                    
65            cin>>g_width>>v1>>v2;
66            int i = Locate_vexs(G,v1);
67            int  j = Locate_vexs(G,v2);
68           G.arcs[i][j].adj = g_width;
69        }
70 }
71 
72 
73 void Display(MGraph &g)
74 {
75 
76    for(int i=0;i<g.vexnum;i++)
77    {
78        for(int j=0;j<g.arcnum;j++)
79        {    
80              cout<<g.arcs[i][j].adj<<"";
81        }
82         cout<<endl;
83    }
84 }
85 
86 int main()
87 {
88  MGraph g;
89  cout<<"创建一个有向图"<<endl;
90  CreateUDN(g); 
91  Display(g);
92  return 0;
93 }