用户注册



邮箱：

密码：

用户登录


邮箱：

密码：
记住登录一个月忘记密码？

发表随想


还能输入：200字
云代码 - c++代码库

图的基本操作——邻接矩阵表示（网（边带权值的图）的编程没有给出，与一般的图类似）

2013-02-21 作者： shiqiang举报

[c++]代码库

view sourceprint?
temp1.h
 
#define VertexType int
#define AdjMatrix int
    typedef enum{NG, DG, NW, DW}GraphKind;
#define Status int
#define MAX_N 10
#define OK 1
#define ERROR 0
 
typedef struct{
    VertexType vexs[MAX_N];//表示顶点的数组;
    AdjMatrix arcs[MAX_N][MAX_N];//表示边的二维数组;
    int vexnum,arcnum;//顶点和边的个数;
    GraphKind kind;
}MGraph;//定义图MGraph；用邻接矩阵表示。
 
 
 
 
 
temp1.cpp
 
#include<iostream>
#include<fstream>
#include"temp1.h"
    using namespace std;
 
int LocateVex(MGraph G, VertexType v){
    //在图G的vexs(顶点）中找值为v的元素的下标，如果没有则返回-1；
    for(int i = 0; i < G.vexnum; i++){
        if(G.vexs[i] == v){
            return i;
        }
    }
    return -1;
}
 
Status CreateMGraph(MGraph &G){
    //创建图G,输入（读文件）的值有
    //1.图的顶点数,边/弧的数目，图的类型
    //2.依次输入顶点的值
    //3.依次输入一条边的起点和终点；
    ifstream in;
    in.open("data3.txt", ios::in);
    cout<<"下列数据从文件data3.txt读入"<<endl<<endl;
    cout<<"请输入图的顶点数,边/弧的数目，图的类型"<<endl;
    int kind;
    in>>G.vexnum>>G.arcnum>>kind;//从文件读入数据，遇到任何结束标记（如空格和换行）则停止。
    switch(kind){
    case 0 :
        G.kind = NG;
        break;
    case 1:
        G.kind = DG;
        break;
    case 2:
        G.kind = NW;
        break;
    case 3:
        G.kind = DW;
        break;
    }
    cout<<"请依次输入顶点的值"<<endl;
    for(int i = 0; i < G.vexnum; i++){
        in>>G.vexs[i];
    }
    for(int i = 0; i < G.vexnum; i++){
        for(int j = 0; j < G.vexnum; j++){
            G.arcs[i][j] = 0;
        }
    }
    cout<<"请依次输入一条边的起点和终点："<<endl;
    for(int k = 0; k < G.arcnum; k++){
        int v1, v2, i, j;
        in>>v1>>v2;
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);
        G.arcs[i][j] = 1;
        if(G.kind == NG)//无向图
            G.arcs[j][i] = 1;
    }
    cout<<endl;
    return OK;
}
 
int Degree(MGraph G, VertexType v){
    //求图G中顶点值为v的顶点的度，找到则返回v的度，如果没有顶点值为v的顶点则返回-1；
    int i = LocateVex(G, v);
    if(i == -1){
        return -1;//顶点不存在
    }
    int num = 0;
    for(int j = 0; j < G.vexnum; j++){
        if(G.arcs[i][j] == 1){
            num++;
        }
    }
    if(G.kind == DG){//有向图
        for(int j = 0; j < G.vexnum; j++){
            if(G.arcs[j][i] == 1){
                num++;
            }
        }
    }
    return num;
}
 
int IsAdj(MGraph G, VertexType v1, VertexType v2){
    //判断图G中的顶点v1， v2是否具有邻接关系；如果有图则返回1，带权值的网则返回“权值”；
    //没有找到这两个顶点则返回-1
 
    int i = LocateVex(G, v1);
    if(i == -1){
        return -1;
    }
    int j = LocateVex(G, v2);
    if(j == -1){
        return -1;
    }
    return G.arcs[i][j];
}
 
Status InsertVertex(MGraph &G, VertexType v){
    //在图G中插入顶点v；插在末尾；
    if(LocateVex(G, v) != -1){
        return ERROR;
    }
    if(G.vexnum >= MAX_N){
        //扩容
    }
    G.vexs[G.vexnum] = v;
    for(int i = 0; i <= G.vexnum; i++){
        G.arcs[G.vexnum][i] = 0;
        G.arcs[i][G.vexnum] = 0;
    }
    G.vexnum++;
    return OK;
}
 
Status InsertAdj(MGraph &G, int i, int j){
    //增加边/弧，即增加下标为i的顶点到下标为j的顶点之间的邻接关系；
    //如果边已经存在则返回ERROR。
    if(i < 0 || i >= G.vexnum || j < 0 || j >= G.vexnum){
        return ERROR;//顶点不存在
    }
    if(G.arcs[i][j] == 1){
        return ERROR;//边已经存在
    }
    G.arcs[i][j] = 1;
    if(G.kind == NG){
        G.arcs[j][i] = 1;
    }
    G.arcnum++;
    return OK;
}
 
Status DeleteAdj(MGraph &G, int i, int j){
    //删除边/弧，即删除下标为i的顶点到下标为j的顶点之间的邻接关系；
    //如果边已经不存在则返回ERROR。
    if(i < 0 || i > G.vexnum || j < 0 || j >= G.vexnum){
        return ERROR;//顶点不存在
    }
    if(G.arcs[i][j] == 0){
        return ERROR;//边已不存在
    }
    G.arcs[i][j] = 0;
    if(G.kind == NG){
        G.arcs[j][i] = 0;
    }
    G.arcnum--;
    return OK;
}
 
 
int main(){
    //依次测试函数CreateMGraph Degree IsAdj InsertVertex
    //InsertAdj DeleteAdj
    MGraph G;
    CreateMGraph(G);
    int n;
    n = Degree(G, 2);
    cout<<"顶点2的度为："<<n<<endl;
    n = IsAdj(G, 3, 4);
    cout<<"顶点3, 4之间的邻接关系："<<n<<endl;
    n = IsAdj(G, 3, 2);
    cout<<"顶点3, 2之间的邻接关系："<<n<<endl;
    InsertVertex(G, 5);
    n = IsAdj(G, 5, 5);
    cout<<"顶点5，5之间的邻接关系："<<n<<endl;
    InsertAdj(G, 5, 5);
    n = IsAdj(G, 5, 5);
    cout<<"顶点5，5之间的邻接关系："<<n<<endl;
    DeleteAdj(G, 3, 4);
    n = IsAdj(G, 3, 4);
    cout<<"顶点3, 4之间的邻接关系："<<n<<endl;
    system("pause");
    return 0;
}
 
 
 
 
 
data3.txt
 
    5
    5
    0
    0
    1
    2
    3
    4
    1
    1
    1
    2
    2
    4
    3
    3
    3
    4


网友评论    (发表评论)


发表评论：

评论须知：

  • 1、评论每次加2分，每天上限为30；
  • 2、请文明用语，共同创建干净的技术交流环境；
  • 3、若被发现提交非法信息，评论将会被删除，并且给予扣分处理，严重者给予封号处理；
  • 4、请勿发布广告信息或其他无关评论，否则将会删除评论并扣分，严重者给予封号处理。


扫码下载

加载中，请稍后...

输入口令后可复制整站源码

加载中，请稍后...