C++算法与数据结构

图是四种逻辑结构中最复杂的结构：

• 集合结构：其中的元素之间没有关系
• 线性结构：严格的一对一关系
• 树状结构：一对多的关系
• 图状结构：多对多关系

在数学中，图可以用 G = ( V , E ) G=(V, E) G=(V,E)来定义，其中， V V V 表示图中的顶点集， E E E 表示图中的边集。

• 有向图：
  • 边有方向，也称为弧
  • 边用 < > <> <>表示，比如， < A , B > 表示从 A A A 出发到 B B B 的一条边

• 无向图：
  • 边无方向
  • 边用圆括号表示， ( A , B ) (A, B) (A,B) 表示顶点 A A A 和 B B B 之间有一条边

• 加权图：
  • 边被赋予一个权值 W W W
  • 如果图是有向的，称为加权有向图，边表示为 < A , B , W >
  • 如果是无向的，称为加权无向图，边表示为 ( A , B , W ) (A, B, W) (A,B,W)

• 基本操作
  • 构造一个由若干个结点、0 条边组成的图
  • 判断两个结点之间是否有边存在
  • 在图中添加或删除一条边
  • 返回图中的结点数或边数
  • 按某种规则遍历图中的所有结点
• 还有一些与应用密切关联的操作
  • 拓扑排序
  • 关键路径
  • 找最小生成树
  • 找最短路径等

template 
class graph {
    public:
        virtual void insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w) = 0;
        virtual void remove(TypeOfVer x, TypeOfVer y) = 0;
        virtual bool exist(TypeOfVer x, TypeOfVer y) const = 0;
        virtual  ~graph() {}
        int numOfVer() const {return Vers;}
        int numOfEdge() const {return Edges;}

    protected:
        int Vers, Edges;
};

图中连接于某一结点的边的总数

• 入度：有向图中进入某一结点的边数
• 出度：有向图中离开某一结点的边数

设有两个图 G = ( V , E ) G = (V, E) G=(V,E)和 G ′ = ( V ’ , E ’ ) G' = (V’, E’) G′=(V’,E’)，如果 V ′ ⊂ V V'subset V V′⊂V, E ′ ⊂ E E'subset E E′⊂E，则称 G ’ G’ G’ 是 G G G的子图

对 1 < i < N 1 ∈ E in E ∈E

• 简单路径：如果一条路径上的所有结点，除了起始结点和终止结点可能相同外，其余的结点都不相同，比如下图中的 BACD、ABA
• 环：环是一条简单路径，其起始结点和终止结点相同，且路径长度至少为 1，比如下图中的 ACDA、ABA

• 非加权的路径长度：组成路径的边数
• 加权路径长度：路径上所有边的权值之和

• 无向图：
  • 连通：顶点 v v v 至 v ’ v’ v’ 之间有路径存在
  • 连通图：任意两点之间都是连通的无向图，比如下面的左图就是一个连通图，右图就不是
  • 连通分量：非连通图中的极大连通子图，比如下面的右图就存在红圈圈住的两个连通分量

• 有向图：
  • 强连通图：顶点 v v v 至 v ’ v’ v’ 之间有路径存在
  • 强连通分量：非强连通图中的极大连通子图，比如下面的左图就是一个强连通图，右图就不是，右图存在红圈圈住的三个强连通分量
  • 弱连通图：如有向图 G 不是强连通的，但如果把它看成是无向图时是连通的，比如下面的右图

• 无向完全图：任意两个结点之间都有边的无向图，比如下面的左图
• 有向完全图：任意两个结点之间都有弧的有向图，比如下面的右图

连通图的极小连通子图，如下图中右侧两图就是左图的生成树

• 包含图的所有 n 个结点和 n-1 条边
• 在生成树中添加一条边之后，必定会形成回路或环

加权无向图的所有生成树中边的权值（代价）之和最小的生成树，如下图中右图就是左图的最小生成树

邻接矩阵的概念和设计

• 有向图
  • V V V 集合存储在一个数组中
  • E E E 集合用 n 行 n 列的布尔矩阵 A A A 表示
    • 如果 i 至 j 有一条有向边， A [ i , j ] = 1 A[i,j] = 1 A[i,j]=1
    • 如果 i 至 j 没有一条有向边， A [ i , j ] = 0 A[i,j] = 0 A[i,j]=0
  • 特点：
    • 第i个结点的出度：i 行之和
    • 第j个结点的入度：j 列之和

