无向图的邻接矩阵是对称矩阵 V10 00 00 V310001 000 V50 100 TDv=zA[]行数字的和等于v的度 e=12A全部数字的和等于边数2 Data structure
Data Structure LXJ 无向图的邻接矩阵是对称矩阵 TD(vi )=ΣA[i,j] i行数字的和等于vi的度 j=1 n e=1/2 ΣΣA[i,j] 全部数字的和等于边数*2 i=1 n j=1 n V5 V1 V2 V3 V4 V1 V2 V3 V4 V5 V1 0 1 1 0 0 V2 1 0 0 1 1 V3 1 0 0 0 1 V4 0 1 0 0 0 V5 0 1 1 0 0
有向图的邻接矩阵 A]=1svvP∈E =0vv>不存在 10 000 000 oD(v)=A行数字的和等于v的出度 旧P∑∑A】〗全部数的和等于边数 Data structure
Data Structure LXJ 有向图的邻接矩阵 A[i,j] =1 <vi,vj>E =0 <vi,vj>不存在 OD(vi )=ΣA[i,j] i行数字的和等于vi的出度 j=1 n |E|= ΣΣA[i,j] 全部数字的和等于边数 i=1 n j=1 n V1 V2 V3 V4 V1 V2 V3 V4 V1 0 1 1 0 V2 1 0 0 0 V3 0 0 0 1 V4 1 0 0 0
网的邻接矩阵 打=wn(wv)∈E权为w =∞v,v)不存在 V1 V2 V3 V4 V5 V6 V1∞5∞7∞∞ V2|∞∞4∞∞ V38∞∞∞∞9 V4|∞∞5 V5∞∞∞5∞∞ V63∞∞∞1 Data structure
Data Structure LXJ 网的邻接矩阵 A[i,j] =wi (vi,vj)∈E 权为wi =∞ (vi,vj)不存在 V5 V1 V6 V2 V4 V3 5 4 8 9 5 7 3 1 5 6 V1 V2 V3 V4 V5 V6 V1 ∞ 5 ∞ 7 ∞ ∞ V2 ∞ ∞ 4 ∞ ∞ ∞ V3 8 ∞ ∞ ∞ ∞ 9 V4 ∞ ∞ 5 ∞ ∞ 6 V5 ∞ ∞ ∞ 5 ∞ ∞ V6 3 ∞ ∞ ∞ 1 ∞
22邻接矩阵表示的图类 iNclude"queue.h # include"seq山sth“ const int Max Vertica 10F template <class T> class AdjMWGraph SeqList<T> vertex Liste∥顶点集 int edge[ Maxvertics] Maxvertics]B∥边集 int graphsizey int Findvertex Seq List<T> &Ly const T& vertex int GetvertexPos(const T& vertex Data structure
Data Structure LXJ 8.2.2 邻接矩阵表示的图类－ AdjMWGraph #include "queue.h“ #include "seqlist.h“ const int MaxVertics = 10; template <class T> class AdjMWGraph { SeqList<T> vertexList; //顶点集 int edge [MaxVertics][MaxVertics]; //边集 int graphsize; int FindVertex(SeqList<T> &L, const T& vertex); int GetVertexPos(const T& vertex); …
AdMWGraph class Ad Graph(void)月 int GraphEmpty(void) const; int GraphFull(void) const; int Numberofvertices(void) const; int GetWeight(const T& vertext, const T& vertex; SeqList<T>& GetNeighbors( const T& vertex int GetFirstNeighbor(const int VE int GetNextNeighbor(const int vl, const int V2); Data structure
Data Structure LXJ AdjMWGraph class … AdjMWGraph(void); int GraphEmpty(void) const; int GraphFull(void) const; int NumberOfVertices(void) const; int GetWeight(const T& vertex1, const T& vertex2); SeqList<T>& GetNeighbors(const T& vertex); int GetFirstNeighbor(const int v); int GetNextNeighbor(const int v1, const int v2); …