采用邻接矩阵表示法创建无向网的算法

邻接矩阵是一种常见的图的表示方法，可以用来表示有向图和无向图。对于无向网，我们可以采用邻接矩阵表示法来创建。

具体算法步骤如下：

1. 定义一个二维数组adjMatrix[N][N]，其中N为顶点数，初始化数组元素为0。

2. 对于每条边(u, v)，将adjMatrix[u][v]和adjMatrix[v][u]的值设置为边的权值。

3. 如果两个顶点之间没有边，则adjMatrix[u][v]和adjMatrix[v][u]的值为0。

4. 最终得到的邻接矩阵就是无向网的表示。

下面是一个示例代码：

// 定义邻接矩阵
int adjMatrix[N][N];
// 初始化邻接矩阵
for(int i=0; i<N; i++){
    for(int j=0; j<N; j++){
        adjMatrix[i][j] = 0;
    }
}
// 添加边
for(int k=0; k<edgeNum; k++){
    int u, v, w;
    cin >> u >> v >> w;
    adjMatrix[u][v] = w;
    adjMatrix[v][u] = w;
}

其中，edgeNum为边的数量，u和v是边的两个顶点，w是边的权值。通过循环输入每条边的信息，可以创建一个无向网的邻接矩阵。

相关问题

}//LocateVex int CreateUDN(AMGraph &G){ //采用邻接矩阵表示法，创建无向网G /**************begin************/ /**************end************/ }//CreateUDN int main(){ //cout << "************算法6.1 采用邻接矩阵表示法创建无向网**************" << endl << endl; AMGraph G; int i , j; CreateUDN(G); cout <<endl; //cout << "*****邻接矩阵表示法创建的无向网*****" << endl; for(i = 0 ; i < G.vexnum ; ++i){ for(j = 0; j < G.vexnum; ++j){ if(j != G.vexnum - 1){ if(G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] << "\t"; else cout << "∞" << "\t"; } else{ if(G.arcs[i][j] != MaxInt) cout << G.arcs[i][j] <<endl; else cout << "∞" <<endl; } } }//for cout <<endl; return 0; }//main 测试输入： 3 2 A B V A B 2 A V 4 预期输出： ∞ 2 4 2 ∞ ∞ 4 ∞ ∞

下面是完整的代码实现：

#include <iostream>
using namespace std;

#define MaxInt 0x7ffffffe  //最大值（即0X7FFFFFFF除去符号位）

typedef struct{
    char vexs[100];     //顶点集合
    int arcs[100][100]; //邻接矩阵，可看作边表
    int vexnum,arcnum;  //图的当前点数和边数
}AMGraph;

int LocateVex(AMGraph G,char ch){
    //确定ch在G中的位置
    for(int i = 0 ; i < G.vexnum ; ++i)
        if(G.vexs[i] == ch)
            return i;
    return -1;
}

