精华内容
下载资源
问答
  • 顶点数组不说了,表示的数组称为“邻接矩阵”AdjMatrix。 对于有向:AdjMatrix[i][j]为0表示顶点i顶点j之间无弧,1为ij间有弧。 对于无向:AdjMatrix[i][j]同样是1表示有弧,0无弧。单AdjMatrix[i][j]为...

     

    可以用两个数组分别存储数据元素(顶点)、数据元素之间的关系(边或弧度)。

    顶点数组不说了,表示弧的数组称为“邻接矩阵”AdjMatrix。

    对于有向图:AdjMatrix[i][j]为0表示顶点i和顶点j之间无弧,1为i和j间有弧。

    对于无向图:AdjMatrix[i][j]同样是1表示有弧,0无弧。单AdjMatrix[i][j]为1则一定有AdjMatrix[j][i]为1,因为弧是无方向对称的。

    对于网(弧带权):AdjMatrix[i][j]上是w或者无穷大,w表示连通且有权值w。无穷大是不连通。

    数据结构定义如下:

    typedef struct
    {
    	int vexs[MAX_VNUM]; // 所有顶点
    	int nvexs; // 顶点数目
    	int arcs[MAX_VNUM][MAX_VNUM]; // 邻接矩阵(即弧信息)
    	int narcs; // 弧的数量
    } Graph;

    下面我们用上面的结构完成一个无向连通图的创建和DFS

    #include <stdio.h>
    #include <string.h>
    
    #define MAX_VNUM 100
    
    typedef struct
    {
    	int vexs[MAX_VNUM]; // 所有顶点
    	int nvexs; // 顶点数目
    	int arcs[MAX_VNUM][MAX_VNUM]; // 邻接矩阵(即弧信息)
    	int narcs; // 弧的数量
    } Graph;
    
    int graph_locate_vec(Graph* graph, int val)
    {
    	int i;
    	for(i=0; i<graph->nvexs; i++)
    	{
    		if(graph->vexs[i]==val)
    		{
    			return i;
    		}
    	}
    	return -1;
    }
    
    void graph_create_graph(Graph* graph)
    {
    	int i, j;
    	// 存储顶点
    	printf("Please enter n for vex(s) :\n");
    	scanf("%d", &graph->nvexs);
    	for(i=0; i<graph->nvexs; i++)
    	{
    		printf("Please enter a int for vecs(%d) :\n", i);
    		scanf("%d", &graph->vexs[i]);
    	}
    	// 存储弧度
    	memset(graph->arcs, 0, sizeof(int)*MAX_VNUM*MAX_VNUM);
    	printf("Please enter m for arc(s) :\n");
    	scanf("%d", &graph->narcs);
    	for(i=0; i<graph->narcs; i++)
    	{
    		int x, y;
    		printf("Please enter v1, v2 for vecs(%d) :\n", i);
    		scanf("%d %d", &x, &y);
    		x = graph_locate_vec(graph, x);
    		y = graph_locate_vec(graph, y);
    		if(x==-1 || y==-1)
    		{
    			i--;
    			printf("Invalid v1 or v2.\n");
    			continue;
    		}
    		graph->arcs[x][y] = 1;
    		graph->arcs[y][x] = 1;
    	}
    }
    
    int flag[MAX_VNUM];
    void graph_dfs_(Graph* graph, int pos)
    {
    	int i;
    	if(flag[pos]==0)
    	{
    		//Visit
    		flag[pos] = 1;
    		printf("Visit %d\n", graph->vexs[pos]);
    		for(i=0; i<graph->nvexs; i++)
    		{
    			if(graph->arcs[pos][i]==1)
    			{
    				graph_dfs_(graph, i);
    			}
    		}
    	}
    }
    
    void graph_dfs(Graph* graph)
    {
    	int i;
    	memset(flag, 0, sizeof(int)*MAX_VNUM);
    	for(i=0;i<graph->nvexs;i++)
    	{
    		graph_dfs_(graph, i);
    	}
    }
    
    int main()
    {
    	Graph g;
    	graph_create_graph(&g);
    	graph_dfs(&g);
    	return 0;
    }

    测试数据:

     

    8
    1
    2
    3
    4
    5
    6
    7
    8
    9
    1 2
    1 3
    2 4
    2 5
    5 8
    4 8
    3 6
    3 7
    6 7

    输出结果:

    Visit 1
    Visit 2
    Visit 4
    Visit 8
    Visit 5
    Visit 3
    Visit 6
    Visit 7
    展开全文
  • 数组表示法邻接矩阵和邻接表两种存储结构分别表示下面无向。![图片说明](https://img-ask.csdn.net/upload/201904/10/1554855949_147929.png)
  • 对于连通网(带权),选择生成树总代价最少(Minimum Spanning Tree,MST ),比如一个N个城市之间通信网,网顶点代表城市,边代表这条路修路费。那么这样就设计一个最小花费问题。 最小生成树可以由...

    普里姆(Prim)算法与最小生成树

    最小生成树(MST)

    对于连通网(带权图),选择生成树的总代价最少(Minimum Spanning Tree,MST ),比如一个N个城市之间的通信网,网的顶点代表城市,边代表这条路的修路费。那么这样就设计一个最小花费的问题。

    最小生成树可以由普里姆(Prim)算法和Kruskal(克鲁斯卡尔)算法求出

    一:普里姆(Prim)算法

    1:需要邻接矩阵作为图的存储结构
    2:需要一个辅助数组来记录从U到V-U的最小代价closedge[i]
    3:这个U刚开始时候为空,逐个一个一个添加进U里

    (1):图的邻接矩阵
    1:用两个数组分别表示(顶点)、(边或弧)

    注意事项:用65535来代表无穷大,表示两个顶点没有联系
    存储结构:

    #define INT_MAX        65535                                        //最大值65535,表示两顶点没有联系
    #define MAX_VERTEX_NUM 20                                           //最多顶点数
    
    typedef char VertexType;
    typedef int  EdgeType;
    
    //有向图, 有向网, 无向图, 无向网
    enum GraphKind {
        DG, DN, UDG, UDN
    };
    
    //顶点信息
    typedef struct ArcCell {
        EdgeType wight;
    
    }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];                //二维数组  
    
    //弧的信息
    typedef struct MGraph {
        VertexType vexs[MAX_VERTEX_NUM];                                //顶点向量  
        AdjMatrix  arcs;                                                //邻接矩阵  
        int vexnum, arcnum;                                             //图的当前顶点数和弧数  
        GraphKind   kind;                                               //图的种类标志  
    }MGraph;
    2:建立无向图的邻接矩阵

    代码逻辑:
    (1)输入所有顶点
    (2)输入所有的边
    (3)将所有的边都设置成65535,表示图现在是孤立点,还没有相互联系
    (4)获取输入弧的两个顶点在顶点数组(邻接矩阵的两个数组–顶点数组,弧(边)数组)的位置
    (5)由于是无向图,且没有使用矩阵的压缩储存,所以这里对称赋值
    G.arcs[i][j].wight = G.arcs[j][i].wight = w;
    注意事项:
    这里scanf的%c输入是比较特殊的:
    (1):需要用getchar()读走空格
    (2):scanf(” %c”, &G.vexs[i]); 添加一个空格(%c前有一个空格),读走回车
    这里不详细讲了,具体在下面链接博客(还不清楚,可以去看看):
    https://blog.csdn.net/weixin_39956356/article/details/80371735
    相关代码:

    //建立无向图的邻接矩阵  
    void CreatMGraph(MGraph &G)
    {
        for (int i = 0; i < G.vexnum; i++) {
            printf("Please enter %d data:", i + 1);
            scanf(" %c", &G.vexs[i]);                                           //输入顶点值
        }
        for (int i = 0; i<G.vexnum; i++)
            for (int j = 0; j<G.vexnum; j++)
                G.arcs[i][j].wight = INT_MAX;           //邻接矩阵初始化  
    
        VertexType v1, v2;
        EdgeType w;
        int i, j;
        printf("Please input the two data of arc and wight,for example: A C 5\n");
        for (int k = 0; k < G.arcnum; k++) {
            printf("The %d arc: ", k + 1);
            scanf(" %c", &v1);                                                      //输入第一个顶点
            getchar();                                                              //把输入的空格读走
            v2 = getchar();                                                         //输入弧的第二个顶点
            scanf("%d", &w);                                                        //输入结点数,弧数
            i = LocateVex(G, v1);                                                   //获取弧的第一个节点位置
            j = LocateVex(G, v2);                                                   //获取弧的第二个节点位置
    
            G.arcs[i][j].wight = G.arcs[j][i].wight = w;                            //把权值存放在邻接矩阵中
        }
    }
    (2):Prim算法描述

    代码逻辑:
    (1)辅助数组初始化,把第一个点的邻接矩阵拷贝到辅助数组,将第一个顶点并入U集
    辅助数组结构:

    //Prim算法中的辅助信息
    struct prim{
        VertexType adjvex;                                              //存放最短路径的出发节点结点
        EdgeType   lowcost;                                             //最短路径
    };
    
    struct prim closedge[MAX_VERTEX_NUM];

    (2)选择其余G.vexnum - 1个顶点,并选择最小代价的边
    (3)输出路径与权值,将mincost并入U集
    (4)如果有更小的边,把小的替换原来的
    选取书上的例子,最小树创建过程:
    这里写图片描述
    辅助数组及变化:
    这里写图片描述
    最短路径及权值:
    这里写图片描述

    普里姆算法:

    /************************************************************************
    **                      普里姆算法
    **  输入参数:MGraph &G          图(邻接矩阵表示)
                :VertexType u       任选一个顶点
    **  返回参数:minSum         最短路径之和
    *************************************************************************/
    
    int MiniSpanTree_Prim(MGraph &G, VertexType u)
    {
        int k = LocateVex(G, u);                                                                            //确定第一个顶点的位置
        closedge[k].lowcost = 0;                                                                            //并入U集
        for (int i = 0; i < G.vexnum; i++)                                                                  //初始化辅助数组
            if(i != k)
            { 
                closedge[i].adjvex = u;                                                                     //存入起始结点
                closedge[i].lowcost = G.arcs[k][i].wight;                                                   //邻接矩阵该行拷贝到辅助数组中
            }
    
        int minSum = 0;                                                                                     //最短路径之和
        for (int i = 0; i < G.vexnum - 1; i++)                                                              //选择其余G.vexnum - 1个顶点
        {
            int mincost = minArc(G, closedge);                                                              //选择最小代价的边
            printf("%c--%c  %d\n", closedge[mincost].adjvex, G.vexs[mincost], closedge[mincost].lowcost);   //输出路径与权值
            minSum += closedge[mincost].lowcost;                                                            //最短路径之和
            closedge[mincost].lowcost = 0;                                                                  //将mincost并入U集
            for (int j = 0; j < G.vexnum; j++)                                                              
            {
                if (G.arcs[mincost][j].wight < closedge[j].lowcost)                                         //如果有更小的边,把小的替换原来的
                {
                    closedge[j].adjvex = G.vexs[mincost];
                    closedge[j].lowcost = G.arcs[mincost][j].wight;
                }
            }
        }
        return minSum;                                                                                      //返回最短路径之和
    }
    
    (3):主函数
    #include "stdafx.h"
    #include "Prim.h"
    
    
    int main()
    {
        MGraph G;
        printf("Please enter vexnum and arcnum: ");
        scanf("%d %d", &G.vexnum, &G.arcnum);                                               //输入结点数,弧数
    
        CreatMGraph(G);                                                                     //建立无向图的邻接矩阵 
        printf("\nTne output of Adjacency Matrix:\n\n");
        printMatrixGraph(G);                                                                //输出邻接矩阵
        printf("\nTne shortest path of Graph:\n\n");
        printf("\nThe sum of the shortest paths is %d.\n", MiniSpanTree_Prim(G, G.vexs[0]));//输出路径与权值
    
        return 0;
    }
    
    (4):代码输出

    这里写图片描述

    感谢与源代码
    1:感谢一下博主文章对我的帮助:
    https://blog.csdn.net/zguiz/article/details/54633115
    2:源代码(VS2017)(这里说一下:VS工程有个.vs的隐藏配置文件,如果第一次弹出配置选错了,直接删除.vs,第二次打开会再次提示。VS向下兼容)
    链接: https://pan.baidu.com/s/1Wv8uqTW7dU6mzinZSNCUgw 密码: p8nb

    展开全文
  •  构造一个采用邻接矩阵作存储结构、具有n个顶点e条边无向网()G时间复杂度是(n*n + e*n), 其中对邻接矩阵G.arcs初始化耗费了n*n时间。  借助于邻接矩阵容易判定两个顶点之间是否有边/弧相连,并容易...

    文字描述

      用两个数组分别存储顶点信息和边/弧信息。

    示意图

    算法分析

      构造一个采用邻接矩阵作存储结构、具有n个顶点和e条边的无向网(图)G的时间复杂度是(n*n + e*n), 其中对邻接矩阵G.arcs的初始化耗费了n*n的时间。

      借助于邻接矩阵容易判定两个顶点之间是否有边/弧相连,并容易求得各个顶点的度。对于无向图,顶点vi的度是邻接矩阵地i行(或第i列)的元素之和;对于有向图,第i行的元素之和为顶点vi的出度;第j列的元素之和为顶点vj的入度;

    代码实现

     

      1 /*
      2     以数组表示法(邻接矩阵)作为图的存储结构创建图。
      3 */
      4 #include <stdio.h>
      5 #include <stdlib.h>
      6 #include <string.h>
      7 
      8 #define INFINITY        100000    //最大值
      9 #define MAX_VERTEX_NUM    20        //最大顶点数
     10 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图,有向网,无向图,无向网}
     11 typedef int  VRType;
     12 typedef char VertexType;
     13 typedef struct{
     14     char note[10];
     15 }InfoType;
     16 typedef struct ArcCell{
     17     VRType adj;        //顶点关系类型:1)对无权图,用1或0表示相邻否;2)对带权图,则为权值类型
     18     InfoType *info;    //该弧相关信息的指针
     19 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
     20 typedef struct{
     21     VertexType vexs[MAX_VERTEX_NUM];    //顶点向量
     22     AdjMatrix arcs;        //邻接矩阵
     23     int vexnum, arcnum;    //图的当前顶点数和弧数
     24     GraphKind kind;        //图的种类标志
     25 }MGraph;
     26 
     27 /*
     28     若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
     29 */
     30 int LocateVex(MGraph G, VertexType v){
     31     int i = 0;
     32     for(i=0; i<G.vexnum; i++){
     33         if(G.vexs[i] == v){
     34             return i;
     35         }
     36     }
     37     return -1;
     38 }
     39 
     40 /*
     41     采用数组表示法(邻接矩阵),构造无向网
     42 */
     43 int CreateUDN(MGraph *G){
     44     int i = 0, j = 0, k = 0, IncInfo = 0;
     45     int v1 = 0, v2 = 0, w = 0;
     46     char tmp[10] = {0};
     47 
     48     printf("输入顶点数,弧数,其他信息标志位: ");
     49     scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo);
     50 
     51     for(i=0; i<G->vexnum; i++){
     52         printf("input vexs %d: ", i+1);
     53         memset(tmp, 0, sizeof(tmp));
     54         scanf("%s", tmp);
     55         G->vexs[i] = tmp[0];
     56     }
     57     for(i=0; i<G->vexnum; i++){
     58         for(j=0; j<G->vexnum; j++){
     59             G->arcs[i][j].adj = INFINITY;
     60             G->arcs[i][j].info = NULL;
     61         }
     62     }
     63     for(k=0; k<G->arcnum; k++){
     64         printf("输入第%d条弧: 顶点1, 顶点2,权值", k+1);
     65         memset(tmp, 0, sizeof(tmp));
     66         scanf("%s", tmp);
     67         sscanf(tmp, "%c,%c,%d", &v1, &v2, &w);
     68         i = LocateVex(*G, v1);
     69         j = LocateVex(*G, v2);
     70         G->arcs[i][j].adj = w;
     71         if(IncInfo){
     72             //
     73         }
     74         G->arcs[j][i] = G->arcs[i][j];
     75     }
     76     return 0;
     77 }
     78 
     79 /*
     80     采用数组表示法(邻接矩阵),构造无向图
     81 */
     82 int CreateUDG(MGraph *G)
     83 {
     84     int i = 0, j = 0, k = 0, IncInfo = 0;
     85     int v1 = 0, v2 = 0, w = 0;
     86     char tmp[10] = {0};
     87 
     88     printf("输入顶点数,弧数,其他信息标志位: ");
     89     scanf("%d,%d,%d", &G->vexnum, &G->arcnum, &IncInfo);
     90 
     91     for(i=0; i<G->vexnum; i++){
     92         printf("输入第%d个顶点: ", i+1);
     93         memset(tmp, 0, sizeof(tmp));
     94         scanf("%s", tmp);
     95         G->vexs[i] = tmp[0];
     96     }
     97     for(i=0; i<G->vexnum; i++){
     98         for(j=0; j<G->vexnum; j++){
     99             G->arcs[i][j].adj = 0;
    100             G->arcs[i][j].info = NULL;
    101         }
    102     }
    103     for(k=0; k<G->arcnum; k++){
    104         printf("输入第%d条弧(顶点1, 顶点2): ", k+1);
    105         memset(tmp, 0, sizeof(tmp));
    106         scanf("%s", tmp);
    107         sscanf(tmp, "%c,%c", &v1, &v2, &w);
    108         i = LocateVex(*G, v1);
    109         j = LocateVex(*G, v2);
    110         G->arcs[i][j].adj = 1;
    111         if(IncInfo){
    112             //
    113         }
    114         G->arcs[j][i] = G->arcs[i][j];
    115     }
    116     return 0;
    117 }
    118 
    119 /*
    120     采用数组表示法(邻接矩阵),构造图
    121 */
    122 int CreateGraph(MGraph *G)
    123 {
    124     printf("输入图类型: -有向图(0), -有向网(1), +无向图(2), +无向网(3): ");
    125     scanf("%d", &G->kind);
    126     switch(G->kind){
    127         case DG://构造有向图
    128         case DN://构造有向网
    129             printf("还不支持!\n");
    130             return -1;
    131         case UDG://构造无向图
    132             return CreateUDG(G);
    133         case UDN://构造无向网
    134             return CreateUDN(G);
    135         default:
    136             return -1;
    137     }
    138 }
    139 
    140 /*
    141     输出图的信息
    142 */
    143 void printG(MGraph G)
    144 {
    145     if(G.kind == DG){
    146         printf("类型:有向图;顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
    147     }else if(G.kind == DN){
    148         printf("类型:有向网;顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
    149     }else if(G.kind == UDG){
    150         printf("类型:无向图;顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
    151     }else if(G.kind == UDN){
    152         printf("类型:无向网;顶点数 %d, 弧数 %d\n", G.vexnum, G.arcnum);
    153     }
    154     int i = 0, j = 0;
    155     printf("\t");
    156     for(i=0; i<G.vexnum; i++){
    157         printf("%c\t", G.vexs[i]);
    158     }
    159     printf("\n");
    160     for(i=0; i<G.vexnum; i++){
    161         printf("%c\t", G.vexs[i]);
    162         for(j=0; j<G.vexnum; j++){
    163             if(G.arcs[i][j].adj == INFINITY){
    164                 printf("INF\t");
    165             }else{
    166                 printf("%d\t", G.arcs[i][j].adj);
    167             }
    168         }
    169         printf("\n");
    170     }
    171 }
    172 
    173 int main(int argc, char *argv[])
    174 {
    175     MGraph G;
    176     if(CreateGraph(&G) > -1)
    177         printG(G);
    178     return 0;
    179 }
    邻接矩阵存储结构(图)

     

     

     

    代码运行

     

    转载于:https://www.cnblogs.com/aimmiao/p/9737654.html

    展开全文
  • 数据结构——图的数组邻接矩阵表示法

    千次阅读 多人点赞 2018-11-20 00:22:19
    若考虑无向图的邻接矩阵的对称性,则可采用压缩存储的方式只存入矩阵的下三角(或上三角)元素。下示算法时在邻接矩阵存储结构MGraph上对图构造的实现框架,它根据G的种类调用具体构造的算法。例如G为无...

    数组表示无向图

    用两个数组(vexs[],arcs[][])分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。以二维数组表示有n个顶点的图时,需存放n个顶点信息和n^2个弧信息存储量。若考虑无向图的邻接矩阵的对称性,则可采用压缩存储的方式只存入矩阵的下三角(或上三角)元素。下示算法时在邻接矩阵存储结构MGraph上对图构造的实现框架,它根据G的种类调用具体构造的算法。例如G为无向图则调用CreatUDN()。本篇只实现了无向图的构建后续将实现DG、DN、及UDG。

    以下图为例:

    顶点数组:

    邻接矩阵:

     

     

     C语言实现

    /*
    文件名:ArrayNotation.c
    描述:图的数组表示法
    时间:2018/11/19
    		2019.1.3补全
    */
    
    
    #include<stdio.h>
    
    //-------------图的数组(邻接矩阵)存储表示---------------
    #define INFINITY 95533	// 最大值
    #define MAX_VERTEX_NUM 20	//最大顶点个数
    #define VRType int		//顶点关系类型,对无权图,用1或0表示相邻否;对带权图,则为权值类型
    #define InfoType int	// ?弧类型??????
    #define VErtexType int	//图顶点类型
    typedef enum {DG,DN,UDG,UDN}GraphKind;	//图的种类(有向图,有向网,无向图,无向网)****枚举类型enum
    typedef struct ArcCell {
    	VRType adj;		//顶点关系类型
    	InfoType *info;	//该弧相关信息的指针
    }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    typedef struct {
    	VErtexType vexs[MAX_VERTEX_NUM];	//顶点向量
    	AdjMatrix arcs;		//邻接矩阵
    	int vexnum, arcnum;		//图的当前顶点数和弧数
    	GraphKind	kind;		//图的种类标志
    }MGraph;
    
    
    int LocateVex(MGraph *G, VRType point)	//确定某个顶点在图G中的位置
    {
    	int i, j;
    	for (i = 0; i < G->vexnum; i++)
    		if (G->vexs[i] == point)
    			return i;
    
    }//LocateVex
    
    
    void CreatUDN(MGraph *G)	//采用数组(邻接矩阵),构造无向网G
    {
    	int i, j, k;
    	VRType origin, terminus, weight; 	//边的起点,终点,权值
    	printf("输入图的顶点数 弧数");
    	scanf("%d %d", &(G->vexnum), &(G->arcnum));
    	for (i = 0; i < G->vexnum; i++)	//将顶点值存储进去
    	{
    		printf("输入顶点值:");
    		scanf("%d", &(G->vexs[i]));
    	}//for
    	for (i = 0; i < G->vexnum; i++)	//初始化邻接矩阵
    		for (j = 0; j < G->vexnum; j++)
    		{
    			G->arcs[i][j].adj = INFINITY;
    			G->arcs[i][j].info = NULL;
    		}//for
    	for (k = 0; k < G->arcnum; k++)	//	arcnum???弧数
    	{
    		printf("输入一条边的两端以及权值");
    		scanf("%d %d %d", &origin, &terminus ,&weight);
    		i = LocateVex(G, origin);	//利用LocateVex函数确定起点(origin)及终点(terminus)在G中位置
    		j = LocateVex(G, terminus);
    		G->arcs[i][j].adj = 0;
    		G->arcs[j][i].adj = 0;
    		G->arcs[i][j].info = (InfoType *)malloc(sizeof(InfoType));
    		G->arcs[j][i].info = (InfoType *)malloc(sizeof(InfoType));
    		*(G->arcs[i][j].info) = weight;
    		*(G->arcs[j][i].info) = weight;
    	}//for
    	printf("创建成功\n");
    }//CreatUDN
    
    void CreatDG(MGraph *G)		//有向图
    {
    	int i, j, k;
    	VRType origin, terminus; 	//边的起点,终点
    	printf("输入图的顶点数 弧数");
    	scanf("%d %d", &(G->vexnum), &(G->arcnum));
    	for (i = 0; i < G->vexnum; i++)	//将顶点值存储进去
    	{
    		printf("输入顶点值:");
    		scanf("%d", &(G->vexs[i]));
    	}//for
    	for (i = 0; i < G->vexnum; i++)	//初始化邻接矩阵
    		for (j = 0; j < G->vexnum; j++)
    		{
    			G->arcs[i][j].adj = INFINITY;
    			G->arcs[i][j].info = NULL;
    		}//for
    	for (k = 0; k < G->arcnum; k++)	//	arcnum???弧数
    	{
    		printf("输入一条边的起点终点");
    		scanf("%d %d", &origin, &terminus);
    		i = LocateVex(G, origin);	//利用LocateVex函数确定起点(origin)及终点(terminus)在G中位置
    		j = LocateVex(G, terminus);
    		G->arcs[i][j].adj = 0;
    		G->arcs[i][j].info = (InfoType *)malloc(sizeof(InfoType));
    	}//for
    	printf("创建成功\n");
    
    }
    
    void CreatDN(MGraph *G)		//有向网
    {
    	int i, j, k;
    	VRType origin, terminus, weight; 	//边的起点,终点,权值
    	printf("输入图的顶点数 弧数");
    	scanf("%d %d", &(G->vexnum), &(G->arcnum));
    	for (i = 0; i < G->vexnum; i++)	//将顶点值存储进去
    	{
    		printf("输入顶点值:");
    		scanf("%d", &(G->vexs[i]));
    	}//for
    	for (i = 0; i < G->vexnum; i++)	//初始化邻接矩阵
    		for (j = 0; j < G->vexnum; j++)
    		{
    			G->arcs[i][j].adj = INFINITY;
    			G->arcs[i][j].info = NULL;
    		}//for
    	for (k = 0; k < G->arcnum; k++)	//	arcnum???弧数
    	{
    		printf("输入一条边的起点终点以及权值");
    		scanf("%d %d %d", &origin, &terminus, &weight);
    		i = LocateVex(G, origin);	//利用LocateVex函数确定起点(origin)及终点(terminus)在G中位置
    		j = LocateVex(G, terminus);
    		G->arcs[i][j].adj = 0;
    		G->arcs[i][j].info = (InfoType *)malloc(sizeof(InfoType));
    		*(G->arcs[i][j].info) = weight;
    	}//for
    	printf("创建成功\n");
    }//CreatUDN
    
    
    void CreatUDG(MGraph *G)	//无向图
    {
    	int i, j, k;
    	VRType origin, terminus; 	//边的起点,终点
    	printf("输入图的顶点数 弧数");
    	scanf("%d %d", &(G->vexnum), &(G->arcnum));
    	for (i = 0; i < G->vexnum; i++)	//将顶点值存储进去
    	{
    		printf("输入顶点值:");
    		scanf("%d", &(G->vexs[i]));
    	}//for
    	for (i = 0; i < G->vexnum; i++)	//初始化邻接矩阵
    		for (j = 0; j < G->vexnum; j++)
    		{
    			G->arcs[i][j].adj = INFINITY;
    			G->arcs[i][j].info = NULL;
    		}//for
    	for (k = 0; k < G->arcnum; k++)	//	arcnum???弧数
    	{
    		printf("输入一条边的两端");
    		scanf("%d %d", &origin, &terminus);
    		i = LocateVex(G, origin);	//利用LocateVex函数确定起点(origin)及终点(terminus)在G中位置
    		j = LocateVex(G, terminus);
    		G->arcs[i][j].adj = 0;
    		G->arcs[j][i].adj = 0;
    	}//for
    	printf("创建成功\n");
    
    }
    
    void CreatGraph(MGraph *G)		//采用数组(邻接矩阵)表示法构造图G
    {
    	int kind;
    	printf("输入图类型(1.DG/2.DN/3.UDG/4.UDN):");
    	scanf("%d", &kind);
    	switch (kind)
    	{
    	case 1: CreatDG(G);	break;
    	case 2: CreatDN(G);	break;
    	case 3:CreatUDG(G);	break;
    	case 4:CreatUDN(G);	break;
    	default: printf("ERROR!"); break;
    	}//switch
    }//CreatGraph
    		
    int main()
    {
    	MGraph G;
    	CreatGraph(&G);
    
    	return 0;
    }

    运行结果:

    存在问题:

    c语言枚举类型的应用 

     

     

     

     

    展开全文
  • 1、 掌握图的结构特征以及四种存储结构(数组表示法、邻接表、十字链表和邻接多重表)的特点和程序设计方法。 2、 掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法的设计方法。 3、 进一步掌握递归...
  • 2、 按照建立一个带权有向图的操作需要,编写在邻接矩阵或邻接表存储结构下,带权有向图基本操作的实现函数(如初始化图、在图中插入一个结点、在图中插入一条边、在图中寻找序号为v的结点的第一个邻接结点、在图中...
  • 邻接矩阵表示法:(将映射到二维数组) #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #define ERROR 0 #define OK 1 #define Overflow 2//上溢 #define Underflow 3//下溢 #define Not...
  • 前言 从线性结构线性关系,到树形结构层次关系,再到现在的图结构 结构比较复杂,中任意两个顶点...数组表示法 用两个数组分别存储数据元素(顶点)信息 数据元素之间关系(边或弧)信息。 #de
  • 图的存储结构之数组表示法

    千次阅读 2013-05-20 20:01:14
    由于图中顶点间的关系(弧或边)无规律,故对图的存储较之表...图的数组表示法又称“邻接矩阵”(Adjacency Matrix)表示法。 G = (V,R) 用两个数组来存储图G: 一个数组(一维)存储G中顶点集合V;另一个数组(二维)映像
  • 图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组表示图,一个一维数组存储图中的顶点信息,一个二维数组(邻接矩阵)存储图中边或弧的信息。 2、图的邻接表表示法 邻接矩阵是一种不错的图存储结构,但我们...
  • 如果仅仅需要对图进行DFS...如果要找单源最短路径(Dijkstra算法),那么最好使用邻接矩阵表示法,因为每次找出distance数组最短路径后,要更新distance数组,此时需要知道某个节点与其他节点之间距离,邻...
  • 呵呵,今天的成果!!图的数组表示法

    千次阅读 2006-12-06 22:53:00
    #include "conio.h"#include "stdio.h"#define MAXSIZE 100 //最大顶点数struct Graph{ char vexs[MAXSIZE]; //顶点数组 int arcs[MAXSIZE][MAXSIZE]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数弧数
  • (一般把带权值的图叫做网)邻接矩阵适合稠密图的存储。 二、邻接表:是图的一种顺序存储于链式存储结合的存储方法。领接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点Vi,将所有的邻接于Vi的顶点Vj...
  • **图的存储结构有两种:**一种是基于二维数组邻接矩阵表示法。 另一种是基于链表的的邻接表表示法。 在邻接矩阵中,可以如下表示顶点和边连接关系: 说明: 将顶点对应为下标,根据横纵坐标将矩阵中的某一位置值...
  • 邻接矩阵图的存储结构中的数组表示法(邻接表为链表表示法)。 邻接矩阵定义源自严版数据结构教材161页: typedef struct{ VertexType vexs[MAX_VERTEX_NUM];//顶点向量 AdjMatrix arcs;//邻接矩阵(地址) int...
  • 图的邻接矩阵表示法是用 两个数组 来表示 图的数据结构。一个是顶点数组,另一个是邻接矩阵数组邻接矩阵 里存放着 顶点的关系。 用邻接矩阵表示图,在 看 顶点之间 是否有边,或者 求顶点的度等操作时比较简单。...
  • 邻接矩阵

    万次阅读 多人点赞 2020-09-08 19:26:45
    数组邻接矩阵表示法无向图的邻接矩阵表示法有向图的邻接矩阵表示法有权图(网)的邻接矩阵表示法邻接矩阵的存储表示2.采用邻接矩阵表示法创建无向网 邻接矩阵 1 1 1 1      1. 数组邻接...
  • 掌握图的结构特征,以及邻接矩阵和邻接表存储结构的特点和建立方法;掌握在邻接矩阵或邻接表存储结构下图的深度优先和广度优先遍历算法的设计方法。 实验条件:计算机一台,vc++6.0 实验内容与算法思想: 内容: ...
  • 图常用的存储表示----------邻接矩阵法和邻接表法。 邻接矩阵 图有N个顶点,那么这个图的邻接矩阵是一个N*N的二维数组。代码中设置两点没边,则这两点对应的二维数组值为0,其他有边的两点看是否为带权图,是则二维...
  • 文章目录邻接矩阵1、邻接矩阵表示法2、无向图的邻接矩阵表示法3、有向图的邻接矩阵表示法4、网(有权图)的邻接矩阵表示法5、邻接矩阵的存储表示6、采用邻接矩阵表示法创建无向网7、邻接矩阵优点缺点 图没有顺序...
  • 数据结构之(二)——邻接矩阵

    千次阅读 2019-08-06 16:20:46
    图的逻辑结构为多对多,图没有顺序存储结构,但可以借助二维数组来表示元素间的关系,即数组表示法(邻接矩阵)。图的链式存储结构可以用多重链表来描述,如邻接表,邻接多重表以及十字链表等。 邻接矩阵 数组(邻接...
  • 邻接矩阵表示一个图的常用存储表示。它用两个数组分别存储数据元素(顶点)的信息数据元素之间的关系(边或弧)的信息。 将的顶点标为。若,,否则。 无向图的邻接矩阵是对称的,有向图的邻接矩阵一般...
  • 另一个是创建弧的信息,包括弧的相关顶点权值,可存储到二维数组里,其中,二维数组的下标分别表示两个顶点的弧尾弧头编号,权值存放在对应的数组中。 创建一个网: 请输入有向网N的顶点数弧数:6 9 请输入6个...
  • 邻接矩阵的定义例子

    万次阅读 2018-04-07 21:41:52
    根据图的定义可知,图的...在图的邻接矩阵表示法中:① 用邻接矩阵表示顶点间的相邻关系② 用一个顺序表来存储顶点信息图的矩阵设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:【例】下图中...
  • 1),无向图的邻接矩阵一定是对称的,对于有n个顶点的无向图则只存上(下)三角阵中剔除了左上右下对角线上的0元素后剩余的元素,故只需1+2+.....+(n-1)=n*(n-1)/2个单元。 2),有向图的邻接矩阵不一定对称,表示图...
  • 一、图的建立 图是表达“多对多”的关系的一种数据结构。 它由非空的有限顶点集合有限边集合组成。 1. 顶点集合常常由数组表示。 数组下标表示顶点位置。 数组内容包含顶点数据,并且要添加判定是否被...
  • 图的邻接矩阵存储

    2017-04-24 20:00:08
    一般的图会使用二元组的方式来描述,G=(V,E) ,其中V 叫作顶点集,E叫作边集。  图分为: (1)无向图 (2)有向图   图的表示存储方式: (1)邻接矩阵表示法 (2)邻接表表示法  邻接矩阵:存储为二维数组
  • 邻接矩阵

    2019-10-06 08:32:06
    有两种表示方法,邻接矩阵和邻接表,接下来我们讲解邻接矩阵和用c实现一个邻接矩阵. ...邻接矩阵表示法,用两个数组表示,一个一维数组和一个二维数组. 一维数组存储节点信息,二维数组存储节点之间关系. ...
  • python图的创建(邻接矩阵

    千次阅读 2020-01-15 22:53:34
    '''邻接矩阵法完成图的表示''' #创建图,输入图的顶点个数、顶点、以及创建邻接表存储顶点的数组 class Graph(object): def __init__(self): self._count = int(input('输入图的顶点的个数:')) ...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 207
精华内容 82
关键字:

图的数组表示法和邻接矩阵