Highlighted text? Practice this concept. Highlighted passages and figures open related questions.
Practice related questions (1)Progress & bookmarks
Current section
2-4-2 Graph Processing
p. 439
Practice this section 1 linked exam question with default filters
Progress
Not marked complete
Related questions in this lesson 1
Depth-first graph search and backtracking1p. 439 · PDF 449
2-4-2 Graph Processing
Graph processing is an algorithm that uses a graph. Graph is a pictorial figure that is made of nodes and branches (or edges). (A tree structure is also a kind of graph.) Graphs include directed graph where branches have a direction like a state transition diagram, and undirected graph where branches have no direction like a tree structure or a network diagram. A graph can be represented with a matrix, array, list, and so on. In algorithms, mostly an adjacency matrix (i.e., array) is used that shows the adjacent (or linked) status of nodes. The following is an example of an adjacency matrix that shows an undirected graph (i.e., network diagram). In this example, cost (e.g., distance) of branches that connect nodes is recorded to
p. 440 · PDF 450
show that there is a branch. (0 if there is no branch.)
Original source text
1
2
3
4
5
6
7
1
0
30
0
40
0
0
0
2
30
0
70
0
0
0
0
3
0
70
0
0
0
0
0
4
40
0
0
0
50
20
0
5
0
0
0
50
0
10
60
6
0
0
0
20
10
0
80
7
0
0
0
0
60
80
0
Source visual description
Original Graph Processing source layout. Source labels: 1; 2; 3; 4; 5.
Representative graph processing is route searching that searches for the route from the origin point (i.e., node) up to the target point (i.e., node). The following are the two main methods of route searching.
- • Depth-first search
Depth-first search searches one path until the end (i.e., dead-end or target point). When it is found that the route is not the solution (e.g.,
it returns to the earlier point and searches for a different route. In this manner, it is a backtrack method (backtracking). · 1 question - • Breadth-first search
Breadth-first search searches the route in a hierarchical manner. It repeats the process of determining the node at one layer below adjacent to each node until the target node is found.
However, in these two methods, the route that was found may not be always the shortest route (i.e., route with minimum cost: 
Therefore, as the method of shortest route search (or shortest path search), the Dijkstra method was proposed so that the lowest cost node can be finalized one by one in order.
[General procedure of Dijkstra method]
1) At the node adjacent to origin node, finalize the lowest cost node X.
2) Including the adjacent nodes to the finalized node X, finalize one lowest cost node among them.
3) Repeat the process of step 2) until the lowest cost of all nodes is finalized. => Decide the lowest cost (i.e., route) up to the target node.
Section progress
Original chapter exercises
Original chapter exercises →New FE Textbook Vol.1 · IT Fundamentals · First Edition, April 2015