有向图的邻接表和逆邻接表 data adi dest link 0A 1∧ dest link 1 B 2∧ B 2C∧ 邻接表(出边表) data adi dest link 0A 1∧ 1B 0∧ 2 C 1∧ 逆邻接表(入边表)
有向图的邻接表和逆邻接表 26 data adj A B C 0 1 2 dest link dest link 邻接表 (出边表) data adj A B C 0 1 2 dest link 逆邻接表 (入边表) 1 0 2 0 1 1 A B C
网络(带权图)的邻接表 data adj dest cost link 6 A D0A 15 36∧ 1B 5 28∧ C B C 32∧ 8 3 19∧ 项点表)(出边表) 统计出边表中结点个数,得到该顶点的出度; 统计入边表中结点个数,得到该顶点的入度 27
网络 (带权图) 的邻接表 • 统计出边表中结点个数，得到该顶点的出度； • 统计入边表中结点个数，得到该顶点的入度。 27 B A C D 6 9 5 2 8 data adj A B C D 0 1 2 3 dest cost link 1 5 3 6 2 8 3 2 1 9 (顶点表) (出边表)
用邻接表表示的图的类定义 template <class t, class e> struct edge i 结点的定义 int dests ∥的另一顶点位置 E cost: ∥边上的权值 Edge<t e> link /一条边链指针 Edge ot 构造函数 Edge(int num,Ec 构造函数 dest(num), cost(c), link(null)f bool operator !=(Edge<T, E>& r) const { return dest!= R dest? true: false;}判边等否
用邻接表表示的图的类定义 template <class T, class E> struct Edge { //边结点的定义 int dest; //边的另一顶点位置 E cost; //边上的权值 Edge<T, E> *link; //下一条边链指针 Edge () {} //构造函数 Edge (int num, E c) //构造函数 : dest (num), cost (c), link (NULL) { } bool operator != (Edge<T, E>& R) const { return dest != R.dest ? true:false; } //判边等否 }; 28
template <class t, class E> struct Vertex t /项点的定义 t data //项点的名字 Edge<t, e>*adj; 链表的头指针 template <class T, class e> class graphIng: public graph<T,E>{/图的 类定义 friend istream& operator >>(istream& in GraphInk<t, e>&g /入 friend ostream& operator <<(ostream& out, GraphInk<t, e>&g /出
template <class T, class E> struct Vertex { //顶点的定义 T data; //顶点的名字 Edge<T, E> *adj; //边链表的头指针 }; template <class T, class E> class Graphlnk : public Graph<T, E> { //图的 类定义 friend istream& operator >> (istream& in, Graphlnk<T, E>& G); //输入 friend ostream& operator << (ostream& out, Graphlnk<T, E>& G); //输出 29
private: Vertex<T, e> *Node Table, 1点表(各边链表的头结点) int get Vertex Pos(const T vertex) /给出顶点 vertex在图中的位置 for(int 1=0; 1< num Vertices; 1++) if (Node Table[i]. data==vertex) return 1; return-I public Graphlnk( int sz= Default vertices);/构造函 数 GGraphInko 析构函数
private: Vertex<T, E> *NodeTable; //顶点表 (各边链表的头结点) int getVertexPos (const T vertex) { //给出顶点vertex在图中的位置 for (int i = 0; i < numVertices; i++) if (NodeTable[i].data == vertex) return i; return -1; } public: Graphlnk (int sz = DefaultVertices); //构造函 数 ~Graphlnk(); //析构函数 30