图的邻接矩阵实现与C语言代码示例（第6讲）

 1 #include<iostream>
 2 using namespace std;
 3 /*使用邻接矩阵表示法创建无向图*/
 4 /**
 5  * 1、输入总顶点数和总边数
 6  * 2、依次输入点的信息存入顶点表中
 7  * 3、初始化邻接矩阵，使每个权值初始化为极大值 
 8  * 4、构造邻接矩阵。依次输入每条边依附的顶点和其权值，确定两个顶点在图中的位置之后，使相应边 
 9  * 赋予相应的权值，同时使其对称边赋予相同的权值。 
10  **/
11 /*图的邻接矩阵存储表示*/
12 #define MAXINT 32767      //表示的是极大值，即为无穷 
13 #define MVNum 100         //最大顶点数 
14 typedef char VerTexType;   //假设顶点的数据类型为字符类型 
15 typedef int ArcType;       //假设边的权值类型为整型
16 typedef struct AMGraph
17 {
18     VerTexType vexs[MVNum];  //顶点数 
19     ArcType arcs[MVNum][MVNum];  //邻接矩阵
20     int vexnum, arcunm;     //图当前的点数和边数 
21 }AMGraph; 
22 
23 int LocateVex(AMGraph G, char v)
24 {
25     int index;
26     for(int i=0;i<G.vexnum;i++)
27     {
28         if(v == G.vexs[i])
29         {
30             index = i;
31             break;
32         }
33     }
34     return index;
35 }
36 
37 void Creat_UDN(AMGraph &G)
38 {
39     char a, b;
40     int w;
41     cout<<"请输入图的总顶点数和边数：";
42     cin>>G.vexnum>>G.arcunm;
43     
44     cout<<"\n请输入顶点"<<endl; 
45     for(int i=0;i<G.vexnum;i++)
46     {
47         cin>>G.vexs[i];
48     }
49     
50     for(int i=0;i<G.vexnum;i++)
51     {
52         for(int j=0;j<G.vexnum;j++)
53         {
54             if(i==j)
55             {
56                 G.arcs[i][j] = 0;
57             }
58             else
59                 G.arcs[i][j] = MAXINT;
60         }
61     }
62     
63     cout<<"\n";
64     for(int i=0;i<G.arcunm;i++)
65     {
66         cout<<"请输入第"<<i+1<<"条边的信息(顶点 顶点 权值):" <<endl;
67         cin>>a>>b>>w; 
68         int m = LocateVex(G, a);
69         int    n = LocateVex(G, b);
70         G.arcs[m][n] = w;
71         G.arcs[n][m] = G.arcs[m][n];
72     }
73 }
74 
75 void print_UDN(AMGraph G)
76 {
77     cout<<"图的邻接矩阵如下："<<endl;
78     for(int i=0;i<G.vexnum;i++)
79     {
80         for(int j=0;j<G.vexnum;j++)
81         {
82             cout<<G.arcs[i][j]<<"  ";
83         }
84         cout<<"\n";
85     }
86 }
87 int main()
88 {
89     AMGraph G;
90     Creat_UDN(G); 
91     print_UDN(G);
92     return 0;
93 }