图的基本算法

ゞ浴缸里的玫瑰 2022-09-21 13:22 92阅读 0赞

\#图的广度优先搜索  
\#\#邻接表方式表示图的广度优先搜索  
构造和初始化图使用[图的表示法][Link 1]章节中**邻接表方法表示图**的代码

// 创建简单循环队列
    // Queue.h
    
    ifndef QUEUE_H
    #define QUEUE_H
    
    #define QUEUE_SIZE 5
    int Queue[QUEUE_SIZE] = {0};
    int start = 0;
    int qSize = 0;
    
    void EnQueue(int vertex) {
            if (qSize == QUEUE_SIZE) {
                    puts("Queue is full");
                    return;
            }
            int index = (start+qSize)%QUEUE_SIZE;
            Queue[index] = vertex;
            qSize++;
    }
    
    int DeQueue() {
            if (qSize == 0) {
                    puts("Queue is empty");
                    return -1;
            }
            int index = (start++)%QUEUE_SIZE;
            qSize--;
            return Queue[index];
    }
    int IsQueueEmpty() {
            if (qSize == 0) {
                    return 1;
            }
            return 0;
    }
    
    
    #endif

// 图（邻接表方式）的广度优先搜索
    // 注：顶点从1开始
    /*
    	params:
    	s: int   开始搜索的顶点
    	n: int   图中所有的顶点数
    */
    void BFS(int s, int n)
    {
            int visited[n+1];
            // 图的顶点从1开始
            for (int i = 1; i < n+1; ++i)
                    visited[i] = 0;
    
            visited[s] = 1;
    
            printf("BFS: %d", s);
            EnQueue(s);
            while (!IsQueueEmpty()) {
                    int u = DeQueue();
                    Vertex *pv = Adj[u].next;
                    while (pv) {
                            int v = pv->v;
                            if (visited[v] == 0) {
                                    visited[v] = 1;
                                    EnQueue(v);
                                    printf("--%d", v);
                            }
                            pv = pv->next;
                    }
            }
            printf("\n");
    
    }

\#\#矩阵方式表示图的广度优先搜索

// 图（矩阵表示）的广度优先搜索
      void BFS(int src, int n)
      {
              int visited[n+1]; 
              for (int i = 1; i <= n; i++)
                      visited[i] = 0;
      
              visited[src] = 1;
              EnQueue(src);
              printf("BFS: %d", src); 
              while (!IsQueueEmpty()) {
                      int u = DeQueue();
                      for (int i = 1; i <= n; i++) {
                              if (G[u][i] == 1 && visited[i] == 0) {
                                      visited[i] = 1;   
                                      EnQueue(i);       
                                      printf("--%d", i);
                              }
                      }
              }
       
              printf("\n");
     }

\#\#广度优先搜索的时间复杂度和空间复杂度

*  每个顶点出队入队操作需要O(1)的时间，因此队列操作所需的全部时间为O(V)。因为只有当每个顶点将出队时，才会扫描其邻接表，因而每个顶点的邻接表至多被扫描一次，扫描所有邻接表花费全部时间为O(E)。因此BFS的总运行时间为O(V+E)。
 *  有上面算法可知，广度优先搜索的空间复杂度O(|V|+|E|)，即所有顶点的个数和边的条数；因为边和顶点都必须存储。

\#图的深度优先搜索  
\#\#邻接表方式表示图的深度优先搜索  
构造和初始化图使用[图的表示法][Link 1]章节中**邻接表方法表示图**的代码

// 自定义简单栈
    #ifndef __STACK_H__
    #define __STACK_H__
    
    #define STACK_SIZE 100
    
    int stack[STACK_SIZE] = {0};
    int curIndex = 0;
    
    int top()
    {
        if (curIndex != 0) {
            int idx = curIndex;
            return stack[--idx];
        }
        printf("stack empty");
        return -1;
    }
    void push(int n) 
    {
        if (curIndex == STACK_SIZE) {
            perror("stack is full");
            return;
        }
    
        stack[curIndex++] = n;
    }
    
    int pop()
    {
        if (curIndex == 0) {
            perror("stack is empty");
            return -1;
        }
        curIndex--;
        return stack[curIndex];
    }
    
    /*
    Returns: 1,empty 0,non-empty
     */
    
    int isStackEmpty()
    {
        if (curIndex == 0) 
            return 1;
        return 0;
    }
    
    #endif

// 图由邻接表存储
    
    /*
      图的深度优先遍历
    */
    
    void DFS(int cur)
    {
        printf("%d ", cur);
    
        Vertex *pv = Adj[cur].next;
        while (pv) {
            int v = pv->v;
            DFS(v);
            pv = pv->next;
        }
    }

/*
    	图的深度遍历-使用栈
    */
    // n : 顶点个数
    int visited[n];
    void init(int *v, int n) {
    	for (int i = 0; i < n; i++) {
    		v[i] = 0;
    	}
    }
    
    void DFS(int cur)
    {
    	init(visited, n);
     	push(cur);
     	Vertex *pv = NULL;
    	while (isStackEmpty() != 0) {
    		int v = top();
    	   	if (visited[v] != 1) {
    			printf("%d ", v);
    			visted[v] = 1;
    		}
    		pv = Adj[v].next;
    		while (pv && visited[pv->v] == 1) {
    			pv = pv->next;
    		}
    		if (pv) {
    		    push(pv->v);
    		} else {
    			pop();
    		}
    	}
    
    }

[Link 1]: http://blog.csdn.net/renwotao2009/article/details/51660688