图（Graph）是由顶点 (Vertex) 的有穷非空集合 和顶点之间 边 的集合组成，通常表示为：G(V, E) , 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
一、图的遍历
总代码
#include#include int *visitedPtr; typedef struct GraphNodeQueue{ int *nodes; int front; int rear; } GraphNodeQueue, *QueuePtr; QueuePtr initQueue() { QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(GraphNodeQueue)); resultQueuePtr->nodes = (int*)malloc(sizeof(int) * 10); resultQueuePtr->front = 0; resultQueuePtr->rear = 0; return resultQueuePtr; } int isQueueEmpty(QueuePtr paraQueuePtr) { if (paraQueuePtr->front == paraQueuePtr->rear) { return 1; } return 0; } void enqueue(QueuePtr paraQueuePtr, int paraNode) { if ((paraQueuePtr->rear + 1) % 10 == paraQueuePtr->front) { printf("Error, trying to enqueue %d. queue fulln", paraNode); return; } paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode; paraQueuePtr->rear = (paraQueuePtr->rear + 1) % 10; } int dequeue(QueuePtr paraQueuePtr) { int tempValue; if (isQueueEmpty(paraQueuePtr) == 1) { printf("Error, empty queuen"); return 0; } tempValue = paraQueuePtr->nodes[paraQueuePtr->front]; paraQueuePtr->front = (paraQueuePtr->front + 1) % 10; return tempValue; } typedef struct Graph{ int **connections; int numNodes; } *GraphPtr; GraphPtr initGraph(int paraSize, int **paraData) { int i, j; GraphPtr resultPtr = (GraphPtr)malloc(sizeof(struct Graph)); resultPtr->numNodes = paraSize; resultPtr->connections = (int**)malloc(sizeof(int*)); for (i = 0; i < paraSize; i ++) { resultPtr->connections[i] = (int*)malloc(sizeof(int) * paraSize); for (j = 0; j < paraSize; j ++) { resultPtr->connections[i][j] = paraData[i][j]; } } return resultPtr; } void initTranverse(GraphPtr paraGraphPtr) { int i; visitedPtr = (int*)malloc(sizeof(int) * paraGraphPtr->numNodes); for (i = 0; i < paraGraphPtr->numNodes; i ++) { visitedPtr[i] = 0; } } void depthFirstTranverse(GraphPtr paraGraphPtr, int paraNode) { int i; visitedPtr[paraNode] = 1; printf("%dt", paraNode); for (i = 0; i < paraGraphPtr->numNodes; i ++) { if (visitedPtr[i] == 0) { if (paraGraphPtr->connections[paraNode][i] == 1) { depthFirstTranverse(paraGraphPtr, i); } } } } void widthFirstTranverse(GraphPtr paraGraphPtr, int paraStart) { int i, j, tempNode; i = 0; QueuePtr tempQueuePtr = initQueue(); printf("%dt", paraStart); visitedPtr[paraStart] = 1; enqueue(tempQueuePtr, paraStart); while (isQueueEmpty(tempQueuePtr) == 0) { tempNode = dequeue(tempQueuePtr); visitedPtr[tempNode] = 1; i ++; for (j = 0; j < paraGraphPtr->numNodes; j ++) { if (visitedPtr[j] == 1) { continue; } if (paraGraphPtr->connections[tempNode][j] == 0) { continue; } printf("%dt", j); visitedPtr[j] = 1; enqueue(tempQueuePtr, j); } } } void testGraphTranverse() { int i, j; int myGraph[5][5] = { {0, 1, 0, 1, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 1}, {1, 0, 1, 0, 0}, {0, 1, 1, 0, 0}}; int **tempPtr; printf("Preparing datan"); tempPtr = (int**)malloc(sizeof(int*) * 5); for (i = 0; i < 5; i ++) { tempPtr[i] = (int*)malloc(sizeof(int) * 5); } for (i = 0; i < 5; i ++) { for (j = 0; j < 5; j ++) { tempPtr[i][j] = myGraph[i][j]; } } printf("Data readyn"); GraphPtr tempGraphPtr = initGraph(5, tempPtr); printf("num nodes = %dn", tempGraphPtr->numNodes); printf("Graph initializedn"); printf("Depth first visit:n"); initTranverse(tempGraphPtr); depthFirstTranverse(tempGraphPtr, 4); printf("rnWidth first visit:n"); initTranverse(tempGraphPtr); widthFirstTranverse(tempGraphPtr, 4); } int main() { testGraphTranverse(); return 0; }
结果
Preparing data Data ready num nodes = 5 Graph initialized Depth first visit: 4 1 0 3 2 Width first visit: 4 1 2 0 3
里面用到了深度优先和广度优先
广度优先类似于树的层序遍历，用到了队列，而深度优先则是类似二叉树的先序遍历，用的是递归实现
深度优先：沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止
广度优先：基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。
二、邻接表
总代码
#include#include int *visitedPtr; typedef struct Graph{ int **connections; int numNodes; } *GraphPtr; GraphPtr initGraph(int paraSize, int **paraData) { int i, j; GraphPtr resultPtr = (GraphPtr)malloc(sizeof(struct Graph)); resultPtr->numNodes = paraSize; resultPtr->connections = (int**)malloc(sizeof(int*) * paraSize); for (i = 0; i < paraSize; i ++) { resultPtr->connections[i] = (int*)malloc(sizeof(int) * paraSize); for (j = 0; j < paraSize; j ++) { resultPtr->connections[i][j] = paraData[i][j]; } } return resultPtr; } typedef struct GraphNodeQueue{ int* nodes; int front; int rear; }GraphNodeQueue, *QueuePtr; QueuePtr initQueue(){ QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct GraphNodeQueue)); resultQueuePtr->nodes = (int*)malloc(sizeof(int) * 10); resultQueuePtr->front = 0; resultQueuePtr->rear = 0; return resultQueuePtr; } int isQueueEmpty(QueuePtr paraQueuePtr){ if (paraQueuePtr->front == paraQueuePtr->rear) { return 1; } return 0; } void enqueue(QueuePtr paraQueuePtr, int paraNode){ if ((paraQueuePtr->rear + 1) % 10 == paraQueuePtr->front) { printf("Error, trying to enqueue %d. queue full.n", paraNode); return; } paraQueuePtr->nodes[paraQueuePtr->rear] = paraNode; paraQueuePtr->rear = (paraQueuePtr->rear + 1) % 10; } int dequeue(QueuePtr paraQueuePtr){ int tempValue; if (isQueueEmpty(paraQueuePtr) == 1) { printf("Error, empty queuen"); return 0; } tempValue = paraQueuePtr->nodes[paraQueuePtr->front]; paraQueuePtr->front = (paraQueuePtr->front + 1) % 10; return tempValue; } typedef struct AdjacencyNode{ int colum; struct AdjacencyNode *next; } AdjacencyNode, *AdjacentNodePtr; typedef struct AdjacencyList{ int numNodes; AdjacencyNode *headers; } AdjacencyList, *AdjacencyListPtr; AdjacencyListPtr graphToAdjacentList(GraphPtr paraPtr) { int i, j, tempNum; AdjacentNodePtr p, q; tempNum = paraPtr->numNodes; AdjacencyListPtr resultPtr = (AdjacencyListPtr)malloc(sizeof(AdjacencyList)); resultPtr->numNodes = tempNum; resultPtr->headers = (AdjacentNodePtr)malloc(sizeof(AdjacencyNode) * tempNum); for (i = 0; i < tempNum; i ++) { p = &(resultPtr->headers[i]); for (j = 0; j < tempNum; j ++) { if (paraPtr->connections[i][j] > 0) { q = (AdjacentNodePtr)malloc(sizeof(AdjacencyNode)); q->colum = j; q->next = NULL; p->next = q; p = q; } } } return resultPtr; } void printAdjacentList(AdjacencyListPtr paraPtr) { int i; AdjacentNodePtr p; int tempNum = paraPtr->numNodes; printf("This is the graph:n"); for (i = 0; i < tempNum; i ++) { p = paraPtr->headers[i].next; while (p != NULL) { printf("%d, ", p->colum); p = p->next; } printf("n"); } } void widthFirstTranverse(AdjacencyListPtr paraListPtr, int paraStart) { printf("width firstn"); int i, j, tempNode; AdjacentNodePtr p; i = 0; visitedPtr = (int*)malloc(sizeof(int) * paraListPtr->numNodes); for (i = 0; i < paraListPtr->numNodes; i ++) { visitedPtr[i] = 0; } QueuePtr tempQueuePtr = initQueue(); printf("%dt", paraStart); visitedPtr[paraStart] = 1; enqueue(tempQueuePtr, paraStart); while (isQueueEmpty(tempQueuePtr) == 0) { tempNode = dequeue(tempQueuePtr); p = paraListPtr->headers[tempNode].next; for (; p != NULL; p = p->next) { j = p->colum; if (visitedPtr[j] == 1) { continue; } printf("%dt", j); visitedPtr[j] = 1; enqueue(tempQueuePtr, j); } } } void testGraphTranverse() { int i, j; int myGraph[5][5] = { {0, 1, 0, 1, 0}, {1, 0, 1, 0, 1}, {0, 1, 0, 1, 1}, {1, 0, 1, 0, 0}, {0, 1, 1, 0, 0}}; int **tempPtr; printf("Preparing datan"); tempPtr = (int**)malloc(sizeof(int*) * 5); for (i = 0; i < 5; i ++) { tempPtr[i] = (int*)malloc(sizeof(int) * 5); } for (i = 0; i < 5; i ++) { for (j = 0; j < 5; j ++) { tempPtr[i][j] = myGraph[i][j]; } } printf("Data readyn"); GraphPtr tempGraphPtr = initGraph(5, tempPtr); AdjacencyListPtr tempListPtr = graphToAdjacentList(tempGraphPtr); printAdjacentList(tempListPtr); widthFirstTranverse(tempListPtr, 4); } int main() { testGraphTranverse(); return 0; }
结果
Preparing data Data ready This is the graph: 1, 3, 0, 2, 4, 1, 3, 4, 0, 2, 1, 2, width first 4 1 2 0 3
邻接表：图中顶点用一个一维数组存储，当然也可以用单链表来存储，不过用数组可以较容易的读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息
总结
深度优先用的是递归实现，广度优先用的是队列，同时也要区分循环队列的队满和队空时的条件，否则很容易出错
在邻接表中，注意用的时候，有一个头结点，所以要到它的下一个才存有要使用的数据
图像出处：https://blog.csdn.net/createprogram/article/details/100104235?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165391395316782184677767%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165391395316782184677767&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-100104235-null-null.142^v11^pc_search_result_control_group,157^v12^new_style2&utm_term=%E9%82%BB%E6%8E%A5%E8%A1%A8&spm=1018.2226.3001.4187
