精华内容
下载资源
问答
  • 关于临界矩阵和邻接表的使用情况 在很多图论的题目中,如果题目本身没有明确指出两个顶点只有最多只有一条直达的边的话那么最好使用邻接表来存储所有的边,因为邻接矩阵会用某一条边来覆盖之前的边,这条边可以是...

    关于临界矩阵和邻接表的使用情况

    在很多图论的题目中,如果题目本身没有明确指出两个顶点只有最多只有一条直达的边的话那么最好使用邻接表来存储所有的边,因为邻接矩阵会用某一条边来覆盖之前的边,这条边可以是最后输入的边,也可以是你设定了相应条件的边,如果这下边的边权不一样,就会很容易出现错误。比如求最短路的时候用之后出现的边覆盖了最短的边,或者是求边的入度出度的时候只记录了一条边以至于出错。

    HDU 3342 Legal or Not

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
    Total Submission(s): 11758    Accepted Submission(s): 5532


    Problem Description
    ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many "holy cows" like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost "master", and Lost will have a nice "prentice". By and by, there are many pairs of "master and prentice". But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?

    We all know a master can have many prentices and a prentice may have a lot of masters too, it's legal. Nevertheless,some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian's master and, at the same time, 3xian is HH's master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not.

    Please note that the "master and prentice" relation is transitive. It means that if A is B's master ans B is C's master, then A is C's master.
     

    Input
    The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y's master and y is x's prentice. The input is terminated by N = 0.
    TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,..., N-1). We use their numbers instead of their names.
     

    Output
    For each test case, print in one line the judgement of the messy relationship.
    If it is legal, output "YES", otherwise "NO".
     

    Sample Input
    3 2 0 1 1 2 2 2 0 1 1 0 0 0
     

    Sample Output
    YES NO

    使用邻接矩阵的错误做法:

    #include <iostream>
    #include <queue>
    #include <stdlib.h>
    #include <stdio.h>
    #include <map>
    #include <string>
    #include <cstdlib>
    #include <stack>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    #include <typeinfo>
    #include <cstring>
    
    
    using namespace std;
    typedef long long ll;
    
    const ll inf = 1061109567;
    const int maxn = 1002;
    
    int n,m;
    
    int mat[maxn][maxn];
    
    int vex_in[maxn];
    
    
    int TopoSort(){
        queue<int> q;
        int s[maxn]={0};
        int cnt=0;
        for(int i=0;i<n;i++){
            if(vex_in[i]==0)    q.push(i);
        }
    
        while(!q.empty()){
            int p=q.front();
            q.pop();
            s[p]=1;
            cnt++;
            for(int i=0;i<n;i++){
                if(mat[p][i]){
                    vex_in[i]--;
                    if(vex_in[i]==0)    q.push(i);
                }
            }
        }
        /*for(int i=0;i<n;i++)
            if(!s[i])    return 0;*/
        if(cnt!=n)    return 0;
        return 1;
    }
    
    int main(int argc, char const *argv[])
    {
        while(cin>>n>>m&&m&&n){
            for(int i=0;i<n;i++){
                vex_in[i]=0;
                for(int j=0;j<n;j++){
                    mat[i][j]=0;
                }
            }
    
            int a,b;
            for(int i=0;i<m;i++){
                cin>>a>>b;
                mat[a][b]=1;
                vex_in[b]++;
            }
            if(TopoSort())
                cout<<"YES";
            else cout<<"NO";
            cout<<endl;
        }
        return 0;
    }
    

    此时莫名奇妙的wa,虽然我没见到测试样例,但是猜测可能是存在上述说的情况。于是改用邻接表a了。

    
    #include <iostream>
    #include <queue>
    #include <stdlib.h>
    #include <stdio.h>
    #include <map>
    #include <string>
    #include <cstdlib>
    #include <stack>
    #include <vector>
    #include <math.h>
    #include <algorithm>
    #include <typeinfo>
    #include <cstring>
    
    
    using namespace std;
    typedef long long ll;
    
    const ll inf = 1061109567;
    const int maxn = 1002;
    
    int n,m;
    
    int mat[maxn][maxn];
    
    std::vector<int> edge[maxn];
    
    int vex_in[maxn];
    
    
    int TopoSort(){
    	queue<int> q;
    	//int s[maxn]={0};
    	int cnt=0;
    	for(int i=0;i<n;i++){
    		if(vex_in[i]==0)	q.push(i);
    	}
    
    	while(!q.empty()){
    		int p=q.front();
    		q.pop();
    		//s[p]=1;
    		cnt++;
    		int len=edge[p].size();
    		for(int i=0;i<len;i++){
    			vex_in[edge[p][i]]--;
    			if(vex_in[edge[p][i]]==0)	q.push(edge[p][i]);
    		}
    	}
    	/*for(int i=0;i<n;i++)
    		if(!s[i])	return 0;*/
    	if(cnt!=n)	return 0;
    	return 1;
    }
    
    int main(int argc, char const *argv[])
    {
    	while(cin>>n>>m&&m&&n){
    		for(int i=0;i<n;i++){
    			vex_in[i]=0;
    			edge[i].clear();
    		}
    
    		int a,b;
    		for(int i=0;i<m;i++){
    			cin>>a>>b;
    			edge[a].push_back(b);
    			vex_in[b]++;
    		}
    		if(TopoSort())
    			cout<<"YES";
    		else cout<<"NO";
    		cout<<endl;
    	}
    	return 0;
    }
    
    展开全文
  • 邻接矩阵和邻接

    千次阅读 2017-10-27 20:08:24
    /* 图的邻接矩阵表示法 */#define MaxVertexNum 100 /* 最大顶点数设为100 */ #define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/ typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ typedef int...
    /* 图的邻接矩阵表示法 */
    
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    #define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
    
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
    
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{
        int Nv;  /* 顶点数 */
        int Ne;  /* 边数   */
        WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
        DataType Data[MaxVertexNum];      /* 存顶点的数据 */
        /* 注意:很多情况下,顶点无数据,此时Data[]可以不用出现 */
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
    
    
    
    MGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V, W;
        MGraph Graph;
    
        Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接矩阵 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
        for (V=0; V<Graph->Nv; V++)
            for (W=0; W<Graph->Nv; W++)  
                Graph->G[V][W] = INFINITY;
    
        return Graph; 
    }
    
    void InsertEdge( MGraph Graph, Edge E )
    {
         /* 插入边 <V1, V2> */
         Graph->G[E->V1][E->V2] = E->Weight;    
         /* 若是无向图,还要插入边<V2, V1> */
         Graph->G[E->V2][E->V1] = E->Weight;
    }
    
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
    
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
    
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */ 
            E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */ 
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        } 
    
        /* 如果顶点有数据的话,读入数据 */
        for (V=0; V<Graph->Nv; V++) 
            scanf(" %c", &(Graph->Data[V]));
    
        return Graph;
    }
    /* 图的邻接表表示法 */
    
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
    
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
    
    /* 邻接点的定义 */
    typedef struct AdjVNode *PtrToAdjVNode; 
    struct AdjVNode{
        Vertex AdjV;        /* 邻接点下标 */
        WeightType Weight;  /* 边权重 */
        PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
    };
    
    /* 顶点表头结点的定义 */
    typedef struct Vnode{
        PtrToAdjVNode FirstEdge;/* 边表头指针 */
        DataType Data;            /* 存顶点的数据 */
        /* 注意:很多情况下,顶点无数据,此时Data可以不用出现 */
    } AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
    
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{  
        int Nv;     /* 顶点数 */
        int Ne;     /* 边数   */
        AdjList G;  /* 邻接表 */
    };
    typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
    
    
    
    LGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V;
        LGraph Graph;
    
        Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接表头指针 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
           for (V=0; V<Graph->Nv; V++)
            Graph->G[V].FirstEdge = NULL;
    
        return Graph; 
    }
    
    void InsertEdge( LGraph Graph, Edge E )
    {
        PtrToAdjVNode NewNode;
    
        /* 插入边 <V1, V2> */
        /* 为V2建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V2;
        NewNode->Weight = E->Weight;
        /* 将V2插入V1的表头 */
        NewNode->Next = Graph->G[E->V1].FirstEdge;
        Graph->G[E->V1].FirstEdge = NewNode;
    
        /* 若是无向图,还要插入边 <V2, V1> */
        /* 为V1建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V1;
        NewNode->Weight = E->Weight;
        /* 将V1插入V2的表头 */
        NewNode->Next = Graph->G[E->V2].FirstEdge;
        Graph->G[E->V2].FirstEdge = NewNode;
    }
    
    LGraph BuildGraph()
    {
        LGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
    
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
    
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */ 
            E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ 
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        } 
    
        /* 如果顶点有数据的话,读入数据 */
        for (V=0; V<Graph->Nv; V++) 
            scanf(" %c", &(Graph->G[V].Data));
    
        return Graph;
    }
    展开全文
  • 数据结构学习笔记----【图】邻接矩阵和邻接表转换代码邻接矩阵-->邻接表要求INPUTOUTPUTSAMPLE代码实现重点邻接表--->邻接矩阵 转载参考:https://blog.csdn.net/qwm8777411/article/details/8990718 邻接矩阵...

    数据结构学习笔记----【图】邻接矩阵和邻接表转换代码


    转载参考:https://blog.csdn.net/qwm8777411/article/details/8990718

    邻接矩阵–>邻接表

    要求

    带权 有向图 邻接矩阵表示 转换为 邻接表

    INPUT

    1.图的节点数、图的边数 m n
    2. n*n 矩阵(数字间以空格空开,非零表示权)

    OUTPUT

    m个结点 则输出m行
    对应结点连接情况

    SAMPLE

    6 10
    0 5 0 7 0 0
    0 0 4 0 0 0
    8 0 0 0 0 0
    0 0 5 0 0 6
    0 0 5 0 0 0
    3 0 0 0 1 0

    0:1 3
    1:2
    2:0
    3:2 5
    4:2
    5:0 4

    代码实现

    `# include<stdio.h>
    # include <malloc.h>
    
    #include <iostream>
    using namespace std;
    typedef  int InfoType;
    #define MAXV 100    //最大顶点个数
    #define INF 32767   //INF 正无穷
    
    //定义邻接矩阵类型
        //顶点
        typedef struct{
             int no;//定点编号
             InfoType info;//顶点其他信息
        }VertexType;//顶点类型
        //图
        typedef struct{
           int edges[MAXV][MAXV];//邻接矩阵
           int vertexNum,arcNum;//顶点数 边数
          VertexType vexs[MAXV];//存放顶点信息
        }MGraph;//图的邻接矩阵类型
    
    //邻接表类型
    
    //表节点类型
        typedef struct ANode{
          int adjvex; //这条弧的终点 <i,j>
          struct ANode *nextarc; //指向下一条边的指针
         InfoType infoType;//相关信息,用于存放权值
        }ArcNode;
    
    //头节点类型
        typedef struct VNode{
            typedef int Vertex;
            Vertex data;//顶点信息
            ArcNode *firstarc;//指向第一条边
            //有趣啊,顺序&结构体
        }VNode;
        typedef VNode AdjList[MAXV];	//AdjList是邻接表类型
    
        typedef struct{
          AdjList adjList;
          int vertexNum,e;//顶点数和边数
        }ALGraph;
    
    //==============================================
        //邻接矩阵转换成邻接表
        void MatToList(MGraph &M, ALGraph *&A){
            int i,j;
            ArcNode *p;
    
            //给邻接表分配内存
            A = (ALGraph*)malloc(sizeof(ALGraph));
            //遍历头节点 赋初值
            for(i=0;i<M.vertexNum;i++)
                A->adjList[i].firstarc=NULL;
    
            //遍历邻接矩阵中的所有元素
            for(i=0;i<M.vertexNum;i++)
                for(j=0;j<i;j++)
                    if(M.edges[i][j]!=0) {//存在<i,j>边
                        p=(ArcNode*)malloc(sizeof(ArcNode)); //创建一个新的表结点
                        p->adjvex=j;    //弧的终点为j
                        p->nextarc=A->adjList[i].firstarc; //邻接表: 头节点 表结点;
                        // 新的表结点的链域nextarc存放 之前表结点的地址(在头节点的链域里)
                        A->adjList[i].firstarc=p;//将p接在头节点后面
                    }
    
    
    
        }
    
    
        //输出邻接矩阵M
        void DispMat(MGraph M)
        {
            int i,j;
            for(i=0;i<M.vertexNum;i++)
                for(j=0;j<M.vertexNum;j++)
                    printf("%3d",M.edges[i][j]);
                printf("\n");
        }
    
        //输出邻接表
        void DispAdj(ALGraph *A)
        {
            int i;
            ArcNode *p;
            for(i=0;i<A->vertexNum;i++)
            {
                p=A->adjList[i].firstarc;
                cout<<i<<":";
                while (p!=NULL)
                {
                    cout<<p->adjvex<<"";
                    p=p->nextarc;
                }
                printf("\n");
            }
        }
    
    
        // main
        int main(){
            int i,j;
            MGraph M;
            ALGraph *A;
    
            int m,n;
            cin>>n>>m;//n节点数 m边数
            int k[n][n];
            for(int i=0;i<M.vertexNum;i++){
                for(int j=0;j<M.vertexNum;j++){
                    cin>>k[i][j];
                }
            }
            M.vertexNum=n;
            M.arcNum=m;
    
            for(i=0;i<M.vertexNum;i++)
                for(j=0;j<M.vertexNum;j++)
                    M.edges[i][j]=k[i][j];
    
            A=(ALGraph*)malloc(sizeof(ALGraph));
            MatToList(M,A)  ;
            DispAdj(A);
        }
    // 输入ok 无显示`
    

    重点

       //邻接矩阵转换成邻接表
        void MatToList(MGraph &M, ALGraph *&A){
            int i,j;
            ArcNode *p;
    
            //给邻接表分配内存
            A = (ALGraph*)malloc(sizeof(ALGraph));
            //遍历头节点 赋初值
            for(i=0;i<M.vertexNum;i++)
                A->adjList[i].firstarc=NULL;
    
            //遍历邻接矩阵中的所有元素
            for(i=0;i<M.vertexNum;i++)
                for(j=0;j<i;j++)
                    if(M.edges[i][j]!=0) {//存在<i,j>边
                        p=(ArcNode*)malloc(sizeof(ArcNode)); //创建一个新的表结点
                        p->adjvex=j;    //弧的终点为j
                        p->nextarc=A->adjList[i].firstarc; //邻接表: 头节点 表结点;
                        // 新的表结点的链域nextarc存放 之前表结点的地址(在头节点的链域里)
                        A->adjList[i].firstarc=p;//将p接在头节点后面
                    }
    
    
    
        }
    

    邻接表—>邻接矩阵

    
    void ListToMat(ALGraph *A,MGraph &M)
    
    {	int i;
    	ArcNode *p;
    	for (i=0;i<A->vertexNum;i++)
    	{	p=A->adjlist[i].firstarc;
    		while (p!=NULL)
    		{	M.edges[i][p->adjvex]=1;
    			p=p->nextarc;
    		}
    	}
    	
    }
    
    
    展开全文
  • 将递增函数的邻接矩阵和非负矩阵分解方法相结合,应用于图像分类。首先由图像中提取的特征点构造递增函数的邻接矩阵,再对其进行非负矩阵分解,用分解后的特征向量作为PNN分类器的输入,实现对图像的分类。算法...
  • LaTeX中画邻接矩阵、邻接表、排列树

    千次阅读 2018-09-12 19:56:28
    最近的算法分析作业总是...给出下图的权矩阵和邻接表 权矩阵: \usepackage{amsmath} \begin{equation*} \begin{matrix} \quad &amp;amp;amp;amp;V_1 &amp;amp;amp;amp;V_2&amp;amp;amp;amp;V...

    最近的算法分析作业总是要编辑公式和画图,word操作的实在是不太友好,于是“杀鸡用牛刀”–便用了LATEX
    题目如下:

    给出下图的权矩阵和邻接表

    这里写图片描述

    • 权矩阵:
    \usepackage{amsmath}
    \begin{equation*}
    \begin{matrix}
    \quad &V_1 &V_2&V_3&V_4&V_5\\
    \end{matrix}
    \end{equation*}
    \begin{equation*}
    \begin{matrix}
     V_1& \\
     V_2& \\
     V_3& \\
     V_4& \\
     V_5&
    \end{matrix}
    \begin{bmatrix}
    \infty&10&\infty&4&\infty\\
    10&\infty&15&8&5\\
    \infty&15&\infty&7&30\\
    4&8&7&\infty&6\\
    12&5&30&6&\infty
    \end{bmatrix}
    \end{equation*}

    这里写图片描述


    • 邻接表

    在这里想啰嗦几句,TikZ包真的是一个很好的神器,在LATEX中使用它可以画出很多超级好看的图哟!
    接下来分享几个学习TikZ的网址:
    官网学习的example
    Data structures in TikZ
    TikZ快速入门文档
    LATEX在线编辑网址
    \usepackage{tikz}
    \usetikzlibrary{calc,matrix,decorations.markings,decorations.pathreplacing}
    \usetikzlibrary{arrows,shapes,chains}
    \begin{tikzpicture}[nodes in empty cells,
          nodes={minimum width=0.7cm, minimum height=0.6cm}]
        \node(0){0};
        \node[draw,rectangle,node distance=0.7cm,right of=0,minimum height=0.8cm](n0){$V_1$} ;
        \node[rectangle,draw,right of=n0,node distance=0.7cm,minimum height=0.8cm](n1){};
        \node[rectangle,draw,right of=n1](n2){1};
        \node[rectangle,draw, right of=n2,node distance=0.7cm](n3){10};
        \node[rectangle,draw,right of=n3,node distance=0.7cm](n4){};
        \node[rectangle,draw, right of=n4](n5){3};
        \node[rectangle,draw, right of=n5,node distance=0.7cm](n6){4};
        \node[rectangle,draw,right of=n6,node distance=0.7cm](n7){};
        \node[rectangle,draw, right of=n7](n8){4};
        \node[rectangle,draw, right of=n8,node distance=0.7cm](n9){12};
        \node[rectangle,draw, right of=n9,node distance=0.7cm](n10){$\wedge$};
        \draw[-latex] (n1.center) -- (n2.west);
        \draw[-latex] (n4.center) -- (n5.west);
        \draw[-latex] (n7.center) -- (n8.west);
    
        \node(1)[node distance=0.8cm,below of=0]{1};
        \node[draw,rectangle,node distance=0.7cm,right of=1,minimum height=0.8cm](n10){$V_2$} ;
        \node[rectangle,draw,right of=n10,node distance=0.7cm,minimum height=0.8cm](n11){};
        \node[rectangle,draw,right of=n11](n12){0};
        \node[rectangle,draw, right of=n12,node distance=0.7cm](n13){10};
        \node[rectangle,draw,right of=n13,node distance=0.7cm](n14){};
        \node[rectangle,draw, right of=n14](n15){2};
        \node[rectangle,draw, right of=n15,node distance=0.7cm](n16){15};
        \node[rectangle,draw,right of=n16,node distance=0.7cm](n17){};
        \node[rectangle,draw, right of=n17](n18){3};
        \node[rectangle,draw, right of=n18,node distance=0.7cm](n19){8};
        \node[rectangle,draw,right of=n19,node distance=0.7cm](n110){};
        \node[rectangle,draw, right of=n110](n111){4};
        \node[rectangle,draw,right of=n111,node distance=0.7cm](n112){5};
        \node[rectangle,draw, right of=n112,node distance=0.7cm](n113){$\wedge$};
        \draw[-latex] (n11.center) -- (n12.west);
        \draw[-latex] (n14.center) -- (n15.west);
        \draw[-latex] (n17.center) -- (n18.west);
        \draw[-latex] (n110.center) -- (n111.west);
    
        \node(2)[node distance=0.8cm,below of=1]{2};
        \node[draw,rectangle,node distance=0.7cm,right of=2,minimum height=0.8cm](n20){$V_3$} ;
        \node[rectangle,draw,right of=n20,node distance=0.7cm,minimum height=0.8cm](n21){};
        \node[rectangle,draw,right of=n21](n22){1};
        \node[rectangle,draw, right of=n22,node distance=0.7cm](n23){15};
        \node[rectangle,draw,right of=n23,node distance=0.7cm](n24){};
        \node[rectangle,draw, right of=n24](n25){3};
        \node[rectangle,draw, right of=n25,node distance=0.7cm](n26){7};
        \node[rectangle,draw,right of=n26,node distance=0.7cm](n27){};
        \node[rectangle,draw, right of=n27](n28){4};
        \node[rectangle,draw, right of=n28,node distance=0.7cm](n29){30};
        \node[rectangle,draw, right of=n29,node distance=0.7cm](n210){$\wedge$};
        \draw[-latex] (n21.center) -- (n22.west);
        \draw[-latex] (n24.center) -- (n25.west);
        \draw[-latex] (n27.center) -- (n28.west);
    
    
        \node(3)[node distance=0.8cm,below of=2]{3};
        \node[draw,rectangle,node distance=0.7cm,right of=3,minimum height=0.8cm](n30){$V_4$} ;
        \node[rectangle,draw,right of=n30,node distance=0.7cm,minimum height=0.8cm](n31){};
        \node[rectangle,draw,right of=n31](n32){0};
        \node[rectangle,draw, right of=n32,node distance=0.7cm](n33){4};
        \node[rectangle,draw,right of=n33,node distance=0.7cm](n34){};
        \node[rectangle,draw, right of=n34](n35){1};
        \node[rectangle,draw, right of=n35,node distance=0.7cm](n36){8};
        \node[rectangle,draw,right of=n36,node distance=0.7cm](n37){};
        \node[rectangle,draw, right of=n37](n38){2};
        \node[rectangle,draw, right of=n38,node distance=0.7cm](n39){7};
        \node[rectangle,draw,right of=n39,node distance=0.7cm](n310){};
        \node[rectangle,draw, right of=n310](n311){4};
        \node[rectangle,draw,right of=n311,node distance=0.7cm](n312){6};
        \node[rectangle,draw, right of=n312,node distance=0.7cm](n313){$\wedge$};
        \draw[-latex] (n31.center) -- (n32.west);
        \draw[-latex] (n34.center) -- (n35.west);
        \draw[-latex] (n37.center) -- (n38.west);
        \draw[-latex] (n310.center) -- (n311.west);
    
    
        \node(4)[node distance=0.8cm,below of=3]{4};
        \node[draw,rectangle,node distance=0.7cm,right of=4,minimum height=0.8cm](n40){$V_5$} ;
        \node[rectangle,draw,right of=n40,node distance=0.7cm,minimum height=0.8cm](n41){};
        \node[rectangle,draw,right of=n41](n42){0};
        \node[rectangle,draw, right of=n42,node distance=0.7cm](n43){12};
        \node[rectangle,draw,right of=n43,node distance=0.7cm](n44){};
        \node[rectangle,draw, right of=n44](n45){1};
        \node[rectangle,draw, right of=n45,node distance=0.7cm](n46){5};
        \node[rectangle,draw,right of=n46,node distance=0.7cm](n47){};
        \node[rectangle,draw, right of=n47](n48){2};
        \node[rectangle,draw, right of=n48,node distance=0.7cm](n49){30};
        \node[rectangle,draw,right of=n49,node distance=0.7cm](n410){};
        \node[rectangle,draw, right of=n410](n411){3};
        \node[rectangle,draw,right of=n411,node distance=0.7cm](n412){6};
        \node[rectangle,draw, right of=n412,node distance=0.7cm](n413){$\wedge$};
        \draw[-latex] (n41.center) -- (n42.west);
        \draw[-latex] (n44.center) -- (n45.west);
        \draw[-latex] (n47.center) -- (n48.west);
        \draw[-latex] (n410.center) -- (n411.west);
    \end{tikzpicture}

    这里写图片描述

    画出n=3的排列树

    \begin{tikzpicture}[level/.style={sibling distance=40mm/#1}]
      \node [circle,draw]{$A$}
      child{node[circle,draw]{$B$}child{node[circle,draw]{$E$}child{node[circle,draw]{$K$}}}child{node[circle,draw]{$F$}child{node[circle,draw]{$L$}}}}
      child{node[circle,draw]{$C$}child{node[circle,draw]{$G$}child{node[circle,draw]{$M$}}}child{node[circle,draw]{$H$}child{node[circle,draw]{$N$}}}}
      child{node[circle,draw]{$D$}child{node[circle,draw]{$I$}child{node[circle,draw]{$J$}}}child{node[circle,draw]{$O$}child{node[circle,draw]{$P$}}}};
    \end{tikzpicture}

    这里写图片描述

    展开全文
  • 编写一个程序algo8-1.cpp,实现不带带权图的邻接矩阵与邻接表的互相 转换算法、输出邻接矩阵与邻接表的算法,并在此基础上设计一个程序exp8-1.cpp 实现如下功能: 1)建立如图有向图G的邻接矩阵,并输出; 2)...
  • 作者:地理小子 ...来源:知乎 著作归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。...我现在有一个区域内的点线的矢量信息,点位于线的交点上,想得到整个图的邻接矩阵。 比如这个图中: 有...
  • 负圈:负圈又称负环,就是说一个全部由负的边组成的环,这样的话不存在最短路,因为每在环中转一圈路径总长就会边小。算法描述: 1.找到最短距离已确定的顶点,从它出发更新相邻顶点的最短距离。 2.以后不需要再...
  • 图存储的两种方式:邻接矩阵和邻接表 邻接矩阵,顾名思义,本身是一个矩阵也就是二维数组,用一个二维数组的索引作为点与点之间的关系,用二维数组实际存储的数据储存是否相通或边。 用邻接矩阵存储时,遍历方式也...
  • 【数据结构】图(邻接矩阵、邻接表)的JAVA代码实现组成常用术语图的分类数据结构(重点)代码 组成 顶点 + 边 (边可以没有但是至少有一个顶点) 图Graph是顶点vertex集合和边(也称之为弧 edge)集合组成。 G=(V...
  • 图的相关概念术语概念无向图有向图度,入度出度子图完全无向图完全有向图稀疏图稠密图简单路径,回路(环)连通,连通图连通分量(无向图)强连通图和强联通分量(有向图)权和网二. 图的存储结构—邻接...
  • 如果G[i] [j]]为0,则说明顶点i顶点j之间不存在边,而这个二维数组G[ ] [ ]则被称为邻接矩阵。另外,如果存在边,则可以令G[ i ] [ j ]存放边,对不存在的边可以设边权为0、-1或是一个很大的数。   图10-4是...
  • 负圈:负圈又称负环,就是说一个全部由负的边组成的环,这样的话不存在最短路,因为每在环中转一圈路径总长就会边小。 算法描述:  1.找到最短距离已确定的顶点,从它出发更新相邻顶点的最短距离。  2.以后...
  • 一、邻接矩阵 用一个二维数组来存储图的信息。 有向图无向图: 对于有向图:a[i][j]!=a[j][i] 对于无向图:a[i][j]==a[j][i] 带权图非带权图: 对于有边的图,若顶点<i,j>之间有边且边权为x,...
  • 1.1.2 邻接矩阵 用于点数不大(不超过1000) 时间复杂度 外层循环O(V)【V就是顶点个数】与内层循环(寻找最小的d[u]需要O(V)、枚举V需要O(V),总时间复杂度为O(V * (V + V)) = O(V 2 ) const int ...
  • 一、邻接矩阵 构造一个二维矩阵M = {mi, j}。 如果图是无权图,那么仅需要表示边的邻接关系。这时每个元素mi, j的取值只能是0或1: 如果图是有权图,那么还需要表示边。权值有时候会取0,所以表示方法改成: 当...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 319
精华内容 127
关键字:

权矩阵和邻接矩阵