图的邻接矩阵创建与深度（广度）遍历

参考资料
http://blog.csdn.net/andyelvis/article/details/1728378

图的相关概念##

待补充

用邻接矩阵创建图无向图##

#define TRUE 1
#define FALSE 0

#define MAX_LENGTH 100

typedef int Boolean;
Boolean visited[MAX_LENGTH];        // 访问标志的数组

// 图结构
typedef struct Grapha{
    char vertext[MAX_LENGTH];    // 顶点数组
    int arc[MAX_LENGTH][MAX_LENGTH]; // 邻接矩阵
    int numVertexts, numEdges;  // 顶点数与边数
} Grapha, *P_Grapha;

// 创建图
void createMGrah(P_Grapha *G) {
    int i, j;
    
    int v, e;
    printf("输入图的顶点数与边数:");
    scanf("%d %d", &v, &e);
    getchar();
    
    (*G) = (P_Grapha)malloc(sizeof(Grapha));
    (*G)->numVertexts = v;
    (*G)->numEdges = e;
    
    // 初始化顶点
    for(i=0; i<v; i++) {
        printf("请输入第%d个顶点:", (i+1));
        scanf("%c", &(*G)->vertext[i]);
        getchar();
    }
    
    
    // 初始化边（无向）
    for(i=0; i<v; i++) {
        for(j=0; j<v; j++) {
            (*G)->arc[i][j] = 0;
        }
    }
    
    // 初始化边
    for(v=0; v<(*G)->numEdges; v++) {
        printf("请输入第%d条边(Vi,Vj)上的下标i,下标j:\n", (v+1));
        scanf("%d %d", &i, &j);
        (*G)->arc[i][j] = 1;
        (*G)->arc[j][i] = (*G)->arc[i][j] ;         // 是无向网图，对称矩阵
        getchar();
    }
    
    // 输出矩阵
    printf("------------ 无向邻接矩阵 ----------\n");
    for(i=0; i<(*G)->numVertexts; i++) {
        if(i == 0) {
            printf("----%d-",i);
        } else {
            printf("%d-",i);
        }
    }
    printf("\n");
    
    for(i=0; i<(*G)->numVertexts; i++) {
        if(i == 0) {
            printf("----%c-",(*G)->vertext[i]);
        } else {
            printf("%c-",(*G)->vertext[i]);
        }
    }
    printf("\n");
    
    for(i=0; i<(*G)->numVertexts; i++) {
        for(j=0; j<(*G)->numVertexts; j++) {
            if(j == 0) {
                printf("%d-%c|%d-",i,(*G)->vertext[i], (*G)->arc[i][j]);
            } else {
                printf("%d-",(*G)->arc[i][j]);
            }
        }
        printf("\n");   // 换行
    }
}

深度遍历（DFS算法实现代码，遍历二维数组的方式）##

// =============  深度优先遍历  二维数组 Start =============
void dfs(P_Grapha G, int i) {
    printf("%c ", G->vertext[i]);
    visited[i] = TRUE;
    
    int j;
    for(j = 0; j<G->numVertexts; j++) {
        if(G->arc[i][j] == 1 && !visited[j]) {
            dfs(G, j);
        }
    }
}

void dfsGraph(P_Grapha G) {
    int i;
    for(i=0; i<G->numVertexts; i++) {
        visited[i] = FALSE;
    }
    
    for(int i=0; i<G->numVertexts; i++) {
        if(!visited[i]) {
            dfs(G, i);
        }
    }
}

主程序

int main(int argc, const char * argv[]) {
    P_Grapha g;
    createMGrah(&g);
    dfsGraph(g);
    return 0;
}

深度遍历（采用栈的形式）##

需要遵循的3个规则：

1. 选取当前顶点的邻接的未访问到的顶点，标记他，并将其放入栈中；
2. 如果不能执行规则1时，如果栈不为空，就从栈中弹出一个顶点，否则执行规则1；
3. 重复执行1，2规则，直到不能执行1，2规则时，就完成了整个搜索过程；

实现代码

// =============  深度优先遍历  使用栈 Start =============
// 清空已访问过得顶点数组
void clearVisit(P_Grapha G) {
    int i;
    for(i=0; i<G->numVertexts; i++) {
        visited[i] = FALSE;
    }
}

// 得到与顶点邻接，且未访问过得顶点
int getAdjUnivisitedVertex(P_Grapha G, int v) {
    int j;
    for(j = 0; j<G->numVertexts; j++) {
        if(G->arc[v][j] == 1 && visited[j] != TRUE) {
            return j;
        }
    }
    
    return -1;

}

SeqStack *stack;
void dfs_stack(P_Grapha G) {
    // 创建栈,并初始化栈
    stack = (SeqStack *)malloc(sizeof(SeqStack));
    initStack(stack);
    clearVisit(G);
    
    // 访问第一个顶点
    printf("%c ", G->vertext[0]);
    visited[0] = TRUE;
    push(stack, 0);
    
    // 栈不为空
    while(isEmpty(stack) == FALSE) {
        int p;
        int v;
        peek(stack, &p);
        
        v = getAdjUnivisitedVertex(G, p);   // 得到与顶点p相邻接的顶点
        if(v == -1) {       // 没找到，就从栈中弹出一个顶点
            int top;
            pop(stack, &top);
        } else {            // 找到了，打印顶点，并入栈
            printf("%c ", G->vertext[v]);
            visited[v] = TRUE;
            push(stack, v);
        }
    }
    
    
    clearVisit(G);
}


// =============  深度优先遍历  使用栈 End =============

广度遍历（采用队列的形式）
遵循原则：

1. 不断访问当前顶点的下一个的顶点，此顶点必须是当前顶点的邻接点，标记它，并将其插入队列；
2. 如果没有未访问的顶点，不能执行1时，则从队列头中取一个顶点，使其成为当前顶点，继续执行1；
3. 队列为空时不能执行2时，表示结束

// =============  广度优先遍历  使用栈 Start =============
Queue *que;
void bfs(P_Grapha G) {
    que = (Queue *)malloc(sizeof(Queue));
    initQueue(que);
    clearVisit(G);
    
    printf("%c ", G->vertext[0]);
    visited[0] = TRUE;              // 类似层序遍历
    insertQueue(que, 0);
    
    int v1;
    int v2;
    while(isQueueEmpty(que) == FALSE) {
        removeQueue(que, &v1);
        while( (v2 = getAdjUnivisitedVertex(G, v1)) != -1 ) {     // 不断获取当前顶点的邻接点
            printf("%c ", G->vertext[v2]);  // 找到邻接点，放入对列中
            visited[v2] = TRUE;
            insertQueue(que, v2);
        }
    }
    
    
    clearVisit(G);
}