• 无向图
  • V V V 集合存储在一个数组中
  • E E E 集合用 n 行 n 列的布尔矩阵 A A A 表示
    • 如果 i 至 j 有一条边， A [ i , j ] = A [ j , i ] = 1 A[i,j] = A[j,i] = 1 A[i,j]=A[j,i]=1
    • 如果 i 至 j 没有边， A [ i , j ] = A [ j , i ] = 0 A[i,j] = A[j,i] = 0 A[i,j]=A[j,i]=0
• 特点：
• 是一个对称矩阵
• 结点 i 的度是 i 行或 i 列之和

• 加权图
  • 如果 i 至 jj 有一条边且它的权值为 a，则 A [ i , j ] = a A[i,j] = a A[i,j]=a
  • 如果 i 至 j 没有一条有向边，则 A [ i , j ] = 空 或 其 它 标 志 A[i,j] = 空或其它标志 A[i,j]=空或其它标志

• 性能分析
  • 优点：基本操作都是 O ( 1 ) O(1) O(1)的时间复杂度，不仅能找到出发的边，也能找到到达的边
  • 缺点：即使 < < n 2 << n^2 <

template 
class adjMatrixGraph::public graph {
public:
    adjMatrixGraph(int vSize, const TypeOfVer d[], const TypeOfEdge noEdgeFlag);
    void insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w);
    void remove(TypeOfVer x, TypeOfVer y);
    bool exist(TypeOfVer x, TypeOfVer y) const;
    ~adjMatrixGraph() ；
 
private:
    TypeOfEdge **edge;                   //存放邻接矩阵
    TypeOfVer *ver;                      //存放结点值
    TypeOfEdge noEdge;                   //邻接矩阵中的∞的表示值
    int find(TypeOfVer v) const {
        for (int i = 0; i < Vers; ++i)
            if (ver[i] == v) return i;
    }
};

• 构造函数

