精华内容
下载资源
问答
  • 数据结构-使用邻接矩阵创建无向图

    千次阅读 2020-12-01 18:09:54
    邻接矩阵表示法表示,除了用一个存储邻接矩阵的二维数组外,还需要用一个一维数组来存储顶点信息。 //采用邻接矩阵表示法创建无向网 #include <iostream> using namespace std; #define MaxInt 32767 /...

    1.邻接矩阵

    邻接矩阵(Adjacency Matrix)是表示顶点之间相邻关系的矩阵。

    2.程序分析

    W i,j表示边上的权值;∞表示计算机允许的,大于所有边权值的数。

    用邻接矩阵表示法表示图,除了用一个存储邻接矩阵的二维数组外,还需要用一个一维数组来存储顶点信息。

    //采用邻接矩阵表示法创建无向网
    
    #include <iostream>
    using namespace std;
    
    #define MaxInt 32767                    	//表示极大值,即∞
    #define MVNum 100                       	//最大顶点数
    #define OK 1	
     						
    typedef char VerTexType;              		//假设顶点的数据类型为字符型 
    typedef int ArcType;                  		//假设边的权值类型为整型 
    
    //- - - - -图的邻接矩阵存储表示- - - - -
    typedef struct{ 
    	VerTexType vexs[MVNum];            		//顶点表 
    	ArcType arcs[MVNum][MVNum];      		//邻接矩阵 
    	int vexnum,arcnum;                		//图的当前点数和边数 
    }AMGraph;
    

    3.采用邻接矩阵表示法创建无向网

    算法步骤:

    1. 输入总顶点数和总边数

    2. 依次输入点的信息存入顶点表中

    3. 初始化邻接矩阵,使得每个权值初始化为极大值

    4. 构造邻接矩阵

    4.如何构造邻接矩阵

    依次输入每条边依附的顶点和其权值,确定两个顶点在图中的位置之后,是相应的边赋予相应的权值,同时使其对称边赋予相同的权值。

    5.如何确定顶点位置

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

    6.完整代码

    #include <iostream>
    using namespace std;
    
    #define MaxInt 32767  //表示极大值
    #define MVNum 100 //最大顶点数
    #define OK 1
    typedef char VerTexType;//顶点数据类型为字符型
    typedef int  ArcType;//权值为整形
    typedef int  Status;//定义返回值类型
    //定义结构体
    typedef struct{
        //顶点表
        VerTexType vexs[MVNum];
        //邻接矩阵
        ArcType arcs[MVNum][MVNum];
        //当前顶点数和边数
        int vexnum,arcnum;
    }AMGraph;
    //确定顶点位置
    Status LocateVer(AMGraph G,VerTexType v){
        for (int i = 0; i < G.vexnum; ++i) {
            if (G.vexs[i]==v){
                return i;
            }
        }
        return -1;
    }
    //采用邻接矩阵创建无向图
    Status CreateUDN(AMGraph &G){
        int i,j,k;
        //1.输入总顶点数和总边数
       // cout<<"please input the vexnum and the arcnum:"<<endl;
       cout<<"1.输入总顶点数和总边数"<<endl;
        cin>>G.vexnum;
        cin>>G.arcnum;
        //2.依次输入点的信息存入顶点表中
        cout<<"2.依次输入点的信息存入顶点表中"<<endl;
        for ( i = 0; i < G.vexnum; ++i) {
            cin>>G.vexs[i] ;
        }
        //3.初始化邻接矩阵,使每个权值初始化为最大值
        cout<<"3.初始化邻接矩阵,使每个权值初始化为最大值"<<endl;
        for (i  = 0; i < G.vexnum; ++i) {
            for ( j = 0; j < G.vexnum; ++j) {
                G.arcs[i][j]=MaxInt;
            }
        }
        //4.构造邻接矩阵,依次输入每条边依附的顶点和权值
        cout<<"4.构造邻接矩阵,依次输入每条边依附的顶点和权值"<<endl;
        for ( k = 0; k < G.arcnum; ++k) {
            //1.定义两个顶点和边的权值
            VerTexType v1,v2;
            ArcType w;
            cout<<"Please enter the vertex and weight of each edge in turn:"<<endl;
            cin>>v1>>v2>>w;
            //2.确定两个顶点在图中的位置
            i=LocateVer(G,v1);
            j=LocateVer(G,v2);
            //3.两个顶点之间的权值
            G.arcs[i][j]=w;
            //4.无向图邻接矩阵权值对称
            G.arcs[j][i]=G.arcs[i][j];
    
    
        }
        return OK;
        cout<<endl;
    }
    
    int main() {
        cout<<"----------------Use the Adjacency Matrix CreateUDN------------"<<endl;
        AMGraph G;
        CreateUDN(G);
        cout<<"----------------Show the Adjacency Matrix---------------------"<<endl;
        for (int i = 0; i < G.vexnum; ++i) {
            for (int 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;
                    }
                }
    
            }
    
        }
        cout<<endl;
        return 0;
    }
    
    

    7.运行结果

    验证无向图:
    在这里插入图片描述
    注:原无向图来自百度百科

    ----------------Use the Adjacency Matrix CreateUDN------------
    1.输入总顶点数和总边数
    6 9
    2.依次输入点的信息存入顶点表中
    a b c d e f
    3.初始化邻接矩阵,使每个权值初始化为最大值
    4.构造邻接矩阵,依次输入每条边依附的顶点和权值
    Please enter the vertex and weight of each edge in turn:
    a b 1
    Please enter the vertex and weight of each edge in turn:
    a c 2
    Please enter the vertex and weight of each edge in turn:
    a d 3
    Please enter the vertex and weight of each edge in turn:
    b e 4
    Please enter the vertex and weight of each edge in turn:
    c d 5
    Please enter the vertex and weight of each edge in turn:
    c e 6
    Please enter the vertex and weight of each edge in turn:
    c f 7
    Please enter the vertex and weight of each edge in turn:
    d f 8
    Please enter the vertex and weight of each edge in turn:
    e f 9
    ----------------Show the Adjacency Matrix---------------------1       2       3       ∞      ∞
    1       ∞      ∞      ∞      42       ∞      ∞      5       6       7
    35       ∞      ∞      84       6       ∞      ∞      9
    ∞      ∞      7       8       9

    在这里插入图片描述

    展开全文
  • /* '邻接矩阵' 实现无向图创建、深度优先遍历*/ #include <stdio.h> #include <stdlib.h> #define MaxVex 100 //最多顶点个数 #define INFINITY 32768 //表示极大值,即 ∞ #define TRUE ...

    Code

    /* '邻接矩阵' 实现无向图的创建、深度优先遍历*/
    #include <stdio.h>
    #include <stdlib.h> 
    
    #define MaxVex      100          //最多顶点个数
    #define INFINITY    32768        //表示极大值,即 ∞
    #define TRUE        1
    #define FALSE       0
    #define OK          1
    #define ERROR       0
    
    typedef char VertexType;    //假设顶点数据类型为字符类型
    typedef int  EdgeType;      //对于无权图,用1或0表示是否相邻,对带权图,则为权值类型 
    typedef struct
    {
        VertexType vertex[MaxVex];            //顶点数组
        EdgeType arcs[MaxVex][MaxVex];       //邻接矩阵
        int    vexnum,arcnum;                //图中的顶点数和边数 
    }Graph;
    
    int visited[MaxVex];    //访问标志数组    
    
    /**********************各个子函数的定义*********************/
    void init(Graph *G);                    //初始化邻接矩阵 
    int LocateVertex(Graph *G,VertexType v);//求顶点位置函数
    int createUDG(Graph *G);                //创建一个无向图 
    void DepthFirstSearch(Graph G, int i);  //图的深度优先遍历
    void TraverseGraph(Graph G);
    
    /**************************主函数*************************/
    int main()
    {
        Graph G;
        int choice;
        while(true)
        {
             printf("*****************Please enter your choice*****************\n\n");
            printf("                choice 1:Initialization\n");
            printf("                choice 2:Create Graph\n");
                    printf("                choice 3:Depth First Search\n");       
            printf("                choice 0:exit\n\n");
             scanf("%d",&choice);
            switch(choice)
            {
                case 1:
                    init(&G);
                    break;
                case 2:
                    (createUDG(&G)==1)?printf("Create Graph success.\n"):printf("Create Graph ERROR\n");
                    break;
                case 3:
                    printf("图的深度优先遍历为: ");
                    TraverseGraph(G);
                    break;        
                case 0:
                    exit(0);
                    break;
                default:
                    printf("ERROR!!\n");
                    exit(0);
                    break;
            }
        }
        return 0;
    } 
    
    /**********************各个子函数功能的实现*********************/
    void init(Graph *G)   //初始化邻接矩阵 
    {
        int i,j;
        printf("请输入图的顶点个数和边数:"); 
        scanf("%d %d",&(G->vexnum),&(G->arcnum));//输入图的顶点个数和边数 
        for(i=0;i<G->vexnum;i++)              //初始化
        {
            for(j=0;j<G->vexnum;j++)
            {
                G->arcs[i][j]=INFINITY;
            }
        } 
        printf("图的初始化成功\n"); 
    }
    
    int LocateVertex(Graph *G,VertexType v)  //查找并返回顶点的位置 
    {
        int j=0,k;
        for(k=0;k<G->vexnum;k++)
        {
            if(G->vertex[k]==v)
            {
                j=k;
                break;
            }
        }
        return j;    
    }
    
    int createUDG(Graph *G)  //创建一个无向图
    {
        int i,j,k,weight;
        VertexType v1,v2;
        for(i=0;i<G->vexnum;i++)
        {
            printf("请输入图的第 %d 顶点:",i+1);
            getchar();
            scanf("%c",&(G->vertex[i]));     //输入图的顶点集 
        } 
        for(k=0;k<G->arcnum;k++)
        {
            printf("请分别输入图的第 %d 条边的两个顶点和权值",k+1);
            getchar();
            scanf("%c %c %d",&v1,&v2,&weight);//输入一条边的两个顶点、权值 
            i=LocateVertex(G,v1);
            j=LocateVertex(G,v2);
            G->arcs[i][j]=weight;     //建立顶点之间的关系 
            G->arcs[j][i]=weight;
        } 
        return OK;
    }
    
    void DepthFirstSearch(Graph G, int i)   //图的深度优先遍历
    {
        int j;
        visited[i] = TRUE;
        printf("%c ",G.vertex[i]);  
        for (j=0; j<G.vexnum; j++)
        {
            if (G.arcs[i][j]!=INFINITY  &&  !visited[j])
                DepthFirstSearch(G,j);
        }
    }
    
    void TraverseGraph(Graph G)
    {
        int i;
        for (i=0; i<G.vexnum; i++)   //初始化访问标志数组
            visited[i] = FALSE;
    
        for (i=0; i<G.vexnum; i++)//循环调用深度优先遍历连通子图的操作,若图G是连通图,则此调用只执行一次 
        {
            if (!visited[i])
                DepthFirstSearch(G, i);
        }
        printf("\n");
    }

    代码测试

    转载于:https://www.cnblogs.com/qftm/p/10317151.html

    展开全文
  • 可考虑用一维数组来存储的结点信息,二维数组来存储节点间的关系,这种存储方式就叫做邻接矩阵的结点结构定义: typedef struct { char vexs[ MVNum ] ;//存储结点信息 int arcs[ MVNum ][ MVNum ] ; //...

    由于图的复杂结构,其物理位置与逻辑位置并不匹配,不能用一维数组来存储图。可考虑用一维数组来存储图的结点信息,二维数组来存储节点间的关系,这种存储方式就叫做邻接矩阵。

    图的结点结构定义:

    typedef struct
    {
        char vexs[ MVNum ] ;//存储结点信息
        int arcs[ MVNum ][ MVNum ] ; //存储权值
        int vexnum , arcnum ;//定义图的节点个数和边的条数
    }AMGraph ;
    

    查找结点元素在vexs[]数组中的下标:

    int LocateVex( AMGraph G , char ch )
    {
        int i ;
        for( i = 0 ; i < G.vexnum ; i++ )
            if( ch == G.vexs[ i ] )
                break ;
        return i ;
    
    }
    

    创建图:

    在创建图的过程中,如果结点信息是字符,且用scanf()函数从键盘读取的话,一定要用getchar()将键盘输入后的回车键吸收。这是因为当用户按下回车键时,回车符还在缓冲区内,当下一次调用scanf()时,程序会读取缓冲区内遗留的回车符。关于scanf()的更加详细的解释:C语言scanf函数用法详细解释!

    Status CreateUDN( AMGraph *G )
    {
        int i , j ;
        printf( "请输入结点个数:" ) ;
        scanf( "%d" , &G->vexnum ) ;
        getchar() ;
    
        for( i = 0 ; i < G->vexnum ; i++ )
        {
            printf( "请输入第%d个结点的信息:" , i+1 ) ;
            scanf( "%c" , &G->vexs[ i ] ) ;
            getchar() ;
        }
    
        for( i = 0 ; i < G->vexnum ; i++ )
            for( j = 0 ; j < G->vexnum ; j++ )
                G->arcs[ i ][ j ] = MaxInt ;
    
        printf( "请输入边的条数:" ) ;
        scanf( "%d" , &G->arcnum ) ;
        getchar() ;
    
        for( i = 0 ; i < G->arcnum ; i++ )
        {
            int w ;
            char a , b ;
            printf( "请输入两个结点以及两节点间的边的权值:" ) ;
            scanf( "%c %c %d" , &a , &b , &w ) ;
            getchar() ;
    
            G->arcs[ LocateVex( *G , a ) ][ LocateVex( *G , b ) ] = w ;
            G->arcs[ LocateVex( *G , b ) ][ LocateVex( *G , a ) ] = w ;
    
        }
        return OK ;
    }
    

    邻接矩阵实现DFS算法:

    DFS就相当于树的前序遍历。

    用visited[]数组来标志结点是否已被遍历过。

    void DFS( AMGraph G , int i )
    {
        int j ;
        visited[ i ] = TRUE ;
        printf( "%c " , G.vexs[ i ] ) ;
    
        for( j = 0 ; j < G.vexnum ; j++ )
            if( !visited[ j ] && G.arcs[ i ][ j ] < MaxInt && G.arcs[ i ][ j ] > 0 )
                DFS( G , j ) ;
    }
    
    void DFSTraverse( AMGraph G )
    {
        int i ;
        for( i = 0 ; i < G.vexnum ; i++ )
            visited[ i ] = FALSE ;
    
        for( i = 0 ; i < G.arcnum ; i++ ) 
            if( !visited[ i ] )
                DFS( G , i ) ;
    }
    

    这里对每个结点都实现DFS可以避免不能遍历非连通图的情况。

    邻接矩阵实现BFS算法:

    BFS算法需借助于队列来实现,其基本思想是:遍历第一个结点,并将其入队之后,再把它出队,然后把与这个结点相连的所有结点都入队,每遍历一次都进行这样的操作,BFS就相当于树的层序遍历

    void BFSTraverse( AMGraph G )
    {
        char temp ;
        int i , j ;
        Queue Q ;
        InitQueue( &Q ) ;
        for( i = 0 ; i < G.vexnum ; i++ )
            visited[ i ] = FALSE ;
    
        for( i = 0 ; i < G.vexnum ; i++ )
        {
            if( !visited [ i ] )
            {
                visited[ i ] = TRUE ;
                printf( "%c " , G.vexs[ i ] ) ;
                EnQueue( &Q , G.vexs[ i ] ) ;
    
                while( !EmptyQueue( Q ) )
                {
                    DeQueue( &Q , &temp ) ;
                    for( j = 0 ; j < G.vexnum ; j++ )//将与刚刚遍历过的结点相连的结点都入队
                    {
                        if( G.arcs[ i ][ j ] < MaxInt && G.arcs[ i ][ j ] > 0 && !visited[ j ] )
                        {
                            visited[ j ] = TRUE ;
                            printf( "%c " , G.vexs[ j ] ) ;
                            EnQueue( &Q , G.vexs[ j ] ) ;
                        }
                    }
                }
            }
        }
        printf( "\n" ) ;
    }
    

    判断队列已满和入队与出队的操作比较简单,这里就不一一列出。

    附上源代码:

    #include<stdio.h>
    #include<stdlib.h>
    
    #define MVNum 100
    #define MaxInt 32767
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    typedef char VerTexType ;
    typedef int ArcType ;
    typedef int Status ;
    typedef int Boolean ;
    
    typedef struct
    {
        VerTexType vexs[ MVNum ] ;
        ArcType arcs[ MVNum ][ MVNum ] ;
        int vexnum , arcnum ;
    }AMGraph ;
    
    typedef struct
    {
        char *base ;
        int front ;
        int rear ;
    }Queue ;
    
    Boolean visited[ MaxInt ] ;
    
    Status CreateUDN( AMGraph *G ) ;
    void DFS( AMGraph G , int i ) ;
    void DFSTraverse( AMGraph G ) ;
    int LocateVex( AMGraph G , char ch ) ;
    
    void InitQueue( Queue *Q ) ;
    int EmptyQueue( Queue Q ) ;
    int EnQueue( Queue *Q , char ch ) ;
    int DeQueue( Queue *Q , char *ch ) ;
    void BFSTraverse( AMGraph G ) ;
    
    int main( void )
    {
        AMGraph G ;
        CreateUDN( &G ) ;
        DFSTraverse( G ) ;
        BFSTraverse( G ) ;
        return 0 ;
    }
    
    int LocateVex( AMGraph G , char ch )
    {
        int i ;
        for( i = 0 ; i < G.vexnum ; i++ )
            if( ch == G.vexs[ i ] )
                break ;
        return i ;
    
    }
    
    Status CreateUDN( AMGraph *G )
    {
        int i , j ;
        printf( "请输入结点个数:" ) ;
        scanf( "%d" , &G->vexnum ) ;
        getchar() ;
    
        for( i = 0 ; i < G->vexnum ; i++ )
        {
            printf( "请输入第%d个结点的信息:" , i+1 ) ;
            scanf( "%c" , &G->vexs[ i ] ) ;
            getchar() ;
        }
    
        for( i = 0 ; i < G->vexnum ; i++ )
            for( j = 0 ; j < G->vexnum ; j++ )
                G->arcs[ i ][ j ] = MaxInt ;
    
        printf( "请输入边的条数:" ) ;
        scanf( "%d" , &G->arcnum ) ;
        getchar() ;
    
        for( i = 0 ; i < G->arcnum ; i++ )
        {
            int w ;
            char a , b ;
            printf( "请输入两个结点以及两节点间的边的权值:" ) ;
            scanf( "%c %c %d" , &a , &b , &w ) ;
            getchar() ;
    
            G->arcs[ LocateVex( *G , a ) ][ LocateVex( *G , b ) ] = w ;
            G->arcs[ LocateVex( *G , b ) ][ LocateVex( *G , a ) ] = w ;
    
        }
        return OK ;
    }
    
    void DFS( AMGraph G , int i )
    {
        int j ;
        visited[ i ] = TRUE ;
        printf( "%c " , G.vexs[ i ] ) ;
    
        for( j = 0 ; j < G.vexnum ; j++ )
            if( !visited[ j ] && G.arcs[ i ][ j ] < MaxInt && G.arcs[ i ][ j ] > 0 )
                DFS( G , j ) ;
    }
    
    void DFSTraverse( AMGraph G )
    {
        int i ;
        for( i = 0 ; i < G.vexnum ; i++ )
            visited[ i ] = FALSE ;
    
        for( i = 0 ; i < G.arcnum ; i++ )
            if( !visited[ i ] )
                DFS( G , i ) ;
    
        printf( "\n" ) ;
    }
    
    void InitQueue( Queue *Q )
    {
        Q->base = ( char * )malloc( sizeof( char ) * MaxInt ) ;
        Q->front = Q->rear = 0 ;
    }
    
    int EmptyQueue( Queue Q )
    {
        if( Q.front == Q.rear )
            return TRUE ;
        else
            return FALSE ;
    }
    
    int EnQueue( Queue *Q , char ch )
    {
        if( ( Q->rear + 1 ) % MaxInt == Q->front )
            return ERROR ;
        else
        {
            Q->base[ Q->rear ] = ch ;
            Q->rear = ( Q->rear +1 ) % MaxInt ;
        }
            return OK ;
    }
    
    int DeQueue( Queue *Q , char *ch )
    {
        if( EmptyQueue( *Q ) )
            return ERROR ;
        else
        {
            *ch = Q->base[ Q->front ] ;
            Q->front = ( Q->front + 1 ) % MaxInt ;
        }
            return OK ;
    }
    
    void BFSTraverse( AMGraph G )
    {
        char temp ;
        int i , j ;
        Queue Q ;
        InitQueue( &Q ) ;
        for( i = 0 ; i < G.vexnum ; i++ )
            visited[ i ] = FALSE ;
    
        for( i = 0 ; i < G.vexnum ; i++ )
        {
            if( !visited [ i ] )
            {
                visited[ i ] = TRUE ;
                printf( "%c " , G.vexs[ i ] ) ;
                EnQueue( &Q , G.vexs[ i ] ) ;
    
                while( !EmptyQueue( Q ) )
                {
                    DeQueue( &Q , &temp ) ;
                    for( j = 0 ; j < G.vexnum ; j++ )
                    {
                        if( G.arcs[ i ][ j ] < MaxInt && G.arcs[ i ][ j ] > 0 && !visited[ j ] )
                        {
                            visited[ j ] = TRUE ;
                            printf( "%c " , G.vexs[ j ] ) ;
                            EnQueue( &Q , G.vexs[ j ] ) ;
                        }
                    }
                }
            }
        }
        printf( "\n" ) ;
    }
    
    展开全文
  • } } //采用邻接矩阵表示法,创建无向图G //算法思想: // 1.输入总顶点和总边数 // 2.依次输入点的信息存于顶点表中 // 3.初始化邻接矩阵,如果是无向图图,初始化为0,如果是无向网,则初始化为极大值 // 4.构造...

    1.完整代码

    #include<iostream>
    using namespace std;
    
    #define OK 		1
    #define ERROR 	0
    #define MaxInt 	0		
    #define MVNum 	100			//最大顶点数
    #define Max 	20
    typedef char VerTexType;	//顶点的数据类型为字符型 
    typedef int ArcType; 		//权值类型为整形
    typedef int Status;
    
    typedef struct{
    	VerTexType vexs[MVNum];			//顶点表 
    	ArcType arcs[MVNum][MVNum];		//邻接矩阵 
    	int vexnum, arcnum;				//图的当前点数和边数 
    }AMGraph;	//Adjacency Matrix Graph 
    
    /****************************图的创建*******************************/ 
    //在图G中查找顶点u,存在则返回顶点表中的下标i 
    Status LocateVex(AMGraph G, VerTexType u)
    {
    	for(int i = 0; i < G.vexnum; ++i)
    	{
    		if( u == G.vexs[i] )
    			return i;
    	}
    }
    
    //采用邻接矩阵表示法,创建无向图G 
    //算法思想:
    //	1.输入总顶点和总边数
    //	2.依次输入点的信息存于顶点表中
    //	3.初始化邻接矩阵,如果是无向图图,初始化为0,如果是无向网,则初始化为极大值
    //	4.构造邻接举证 
    Status CreatUDN(AMGraph &G)
    {
    	VerTexType v1, v2;
    	int w;
    	cout << "输入总顶点数: " << endl;
    	cin >> G.vexnum;
    	cout << "输入总边数: "<< endl;	
    	cin >> G.arcnum;					//输入总顶点数,总边数
    	
    	cout << "请输入所有顶点:" << endl;
    	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;		//边的权值均置为极大值 
    		}
    	}
    	
    	cout << "分别输入一条边依附的两个顶点和权值:" << endl;
    	for(int k = 0; k < G.arcnum; ++k)
    	{
    		cin >> v1 >> v2 >> w;
    		int m = LocateVex(G, v1);
    		int n = LocateVex(G, v2);
    		G.arcs[m][n] = w;					 
    		G.arcs[n][m] = w;				//(如果是有向图,则不需要给G.arcs[n][m]赋值)
    	}
    	return OK;
    }
    
    
    /****************************图的打印和遍历*******************************/ 
    //打印图的顶点 
    void PrintVex(AMGraph G)
    {
    	cout << "  ";
    	for (int i = 0;i < G.vexnum;i++)
    	{
    		cout << G.vexs[i] << " ";
    	}
    	cout << endl;
    }
    
    //打印图的边 
    void PrintEdge(AMGraph G)
    {
    	for (int i = 0;i < G.vexnum;i++)
    	{
    		cout << G.vexs[i] << " "; 
    		for (int j = 0;j < G.vexnum;j++)
    		{
    			cout << G.arcs[i][j] << " ";
    		}
    		cout << endl;
    	}
    }
    
    //深度优先遍历 
    bool visited[Max];					//定义布尔型数组作为标记数组 
    void DFS(AMGraph G, int v)
    {
    	cout << G.vexs[v];				//访问第v个结点 
    	visited[v] = true;
    	for(int w = 0; w < G.vexnum; w++)
    	{
    		if( (G.arcs[v][w] != 0) && (!visited[w]) )
    		{
    			cout << "->";
    			DFS(G, w);				//对v的尚未访问的邻接顶点w递归调用DFS 
    		}
    			
    	}
    }
    
    void DFSTraverse(AMGraph G)
    {
    	for (int i = 0;i < Max;i++)			//初始化访问标记数组
    	{
    		visited[i] = false;
    	}
    	for (int i = 0;i < G.vexnum;i++)	//对每个连通分量进行遍历
    	{
    		if (!visited[i])				
    		{
    			DFS(G, i);					//对尚未访问的顶点调用DFS 
    			cout << endl;
    		}
    	}
    }
    
    /****************************主函数*******************************/ 
    int main()
    {
    	AMGraph G;
    	CreatUDN(G);
    	cout << "创建的图为:" << endl;
    	PrintVex(G);
    	PrintEdge(G);
    	cout << "深度遍历顺序为:" << endl;	
    	DFSTraverse(G);
    	cout << endl;
    	
    	return 0;
    }
    

    2.测试结果

    在这里插入图片描述

    展开全文
  • 文章目录邻接矩阵创建无向网代码实现邻接表创建无向图代码实现 邻接矩阵创建无向网代码实现 #include<iostream> using namespace std; #define OK 1 #define Maxint 32767 typedef int status ; typedef ...
  • 有向图不对称邻接矩阵无向图对称邻接矩阵 一个简单图实例 import numpy as np # 使用numpy编写的上述有向图的邻接矩阵如下: # 不对称邻接矩阵 A = np.matrix([ [0,1,0,0], [0,0,1,1], [0,1,0,0], [1,0,1,0]...
  • 主要介绍了Python根据已知邻接矩阵绘制无向图操作,涉及Python使用networkx、matplotlib进行数值运算与图形绘制相关操作技巧,需要的朋友可以参考下
  • 基于邻接矩阵无向图的构建2.深度优先遍历3.广度优先遍历伪代码:构建:1.初始化标志数组2.输入顶点数、边数、顶点信息、边的信息3.初始化arc、vertex深度优先遍历(栈)1.输出一个顶点v并将其标志为已遍历2.递归...
  • C++邻接矩阵构造无向图和无向网

    千次阅读 2019-05-31 21:24:57
    假设我们要创建一个无向图邻接矩阵 #include<iostream> #define OK 1 #define ERROR 0 #define MaxNum 100 //最大顶点数 typedef char VexType; //顶点数据类型为char型 typedef int VarType; //边的...
  • 无向图邻接矩阵创建表示

    千次阅读 2017-04-05 20:44:02
    无向图邻接矩阵创建
  • 邻接矩阵画有向图、无向图

    万次阅读 2017-07-19 10:39:08
    邻接矩阵画有向图、无向图邻接矩阵画有向图的逻辑如下: 设邻接矩阵的行(列)数为N,矩阵中非零元素的个数为M,画布宽为W、高为H 1、有向图顶点数为N、有向边数为M,问题转化为:画正N边形的所有顶点、以及顶点...
  • 邻接矩阵实现无向图创建

    万次阅读 2016-11-22 21:45:47
    #include #define Maxsize 50 #define M 5000//定义无穷数值为5000 typedef struct { char vex[Maxsize];...//矩阵表 int numVertexes,numEdges;//顶点数和边数 }MGraph; void GreateGraph(MGraph *
  • 如何用邻接矩阵判断无向图的连通性? 要Java或者C#的实现思路,最好有代码。
  • 网上查了很多资料,发现主要是使用邻接表来实现图,并进行遍历的。而采用邻接矩阵的就非常少...不想看的可以直接下载:python 邻接矩阵三种方法实现有向图、无向图,并绘图显示不废话。上代码首先图类 class Graph_Matr
  • 邻接矩阵创建图

    千次阅读 2019-05-30 17:53:52
    邻接矩阵创建图用的二维数组创建图,是用顺序存储结构实现的; 邻接矩阵创建图的过程也就是给二维数组赋值的过程 的数据结构: public class Graph { String[] vertex = new String[5]; //顶点类型可自定义 ...
  • 邻接矩阵无向图

    千次阅读 2017-12-29 21:15:58
    无向图和有向图在邻接矩阵中的表示方法:  无向图和有向图大同小异,在这里只以无向图为例,代码部分通过简单调整即可对应编译有向图 邻接矩阵数据类型定义 #define MaxVertices 100 //定义最大容量 ...
  • 无向图邻接矩阵创建

    千次阅读 多人点赞 2019-01-29 16:00:49
    首先创建邻接矩阵的结构体,变量有存放顶点信息的一维数组(Vexs),存放边的信息的二维数组(Edge),当前的顶点数和边数这四个变量,然后创建一个子函数CreateMGraph用来创建无向图邻接矩阵,在创建一个子函数...
  • Matlab中根据邻接矩阵做图 function tu_plot(rel,control) ...%第二个输入为控制量,0表示无向图,1表示有向图。默认值为0 r_size=size(rel); if nargin<2 control=0; end if r_size(1)~=r_size(2) di...
  • 邻接矩阵建立无向图

    千次阅读 2018-05-25 20:27:10
    #include&lt;iostream&gt; using namespace std; const int MaxSize=10; class MGraph {public: MGraph(int n,int e){vertexNum=n;arcNum=e; for(int i=0;i&lt;vertexNum;i++){cout&......
  • #include #include #include #define MAXSIZE 100 #define MaxInt 32767 //表示最大值,即正无穷大 #define ... } } //输出邻接矩阵 void PrintAM(AMGraph &G){ printf("\n输出邻接矩阵:\n"); for(int i=0;i
  • 邻接矩阵实现无向图的BFS和DFS

    千次阅读 2018-09-13 21:45:19
    创建邻接矩阵图的结构体 typedef struct graph { int vexnum,arcnum;//节点个数,弧的个数 int tyust[MAX][MAX];//使用二维数组定义一个矩阵 char vexs[MAX];//存储节点数据 }*Graph; 创建邻接矩阵图 Graph ...
  • 图的创建及深度广度遍历的代码实现,基于的是邻接矩阵,图这里是无向图,并且两个顶点之间有连接则邻接矩阵非零,如果没有连接则为零 public class Graph { //图的邻接矩阵形式 private int[][] edges; private ...
  • 使用邻接矩阵存储无向图

    千次阅读 2019-05-11 21:21:00
    使用邻接矩阵存储下图所示无向图 **  ** 解题思路  创建一个邻接矩阵 程序实现 #include #include #define MAXVEX 10 /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef int Status;...
  • 邻接矩阵实现无权无向图、带权无向图 java 1.图的接口 import java.util.List; public interface Graph { public int getSize(); //返回图中的顶点数 public List getVertices(); //返回图形中的顶点 public V ge...
  • #include &lt;iostream&gt;#include&lt;stdlib.h&gt;#include&lt;stdio.h&...#define MVNum 100using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MAXQSIZE ...
  • C++邻接矩阵实现有向图、无向图

    千次阅读 2017-05-03 19:49:45
    /*********************邻接矩阵实现无向图******************/ class MatrixUDG { private: char mVexs[MAX];//顶点集合 int mVexBum;//顶点数 int mEdgNum;//边数 int mMatrix[MAX][MAX];//邻接矩阵 char ...
  • //环境:vs2010 //MGraph.h #ifndef MGraph_H //定义头文件 #define MGraph_H const int MaxSize = 10; //中最多顶点个数 template &lt;class DataType&gt; class MGraph { public: MGraph(...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,491
精华内容 9,796
关键字:

邻接矩阵创建无向图