精华内容
下载资源
问答
  • 基于C++的带权重的无向图的实现(邻接表法)

    该系列文章是本人整理的有关带权无向图的数据结构和算法的分析与实现,若要查看源码可以访问我的github仓库,如有问题或者建议欢迎各位指出。

    目录

    基于C++的带权无向图的实现 (一)- 数据结构
    基于C++的带权无向图的实现 (二)- 遍历算法
    基于C++的带权无向图的实现 (三)- Prim最小生成树算法
    基于C++的带权无向图的实现 (四)- Dijkstra最短路径算法
    基于C++的带权无向图的实现 (五)- 连通图和连通分量
    基于C++的带权无向图的实现 (六)- 关节点算法

    图的基本概念

    1. 图的表达形式:Graph = (V,E)
      在这里插入图片描述
      其中V代表顶点(Vertex)的集合,E代表边(Edge)的集合,每一组边用括号表示,比如(A,B)代表顶点A,B之间的边。

    1. 图可以分为有向图和无向图,例如:
      在这里插入图片描述

    2. 我们可以用邻接矩阵或者邻接表,来实现“图”这种数据结构,比如,对于下图:
      在这里插入图片描述

    邻接矩阵和邻接表的表示如下:
    在这里插入图片描述

    • 邻接矩阵中,横轴和纵轴表示的数字分别为顶点,矩阵中的“0”和“1”表示两个顶点间是否有相邻关系。邻接矩阵中主对角线都是0因为顶点不可能与本身具有相邻关系。要知道某个顶点的度数,只需要求该顶点所在的行或者列的和即可。

    • 邻接表是一种数组与链表(或集合)结合的存储方法,其中数组用来存放所有顶点,链表(或集合)用来存在该顶点的所有邻接顶点。


    1. 如果顶点之间的边加上权重,则可以表示如下:

    在这里插入图片描述


    本文所实现的就是这种带权重的无向图,测试案例用的就是该图顶点和边的数据,最终存储在如下所示的邻接表中:

    在这里插入图片描述

    定义类

    图类(class Graph)

    由于C++中存在很多高效的STL容器,这里使用了map和set两种关联式容器来存储顶点和边的数据。

    1. map:存储键值对(key-value)的容器,提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可以称为该关键字所对应的值)的数据处理能力。这里我把顶点设置为键,其对应的邻接点和边的权重的集合设置为值。

    2. set:不会有相同元素,并且存进去的元素会自动进行升序排序(默认情况下),set就是每一个顶点的邻接表。

    来存储每一个顶点及其邻接点和权重集合,设置了模板"T"后图就可以存储任何数据类型的数据。

    template <typename T>
    class Graph {
    public:
    	map<T, set<Edge<T>>> adj;
    };
    

    边类(class Edge)

    类中有两个成员变量,其中vertex表示相邻顶点,weight表示权重。

    template <typename T>
    class Edge {
    public:
    	T vertex;
    	int weight;
    };
    

    功能描述


    在Graph类中实现了以下功能,T为提前定义好的模板:


    函数名 用途
    bool contains(const T& u) 判断图内是否存在顶点u
    bool adjacent(const T& u, const T& v) 判断顶点u和v是否相邻
    void add_vertex(const T& u) 在图中添加顶点u
    void add_edge(const T& u, const T& v, int weight ) 给顶点u和v添加边
    void change_weight(const T& u, const T& v, int weight) 改变顶点u和v之间边的权重值
    void remove_weight(const T& u, const T& v) 删除顶点u和v之间边的权重值
    void remove_vertex(const T& u) 删除给定的顶点u, 同时清除所有入射边
    void remove_edge(const T& u, const T& v) 删除两个顶点之间的边
    int degree(const T& u) 返回顶点的入射边数
    int num_vertices() 返回图中的顶点总数
    int num_edges() 返回图中的边的总数
    int largest_degree() 返回最大顶点的度数。
    int get_weight(const T& u, const T& v) 返回顶点u和v之间边的权重值
    vector get_vertices() 返回图形中所有顶点ID的vector向量
    vector get_neighbours(const T& u) 返回给定顶点的所有相邻顶点ID的vector向量。

    void show()| 打印图中所有数据


    代码实现

    1. 在“edge.hpp”中的代码如下:
    template <typename T>
    class Edge {
    public:
    	T vertex;
    	int weight;
    
    	Edge(T neighbour_vertex) {
    		this->vertex = neighbour_vertex;
    		this->weight = 0;
    	}
    
    	Edge(T neighbour_vertex, int weight) {
    		this->vertex = neighbour_vertex;
    		this->weight = weight;
    	}
    
    	bool operator<(const Edge& obj) const {
    		return obj.vertex > vertex;
    	}
    
    	bool operator==(const Edge& obj) const {
    		return obj.vertex == vertex;
    	}
    };
    

    重载了"<“和”=="运算符,这样Edge的对象就可以在集合中进行排序和查找。


    1. 在“graph.hpp”中的代码如下:
    #include<iostream>
    #include<string>
    #include<vector>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include "edge.hpp"
    using namespace std; 
    
    template <typename T>
    class Graph {
    public:
    	map<T, set<Edge<T>>> adj;  /* 邻接表 */
    
    	bool contains(const T& u); /* 判断顶点u是否在图中 */
    	bool adjacent(const T& u, const T& v); /* 判断顶点u和v是否相邻 */
    
    	void add_vertex(const T& u); /* 添加顶点 */
    	void add_edge(const T& u, const T& v, int weight); /* 添加边和权重 */
    
    	void change_weight(const T& u, const T& v, int weight); /* 修改权重 */
    
    	void remove_weight(const T& u, const T& v); /* 移除权重 */
    	void remove_vertex(const T& u); /* 移除顶点 */
    	void remove_edge(const T& u, const T& v); /* 移除边 */
    
    	int degree(const T& u); /* 求顶点的度数 */
    	int num_vertices(); /* 求图中顶点的总数 */
    	int num_edges(); /* 求图中边的总数*/
    	int largest_degree(); /* 求图中的最大度数 */
    
    	int get_weight(const T& u, const T& v); /* 得到某两个顶点之间边的权重 */
    	vector<T> get_vertices(); /* 得到图中所有顶点 */
    	map<T, int> get_neighbours(const T& u); /* 得到顶点u的所有边 */
    
    	void show();
    };
    
    template <typename T> void Graph<T>::show() {
    	for (const auto& u : adj) {
    		cout <<"顶点"<< u.first << ": ";
    		for (const auto& v : adj[u.first])
    			cout << "(相邻顶点: " << v.vertex << ", 边的权重: " << v.weight << ") ";
    		cout <<endl;
    	}
    }
    
    template <typename T> bool Graph<T>::contains(const T& u) {
    	return adj.find(u) != adj.end();
    }
    
    template <typename T> bool Graph<T>::adjacent(const T& u, const T& v) {
    	if (contains(u) && contains(v) && u != v) {
    		for (auto edge : adj[u])
    			if (edge.vertex == v)
    				return true;
    	}
    	return false;
    }
    
    template <typename T> void Graph<T>::add_vertex(const T& u) {
    	if (!contains(u)) {
    		set<Edge<T>> edge_list;
    		adj[u] = edge_list;
    	}
    }
    
    template <typename T> void Graph<T>::add_edge(const T& u, const T& v, int weight) {
    	if (!adjacent(u, v)) {
    		adj[u].insert(Edge<T>(v, weight));
    		adj[v].insert(Edge<T>(u, weight));
    	}
    }
    
    template <typename T> void Graph<T>::change_weight(const T& u, const T& v, int weight) {
    	if (contains(u) && contains(v)) {
    		if (adj[u].find(Edge<T>(v)) != adj[u].end()) {
    			adj[u].erase(Edge<T>(v));
    			adj[u].insert(Edge<T>(v, weight));
    		}
    
    		if (adj[v].find(Edge<T>(u)) != adj[v].end()) {
    			adj[v].erase(Edge<T>(u));
    			adj[v].insert(Edge<T>(u, weight));
    		}
    	}
    }
    
    template <typename T> void Graph<T>::remove_weight(const T& u, const T& v) {
    	if (contains(u) && contains(v)) {
    		if (adj[u].find(Edge<T>(v)) != adj[u].end()) {
    			adj[u].erase(Edge<T>(v));
    			adj[u].insert(Edge<T>(v, 0));
    		}
    
    		if (adj[v].find(Edge<T>(u)) != adj[v].end()) {
    			adj[v].erase(Edge<T>(u));
    			adj[v].insert(Edge<T>(u, 0));
    		}
    	}
    }
    
    template <typename T> void Graph<T>::remove_vertex(const T& u) {
    	if (contains(u)) {
    		for (auto& vertex : adj) {
    			if (vertex.second.find(Edge<T>(u)) != vertex.second.end())
    				vertex.second.erase(Edge<T>(u));
    		}
    		adj.erase(u);
    	}
    }
    
    template <typename T> void Graph<T>::remove_edge(const T& u, const T& v) {
    	if (u == v || !contains(u) || !contains(v)) return;
    
    	if (adj[u].find(Edge<T>(v)) != adj[u].end()) {
    		adj[u].erase(Edge<T>(v));
    		adj[v].erase(Edge<T>(u));
    	}
    }
    
    
    template <typename T> int Graph<T>::degree(const T& u) {
    	if (contains(u)) return adj[u].size();
    
    	return -1; // 度数为-1说明图中没有该顶点
    }
    
    template <typename T> int Graph<T>::num_vertices() {
    	return adj.size();
    }
    
    template <typename T> int Graph<T>::num_edges() {
    	int count = 0;
    	set<Edge<T>> vertex_set;
    
    	for (auto vertex : adj) {
    		vertex_set.insert(Edge<T>(vertex.first, 0));
    		for (auto edge : vertex.second) {
    			if (vertex_set.find(edge) != vertex_set.end()) continue;
    			count++;
    		}
    	}
    	return count;
    }
    
    template <typename T> int Graph<T>::largest_degree() {
    	if (num_vertices() == 0) return 0;
    
    	unsigned max_degree = 0;
    	for (auto vertex : adj) {
    		if (vertex.second.size() > max_degree)
    			max_degree = vertex.second.size();
    	}
    	return max_degree;
    }
    
    template <typename T> int  Graph<T>::get_weight(const T& u, const T& v) {
    	if (contains(u) && contains(v)) {
    		for (Edge<T> edge : adj[u])
    			if (edge.vertex == v) return edge.weight;
    	}
    	return -1;  
    }
    
    template <typename T> vector<T> Graph<T>::get_vertices() {
    	vector<T> vertices;
    	for (auto vertex : adj)
    		vertices.push_back(vertex.first);
    
    	return vertices;
    }
    
    template <typename T> map<T, int> Graph<T>::get_neighbours(const T& u) {
    	map<T, int> neighbours;
    
    	if (contains(u)) {
    		for (Edge<T> edge : adj[u])
    			neighbours[edge.vertex] = edge.weight;
    	}
    
    	return neighbours;
    }
    

    测试

    在“graph_testing.cpp”中的代码如下:

    #include "graph.hpp"
    
    void test01(Graph<char> g)
    {
        cout << "'A' 和 'D'之间边的权重为:" << g.get_weight('A', 'D') << endl;
        g.change_weight('A', 'D', 100);
        cout << "将'A' 和 'D'之间边的权重更改为100后,其权重为:" << g.get_weight('A', 'D') << endl;
        g.remove_weight('A', 'D');
        cout << "将'A' 和 'D'之间边的权重删除后,其权重为:" << g.get_weight('A', 'D') << endl;
        cout << "将'A' 和 'D'之间边的权重重新设置为5" << endl;
        g.change_weight('A', 'D', 5);
    
        cout << "顶点总数:" << g.num_vertices() << endl;
        cout << "边的总数:" << g.num_edges() << endl;
    
        cout << "图中包含'F'吗?" << (g.contains('F') ? "包含" : "不包含") << endl;
        cout << "图中包含'G'吗?" << (g.contains('G') ? "包含" : "不包含") << endl;
        cout << "'A'和'D'相邻吗?" << (g.adjacent('A', 'D') ? "相邻" : "不相邻") << endl;
        cout << "'B'和'E'相邻吗?" << (g.adjacent('B', 'E') ? "相邻" : "不相邻") << endl;
        cout << "顶点'A'的度数为: " << g.degree('A') << endl;
        cout << "最大度数为:" << g.largest_degree() << endl;
    
        auto vertices = g.get_vertices();
        cout << "图中的顶点分别为:";
        for (auto u : vertices) cout << " " << u;
        cout << endl;
    
        map<char, int> nbrs = g.get_neighbours('F');
        cout << "顶点F的邻接顶点ID及其权重为:";
        for (auto u : nbrs) cout << " (" << u.first << ": " << u.second <<")";
        cout << endl;
    }
    
    int main()
    {
        Graph<char> g;
        g.add_vertex('A');
        g.add_vertex('B');
        g.add_vertex('C');
        g.add_vertex('D');
        g.add_vertex('E');
        g.add_vertex('F');
        g.add_vertex('G');
    
        g.add_edge('A', 'B', 7);
        g.add_edge('A', 'D', 5);
        g.add_edge('B', 'C', 8);
        g.add_edge('B', 'D', 9);
        g.add_edge('B', 'E', 7);
        g.add_edge('C', 'E', 5);
        g.add_edge('D', 'E', 15);
        g.add_edge('D', 'F', 6);
        g.add_edge('E', 'F', 8);
        g.add_edge('E', 'G', 9);
        g.add_edge('F', 'G', 11);
    
        g.add_vertex('H');
        g.add_edge('B', 'H', 9);
        g.add_edge('A', 'H', 10);
        g.add_edge('D', 'H', 11);
        g.add_edge('A', 'H', 12);
        g.remove_vertex('H');
        cout << "打印图中顶点及其邻接表的详细信息如下" << endl;
        g.show();
        cout << endl;
        
        test01(g);
        return 0;
    }
    

    输出结果:

    在这里插入图片描述

    再来跟刚刚的两张概念图直观对比一下,发现完全一致:
    在这里插入图片描述

    在这里插入图片描述

    最后,给大家推荐一个可交互的在线绘图的网站Graph Editor,在已知顶点和边的数据后可以在这里左边Node Count栏输入数据进行可视化:
    在这里插入图片描述

    展开全文
  • 情景:在一个图中,已知经过的一串n节点信息,希望显示经过的路径。 数据组织:  点要素:存放图中的点信息,必含Id字段...数据结构图的邻接表存储结构AdjacencyList<T> 1 public class AdjacencyList...

    情景:在一个图中,已知经过的一串n节点信息,希望显示经过的路径。

    数据组织:

      点要素:存放图中的点信息,必含Id字段

      线要素:存放编辑好的路径信息,必含“Start”和“end”字段,存放无向图的起始终止节点Id,隐含线的FID

    实现语言:C#

    数据结构:图的邻接表存储结构AdjacencyList<T>

    1 public class AdjacencyList<T> //图的邻接表存储结构    
    2 public class Node<T> //表示链表中的表结点
    3 public class Vertex<T>//表示存放于数组中的表头结点

    这里在Node<T>类中增加了ArcId字段,用来存储线的FID。

    首先读取点和线要素,初始化邻接表,初始化走过的节点数组。

    View Code
     1  public IPolyline FindPolyLine(string _start, string _end)
     2         {
     3             Node<string> TargetNode=null;
     4             string strTargetLineId=string.Empty;
     5             Vertex<string> head= pathDisplay.Find(_start);
     6             if (head.firstEdge != null)
     7             {
     8                 
     9                 Node<string> tmp = head.firstEdge;
    10                 while (tmp != null)
    11                 {
    12                     if (_end==tmp.adjvex.data.ToString())
    13                     {
    14                         TargetNode=tmp;
    15                     }
    16                     
    17                     tmp = tmp.next;
    18                 }
    19                 strTargetLineId=TargetNode.arcId;
    20             }
    21             IPolyline poline = dic_Id_Polyline[strTargetLineId];
    22             return poline;
    23         }
    24         Dictionary<string, IPoint> dic_Id_Pt = new Dictionary<string, IPoint>();
    25         Dictionary<string, IPolyline> dic_Id_Polyline = new Dictionary<string, IPolyline>();
    26         AdjacencyList<string> pathDisplay = new AdjacencyList<string>();

    为了实现轨迹的动画显示,应用了Threading空间中的Timer,用委托实现在AxMapControl中的动画显示。

    参考文献:

    http://www.cnblogs.com/abatei/archive/2008/06/06/1215114.html

    转载于:https://www.cnblogs.com/yhlx125/archive/2012/12/26/2834155.html

    展开全文
  • 本文简单介绍了图的几种类型以及图的数据结构,并利用C++构建工程实现了有向图和无向图 图的基本定义 图是一种多对多的数据结构,由顶点和边构成 带/无权图:如果图的边的长度不完全相同,则图为带权图。有/无向图...

    数据结构图-邻接表的介绍

    本文简单介绍了图的几种类型以及图的数据结构,并利用C++构建工程实现了有向图和无向图

    图的基本定义

    图是一种多对多的数据结构,由顶点和边构成

    1. 带/无权图:如果图的边的长度不完全相同,则图为带权图。有/无向图:如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,与一个节点相关联的边有出边和入边之分,而与一个有向边关联的两个点也有始点和终点之分。相反,边没有方向的图称为无向图。
      该图为一个无向带权图
    2. 有/无向图:如果给图的每条边规定一个方向,那么得到的图称 为有向图。在有向图中,与一个节点相关联的边有出边和入边之分,而与一个有向边关联的两个点也有始点和终点之分。相反,边没有方向的图称为无向图。
      该图为一个有向图

    邻接表

    1.简单介绍

    数组+链表实现:利用数组存储下标,利用链表实现顶点之间的联系,数据域存储其所有相邻顶点的下标和边权,指针域指向下一个相邻顶点。

    2.无向图的邻接表

    举例:一个无向带权图
    图的顶点数为n

    • 无向图的邻接表
      • 利用一个一维数组V[n-1]存储顶点下标
      • 利用链表实现存在边的顶点之间的联系
        • 若两顶点之间存在边,则用链表联系起来在这里插入图片描述
          该图可以得到如下的邻接表,v1->v2为2,因此v1指针域指向v2,顶点v2在数组中下标为1,v1与v2的权值为2;同理v2指针域指向v1,v1下标为0,v1与v2边长为2。其余顶点同理
          在这里插入图片描述
    展开全文
  • 20171124  图的概念:    图的基本性质:  无向图:  有向图:  连通图:  图的权:有些图的边或者狐剧有与他相关的数字,这种与图的边或者狐相关的数叫做权。... 无向图的邻接表:  有向

    20171124

      图的概念:

      

      图的基本性质:

      

      无向图:

      

      有向图:

       

      连通图:

      

      图的权:有些图的边或者狐剧有与他相关的数字,这种与图的边或者狐相关的数叫做权。

      图的度:无向图顶点的边数叫度,有向图顶点的边数叫出度和入度 。


      图的数据存储结构-邻接矩阵:

      

      

       



      带权邻接矩阵表示法:

      

      图的存储结构-邻接表

      

      无向图的邻接表:

      

      有向图的邻接表:

      

      逆邻接表:

      

      带权邻接表:

      

      


    展开全文
  • 图的存储结构相比线性表与树...(PS:感谢Covit大佬提供的皂片)上面的图片演示的是关于带权图,所以里面存储的是权值,如果是无向图的话,一般用1表示有边,0表示无边。从图的邻接矩阵存储方法(或称数组存储法)容翻译
  • 01知识框架02图结构的存储1邻接矩阵法有向图、无向图和网对应的邻接矩阵如下图所示:邻接矩阵存储结构的定义如下:#define MaxVertexNum 100 //顶点数目的最大值typedef char VertexType; //顶点的数据类型typedef ...
  • 数据结构–图(深度优先遍历和广度优先遍历)(Java) 博客说明 文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请...无向图 有向图 带权图的表示方式 图的表...
  • AOE-网时一个带权的向无,其中顶点表示事件,弧表示活动,权表示活动时间。通常,AOE-网可用来估算工程完成时间。 如:一个AOE-网 由于在AOE-网中只有一个开始点和一个完成点,故在正常情况下(...
  •  给定一个带权无向图,求节点1到节点n最短路径。   输入  输入包含多组数据,格式如下。 第一行包括两个整数n m,代表节点个数和边个数。(n 剩下m行每行3个正整数a b c,代表节点a和节点b之间有...
  • 来看一个一般的无向图:通俗地讲,一张图是由边、顶点集构成,每条边上可能还会有相应的边权(带权的),这里讲带权的。 然后想我们怎样存储它呢,下面介绍几种存储方式。 1、邻接矩阵 图的邻接矩阵...
  • 图的存储结构相邻矩阵有向图的相邻矩阵无向图的相邻矩阵邻接表无向图的邻接表表示带权图的邻接表表示有向图的邻接表(出边表)有向图的逆邻接表(入边表)十字链表3. 图的遍历深度优先遍历(depth-first search)...
  • @[TOC]图算法1、图的表示1.1...C++实现如下:#include1.2、 邻接表1、邻接表的提出 2、无向图的邻接表 3、有向图的邻接表(分出边表、入边表) 4、带权图的处理 有了上面的邻接表的理解,我们可以实现代码(java):...
  • 数据结构-课件.ppt

    2020-11-18 12:44:13
    数据结构课程的内容 第9章 图 9.1 图的基本概念 例判断下列4种图形各属什么类型 证明 稀疏图 稠密图 带权图 ... 邻接表链式表示法 例1无向图的邻接表如何表示 例3已知某网的邻接出边表请画出该网络 邻接表存储法的特点
  • 数据结构图的存储

    2017-04-20 15:09:30
    关于图这种数据结构的概念,请参考相关的教材 在存储图的过程中,我们需要关注三个要素,...(2)、无向图的邻接矩阵是一个对阵矩阵,因此在存储是可以采用稀疏矩阵的存储方法 (3)、对于无向图,邻接矩阵的第i行
  • 设计并验证如下算法:带权图采用邻接表表示,实现无向图的广度优先搜索与有向图的深度优先搜索。 #define MAX_VERTEX_NUM 20 //图的邻接表存储表示 typedef struct ArcNode{ int adjvex; //该弧所指向的顶点的位置...
  • 数据结构学习笔记11——图1.1图的定义1.2图的逻辑结构应用1.3无向图与有向图1.3.1无向图1.3.2有向图1.4简单图与多重图1.4.1简单图1.4.2多重图1.5度1.5.1无向图的度1.5.2有向图的度1.6 顶点之间的关系1.7连通图与强...
  • 有向图、无向图带权图的存储 邻接矩阵 优点:简单、直观;方便矩阵运算,查询效率高 缺点:浪费存储空间,尤其是稀疏图(顶点很多,但是每个顶点的边不多) 领接 每个顶点都对应一个链表 有时为了...
  • 举例图的常用概念无向图有向图带权图图的表示方式邻接矩阵邻接表图的入门案例代码实现结果图的遍历深度优先遍历(Depth First Search)具体步骤广度优先遍历 介绍 为什么要有图?     前面我们学...
  • 设图结点的元素类型为char,建立一个不少于8个顶点的带权无向图G,实现以下图的各种基本操作的程序: ① 用邻接矩阵作为储结构存储图G并输出该邻接矩阵; ② 用邻接链表作为储结构存储图G并输出该邻接链表; ③ 按...
  • 无向图:没有方向图,两顶点之间拥有边及两顶点相互关联 有向图:有方向图,A指向B顶点,只能表示A向B建立了关系 入度:有向图中,被建立关系条数 出度:有向图中,与其他顶点建立条数 带权图:一个...
  • 无向图、有向图对应的邻接矩阵: 网对应的邻接矩阵: 所谓的网就是带权图。 邻接矩阵法的一些要点 6.2.2 邻接表法 顺序+链式存储。对图G的每个顶点建立一个单链表。与树中的孩子表示法相同。 邻接表...
  • 数据结构简记_

    2021-02-17 11:13:38
    图一、图(Graph)的定义二、图的存储结构1. 邻接数组2. 邻接表 一、图(Graph)的定义 ...//图的4种类型:有向图,有向带权图,无向图,无向带权图 typedef struct { VexType *vexs;//顶点数组,V
  • 4,图可以分为有向图和无向图两种,有向图的边有方向。 5,在有向图中,度可以分为入度和出度(Out-degree) 6,带权图:在带权图中,每条边都有一个权重 二:邻接矩阵存储方法 1,图最直观的一种存储方法是:邻接...
  • 图的存储结构 1邻接矩阵表示法 存储方式是用两个数组来表示图,一个一维数组表示图中顶点的信息...在无向图的邻接矩阵中的第i 行或者第i 列的非零元素的个数,为第i个顶点的度; 在有向图中邻接矩阵中的第i行的非00
  • 无向图:顶点之间的连接没有方向 有向图:顶点之间的连接有方向 带权图:边带有权值,也叫网 图的表示方法 二维数组表示(邻接矩阵);链表表示(邻接表) 邻接矩阵:表示图形中顶点之间相邻关系的矩阵,对于n个...
  • 数据结构---->图的存储结构

    千次阅读 2012-12-27 20:12:39
    树的存储结构 2.1邻接矩阵(数组)表示法 图没有顺序映像的存储...分析1:无向图的邻接矩阵是对称的; 分析2:顶点i 的度=第i 行 (列) 中1 的个数; 特别:完全图的邻接矩阵中,对角元素为0,其余全1。 有向带权
  • 给定一个带权无向图,求节点1到节点n最短路径。 Input 输入包含多组数据,格式如下。 第一行包括两个整数n m,代表节点个数和边个数。(n<=100) 剩下m行每行3个正整数a b c,代表节点a和节点b之间有一条边...

空空如也

空空如也

1 2 3 4
收藏数 73
精华内容 29
关键字:

数据结构带权无向图的邻接表

数据结构 订阅