template 
adjMatrixGraph::adjMatrixGraph (int vSize, const TypeOfVer d[], TypeOfEdge noEdgeFlag) {
    int i, j;
    // 结点数和边数存储到父类的成员变量中
    Vers = vSize;   
    Edges = 0;  
    noEdge = noEdgeFlag;

    ver = new TypeOfVer[vSize];
    for (i=0; i 
析构函数
 
template 
adjMatrixGraph::~adjMatrixGraph() {
    delete [] ver;
    for (int i=0; i 
insert函数
 
template 
void adjMatrixGraph ::insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w) { 
    int u = find(x), v = find(y); 
    edge[u][v] = w;
    ++Edges;
}
 
remove函数
 
template 
void adjMatrixGraph::remove(TypeOfVer x, TypeOfVer y) { 
    int u = find(x),  v = find(y); 
    edge[u][v] = noEdge;
    --Edges;
}
 
邻接表 
邻接表的概念和设计 
 
邻接表是图的标准存储方式
 
  
 

        
         
          
           
            V
           
          
          
           V
          
         
        V 集合
 
    
用数组或单链表的形式存放所有的结点值
如果结点数 n 固定，则采用数组形式，否则可采用单链表的形式
 
 

        
         
          
           
            E
           
          
          
           E
          
         
        E 集合
 
    
同一个结点出发的所有边组成一个单链表 
      
注意：如果是加权图，单链表的每个结点中还要保存权值
 
 
 
 
 
性能分析
 
  
优点： 
    

         
          
           
            
             内
            
            
             存
            
            
             ＝
            
            
             结
            
            
             点
            
            
             数
            
            
             ＋
            
            
             边
            
            
             数
            
           
           
            内存 ＝ 结点数 ＋ 边数
           
          
         内存＝结点数＋边数
处理时间：结点数 ＋ 边数，即为 
         
          
           
            
             O
            
            
             (
            
            
             ∣
            
            
             V
            
            
             ∣
            
            
             +
            
            
             ∣
            
            
             E
            
            
             ∣
            
            
             )
            
           
           
            O(|V|+|E|)
           
          
         O(∣V∣+∣E∣)
 
缺点： 
    
确定 
         
          
           
            
             i
            
            
             −
            
            
             >
            
            
             j
            
           
           
            i->j
           
          
         i−>j 是否有边，最坏需耗费 
         
          
           
            
             O
            
            
             (
            
            
             n
            
            
             )
            
           
           
            O(n)
           
          
         O(n) 时间
无向图同一条边表示两次，边表空间浪费一倍
有向图中寻找进入某结点的边，非常困难
 
 
 
邻接表类定义 
template 
class adjListGraph::public graph {
public:      
    adjListGraph(int vSize, const TypeOfVer d[]);
    void insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w);
    void remove(TypeOfVer x, TypeOfVer y);
    bool exist(TypeOfVer x, TypeOfVer y) const;
    ~adjListGraph();
    
private:    
    struct edgeNode {                   
        int end;                          
        TypeOfEdge weight;                
        edgeNode *next;
        edgeNode(int e, TypeOfEdge w, edgeNode *n = NULL) { end = e; weight = w; next = n;}
    };

    struct verNode{                     
        TypeOfVer ver;                   
        edgeNode *head;                 
        verNode( edgeNode *h = NULL) { head = h;}
    };

    verNode *verList;
    int find(TypeOfVer v) const { 
        for (int i = 0; i < Vers; ++i)
            if (verList[i].ver == v) return i; 
    } 
};
 
邻接表成员函数实现 
构造函数：假设所有单链表用的都是不带头结点的单链表，那我们需要构造一个数组存放顶点，每个顶点中的edgeNode都是空的
 
template 
adjListGraph ::adjListGraph(int vSize, const TypeOfVer d[]) {
    Vers = vSize; 
    Edges = 0;
 
    verList = new verNode[vSize];
    for (int i = 0; i < Vers; ++i) 
		verList[i].ver = d[i];
}
 
析构函数
 
template 
adjListGraph::~adjListGraph() { 
	int i;
    edgeNode *p;
    
    for (i = 0; i < Vers; ++i) 
		while ((p = verList[i].head) != NULL) ｛
			verList[i].head = p->next;
	    	delete p;
		}

	delete [] verList;
} 
 
insert函数
 
template 
void adjListGraph:: insert(TypeOfVer x, TypeOfVer y, TypeOfEdge w) {
	int u = find(x),  v = find(y);
	verList[u].head = new edgeNode(v, w, verList[u].head);
    ++Edges;
}
 
remove函数
 
template 
void adjListGraph::remove(TypeOfVer x,TypeOfVer y) {  
	int u = find(x), v = find(y);
	edgeNode *p = verList[u].head, *q; 

	if (p == NULL) return;  
	if (p->end == v) {       
		verList[u].head = p->next; 
		delete p;
		--Edges;
		return;
	} 
	while (p->next !=NULL && p->next->end != v) p = p->next;        
	if (p->next != NULL) {               
		q = p->next;        
		p->next = q->next;         
		delete q;       
		--Edges;  
	}
}
 
exist函数
 
template 
bool adjListGraph::exist(TypeOfVer x, TypeOfVer y) const {
	int u = find(x),  v = find(y);
    edgeNode *p = verList[u].head;
 
    while (p !=NULL && p->end != v) 
    	p = p->next;
	if (p == NULL) 
    	return false; 
	else return true;
}
 
逆邻接表 
将进入同一结点的边组织成一个单链表。
 
 
十字链表 
每个结点维护两条链，既记录前驱又记录后继，而且每条边只存储一次。
 
 
邻接多重表 
解决无向图中边存储两次的问题。
 
每个边的链表结点中存储与这条边相关的两个顶点，以及分别依附于这两个顶点下一条的边。
 
 
练习 
连通路径
 
已知一张图有n (2 <= n <= 1000)个点，m (1 <= m <= 10^6)条边，点的编号为1 ~ n，现在给出每条边连接的两侧端点，请你列出每个点都与哪些点有直接连通的边。
 
输入描述：
 
第一行两个整数n m，分别表示这张图点和边的数量。
 
接下来m行，每行两个整数，表示这条边所连接的两个端点。
 
输出描述：
 
共n行，每行若干个整数，第i行表示与点i相直接连接的点。若有多个，则由小到大输出，不包含点i自己；若没有点与其直接相连，则在改行输出none。
 
示例 1：
 
输入：
5 5
1 2
2 3
1 3
2 1
1 4
输出：
2 3 4
1 3
1 2
1
none
 
代码：
 
#include 

#define N 1010

using namespace std; 

bool nxt[N][N];

int main() {
    int n, m, a, b;
    cin >> n >> m;
    while (m--) {
        cin >> a >> b;
        nxt[a][b] = true;
        nxt[b][a] = true;
    }
    for (int i = 1; i <= n; i++) {
        bool f = false;
        for (int j = 1; j <= n; j++)
            if (nxt[i][j] == true && i != j) {
                cout << j << " ";
                f = true;
            }
        if (f == false)
            cout << "none";
        cout << endl;
    }
    return 0;
}