参考资料
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时，如果栈不为空，就从栈中弹出一个顶点，否则执行规则1；
- 重复执行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时，则从队列头中取一个顶点，使其成为当前顶点，继续执行1；
- 队列为空时不能执行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);
}