int CreateUDN(AMGraph &G){
    //采用邻接矩阵表示法，创建无向网G
    cin >> G.vexnum >> G.arcnum;    //输入点数和边数
    for(int i = 0 ; i < G.vexnum ; ++i)
        cin >> G.vexs[i];           //输入顶点信息

    //初始化邻接矩阵
    for(int i = 0 ; i < G.vexnum ; ++i)
        for(int j = 0 ; j < G.vexnum ; ++j)
            G.arcs[i][j] = MaxInt;
    //构造邻接矩阵
    for(int k = 0 ; k < G.arcnum ; ++k){
        char v1,v2;
        int w;
        cin >> v1 >> v2 >> w;        //输入边（vi,vj）上的权值w
        int i = LocateVex(G,v1);    //确定v1和v2在G中的位置
        int j = LocateVex(G,v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = G.arcs[i][j];    //因为是无向图，矩阵对称
    }
    return 1;
}

int main(){
    cout << "************算法6.1 采用邻接矩阵表示法创建无向网**************" << endl << endl;
    AMGraph G;
    int i , j;
    CreateUDN(G);
    cout << endl;
    cout << "*****邻接矩阵表示法创建的无向网*****" << endl;
    for(i = 0 ; i < G.vexnum ; ++i){
        for(j = 0; j < G.vexnum; ++j){
            if(j != G.vexnum - 1){
                if(G.arcs[i][j] != MaxInt)
                    cout << G.arcs[i][j] << "\t";
                else
                    cout << "∞" << "\t";
            }
            else{
                if(G.arcs[i][j] != MaxInt)
                    cout << G.arcs[i][j] <<endl;
                else
                    cout << "∞" <<endl;
            }
        }
    }//for
    cout <<endl;
    return 0;
}

输入测试数据：

3 2
A B V
A B 2
A V 4

输出结果：

************算法6.1 采用邻接矩阵表示法创建无向网**************

*****邻接矩阵表示法创建的无向网*****
∞	2	4
2	∞	∞
4	∞	∞

#include<iostream> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MVNum 100 //最大顶点数 #define MaxInt 32767 using namespace std; typedef struct {//图的邻接矩阵存储表示 int vexnum,arcnum; //图的当前顶点数和边数 int vexs[MVNum]; //顶点表 int arcs[MVNum][MVNum]; //邻接矩阵 }AMGraph; int CreateUDN(AMGraph &G,int vexnum,int arcnum) {//采用邻接矩阵表示法，创建无向网G G.vexnum=vexnum; //输入总顶点数 G.arcnum=arcnum; //输入总边数 if(G.vexnum>MVNum) return ERROR; //超出最大顶点数则结束函数 int i,j,a,b,c; for(i=1;i<=G.vexnum;i++) G.vexs[i]=i; for(i=1;i<=G.vexnum;i++) //初始化邻接矩阵，边的权值均置为极大值 for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=MaxInt; for(i=0;i<G.arcnum;i++) //顶点a和顶点b之间有一条长度为c的路 { cin>>a>>b>>c; G.arcs[a][b]=c; G.arcs[b][a]=c; } return OK; } void ShortPathMAX(AMGraph G,int v0) {//用Dijkstra算法求图G中距离顶点v0的最短路径长度最大的一个顶点 /**begin/ /**end/ } int main() { int n,m; while(cin>>n>>m) { if(n==0&&m==0) break; AMGraph G; CreateUDN(G,n,m); //创建无向网G int v; cin>>v; ShortPathMAX(G,v); //最长的最短路径的求解 } return 0; }补全代码，测试输入： 4 4 1 2 1 2 3 1 3 4 1 2 4 1 4 4 3 1 2 3 2 3 2 2 4 6 3 0 0 预期输出： 1 2 4 8

#include<iostream>
#include<algorithm>
#include<cstring>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100 //最大顶点数
#define MaxInt 32767
using namespace std;

typedef struct {//图的邻接矩阵存储表示
int vexnum,arcnum; //图的当前顶点数和边数
int vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
}AMGraph;

int CreateUDN(AMGraph &G,int vexnum,int arcnum) {//采用邻接矩阵表示法，创建无向网G
G.vexnum=vexnum; //输入总顶点数
G.arcnum=arcnum; //输入总边数
if(G.vexnum>MVNum)
return ERROR; //超出最大顶点数则结束函数
int i,j,a,b,c;
for(i=1;i<=G.vexnum;i++)
G.vexs[i]=i;
for(i=1;i<=G.vexnum;i++) //初始化邻接矩阵，边的权值均置为极大值
for(j=1;j<=G.vexnum;j++)
G.arcs[i][j]=MaxInt;
for(i=0;i<G.arcnum;i++) //顶点a和顶点b之间有一条长度为c的路
{
cin>>a>>b>>c;
G.arcs[a][b]=c;
G.arcs[b][a]=c;
}
return OK;
}

void ShortPathMAX(AMGraph G,int v0) {//用Dijkstra算法求图G中距离顶点v0的最短路径长度最大的一个顶点
int dist[MVNum];//存储源点v0到其他顶点的最短距离
bool visited[MVNum]={false};//记录顶点是否已被访问
memset(dist,0,sizeof(dist));
for(int i=1;i<=G.vexnum;i++)//初始化dist数组
if(i!=v0)
dist[i]=MaxInt;
for(int i=1;i<=G.vexnum;i++) //循环n次，每次找出一个顶点的最短路径
{
int maxDist=-1,u;
for(int j=1;j<=G.vexnum;j++)
{
if(!visited[j]&&dist[j]>maxDist)
{
maxDist=dist[j];
u=j;
}
}
visited[u]=true;
for(int v=1;v<=G.vexnum;v++)
{
if(!visited[v]&&G.arcs[u][v]<MaxInt)
{
int newDist=max(dist[u],G.arcs[u][v]);
if(newDist<dist[v])
dist[v]=newDist;
}
}
}
for(int i=1;i<=G.vexnum;i++)
if(dist[i]!=MaxInt)
cout<<dist[i]<<" ";
cout<<endl;
}

int main() {
int n,m;
while(cin>>n>>m) {
if(n==0&&m==0)
break;
AMGraph G;
CreateUDN(G,n,m); //创建无向网G
int v;
cin>>v;
ShortPathMAX(G,v); //最长的最短路径的求解
}
return 0;
}